BOJ 풀이 노트: 피보나치 DP와 다익스트라 최단경로 점검

2026. 3. 3. · tech

BOJ 1003, 1753 풀이를 중심으로 호출 횟수 DP와 우선순위 큐 기반 최단경로 구현의 실전 포인트를 정리했다.

오늘은 성격이 다른 두 문제를 묶어서 풀었다.

• BOJ 1003 - 피보나치 함수
• BOJ 1753 - 최단경로

1003은 재귀 호출 패턴을 DP로 치환하는 문제이고, 1753은 가중치가 있는 단일 시작점 최단거리 문제의 기본형이다.

1) BOJ 1003 - 피보나치 함수

문제 핵심 요약

피보나치 재귀 함수를 호출했을 때 fibonacci(0)과 fibonacci(1)이 각각 몇 번 호출되는지 구하는 문제다.

접근 아이디어(왜 이 방법인지)

직접 재귀를 돌리면 중복 호출이 매우 많아진다. 호출 횟수 자체도 피보나치 점화식을 따르기 때문에 DP 테이블로 한 번만 계산해두면 된다.

dp[n] = {zeroCount, oneCount}로 두고,

• dp[0] = {1, 0}
• dp[1] = {0, 1}
• dp[n] = dp[n-1] + dp[n-2]

로 채우면 각 질의를 O(1)에 답할 수 있다.

시간/공간 복잡도

• 시간: 전처리 O(40), 질의당 O(1)
• 공간: O(40)

실수하기 쉬운 포인트

• 초기값 dp[0], dp[1]를 반대로 두는 실수
• 테스트케이스마다 매번 재귀/DP를 다시 계산해 불필요하게 느려지는 구현
• n의 최댓값(40)을 고려하지 않고 배열 크기를 작게 잡는 실수

C++ 코드 설명(핵심 라인)

dp[0] = {1, 0};
dp[1] = {0, 1};
for (int i = 2; i <= 40; i++) {
    dp[i].first = dp[i - 1].first + dp[i - 2].first;
    dp[i].second = dp[i - 1].second + dp[i - 2].second;
}

호출 횟수 쌍을 점화식으로 누적하는 핵심 구간이다.

cout << dp[n].first << ' ' << dp[n].second << '\n';

전처리된 값을 바로 출력해 각 테스트케이스를 상수 시간에 처리한다.

다른 풀이 가능성

• 메모이제이션 재귀로도 해결 가능하다.
• 하지만 이 문제는 반복문 기반 바텀업 DP가 코드가 더 짧고 실수 여지가 적다.

2) BOJ 1753 - 최단경로

문제 핵심 요약

방향 그래프에서 시작 정점 K로부터 모든 정점까지의 최단거리를 구하는 문제다. 도달할 수 없는 정점은 INF를 출력한다.

접근 아이디어(왜 이 방법인지)

간선 가중치가 양수이므로 다익스트라 알고리즘이 정석이다. 우선순위 큐에 (현재까지 거리, 정점)을 넣고 가장 짧은 후보부터 확정해 나가면 된다.

핵심은 이미 더 짧은 거리로 갱신된 항목은 버리는 것이다.

시간/공간 복잡도

• 시간: O((V + E) log V)
• 공간: O(V + E)

실수하기 쉬운 포인트

• if (curDist > dist[curNode]) continue; 체크 누락으로 중복 확장 과다
• 무방향 그래프처럼 반대 간선까지 추가하는 실수 (이 문제는 방향 그래프)
• 거리 초기값/자료형 처리 미흡으로 오버플로우 위험 증가
• 도달 불가 정점 출력을 INF 문자열이 아닌 숫자로 출력하는 실수

C++ 코드 설명(핵심 라인)

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[K] = 0;
pq.push({0, K});

최소 힙으로 사용할 우선순위 큐를 만들고 시작점을 초기화한다.

if (curDist > dist[curNode]) continue;
for (auto [nextNode, weight] : graph[curNode]) {
    int nextDist = curDist + weight;
    if (nextDist < dist[nextNode]) {
        dist[nextNode] = nextDist;
        pq.push({nextDist, nextNode});
    }
}

느슨한(오래된) 큐 항목을 건너뛰고, 더 짧은 경로가 발견될 때만 갱신하는 전형적인 다익스트라 패턴이다.

다른 풀이 가능성

• 간선 가중치가 0/1만 나온다면 0-1 BFS를 고려할 수 있다.
• 모든 정점 쌍 최단거리가 필요하면 플로이드-워셜도 가능하지만, 이 문제는 단일 시작점이므로 다익스트라가 가장 적합하다.

오늘 포인트는 두 가지다.

• 반복되는 재귀 호출 구조는 DP 상태로 바꾸면 계산량을 크게 줄일 수 있다.
• 가중치 양수 그래프의 단일 시작점 최단거리는 다익스트라를 안정적으로 구현하는 습관이 중요하다.

서로 다른 유형을 하루에 2문제씩 고정 루틴으로 섞어 풀면, 자료구조 선택 감각과 구현 정확도가 같이 올라간다.