C++ 코딩테스트 강좌, 타임머신으로 빨리 가기

요즘 많은 기업에서 코딩 테스트를 통해 지원자의 알고리즘적 사고력과 문제 해결 능력을 평가하고 있습니다. 이번 강좌에서는 “타임머신으로 빨리 가기”라는 흥미로운 알고리즘 문제를 통해, 문제를 이해하고 해결하는 과정을 자세히 설명하겠습니다. 특히, C++ 언어를 사용하여 효율적이고 최적화된 해결책을 찾아보겠습니다.

문제 설명

당신은 시간을 초월할 수 있는 타임머신을 갖고 있습니다. 그러나 이 타임머신은 특정 규칙에 따라 작동합니다. 타임머신의 작동 규칙은 다음과 같습니다:

당신은 현재 시간 t에 있으며, 이 시간은 양의 정수입니다.
당신은 k 초 후로 이동할 수 있고, k는 최대 C로 제한됩니다.
각 이동 후에는 새로운 시간 t + k를 기준으로 다시 k를 정할 수 있습니다.
이렇게 여러 번 이동하여 목표 시간 N에 도달해야 합니다.

당신은 현재 시간 t와 목표 시간 N, 그리고 최대 이동 시간 C가 주어졌을 때, 목표 시간 N에 도달하기 위해 필요한 최소 이동 횟수를 구하는 프로그램을 작성해야 합니다.

입력 형식

첫 번째 줄에 현재 시간 t (1 ≤ t ≤ 10⁵), 목표 시간 N (t ≤ N ≤ 10⁵), 최대 이동 시간 C (1 ≤ C ≤ 1000)가 주어집니다.

출력 형식

목표 시간 N에 도달하기 위한 최소 이동 횟수를 출력합니다.

예시

설명: 고객은 시간 5에서 시작하여, 3초 후로 이동 (시간 8), 다시 2초 후로 이동 (시간 10)하여 총 2번 이동함으로써 목표시간 10에 도달합니다.

문제 해결 전략

이 문제는 BFS(너비 우선 탐색)를 활용하여 해결할 수 있습니다. BFS는 그래프나 트리에서 최단 경로를 탐색할 때 매우 유용한 알고리즘입니다. 이 문제에서의 그래프는 현재 시간과 목표 시간을 이루는 노드로 생각할 수 있으며, 각 이동이 그래프의 간선으로 작용합니다.

BFS 알고리즘의 단계

큐를 사용하여 BFS를 시작합니다. 초기 상태는 현재 시간 t로 설정합니다.
큐에서 현재 시간을 꺼내고, 목표 시간 N에 도달했는지 확인합니다.
현재 시간에서 가능한 모든 이동(1초부터 C초까지)을 시도하여 새로운 시간을 계산하고, 이 새로운 시간이 목표 시간 N에 도달할 수 있는지 확인합니다.
새로운 시간이 목표 시간 N이라면 이동 횟수를 출력합니다. 아니라면, 새로운 시간을 큐에 추가하여 탐색을 계속합니다.

C++ 코드 구현

    #include 
    #include 
    #include 
    using namespace std;

    int minMoves(int t, int N, int C) {
        vector visited(N + 1, false);
        queue> q; // {current_time, moves}
        q.push({t, 0});
        visited[t] = true;

        while (!q.empty()) {
            auto [current_time, moves] = q.front();
            q.pop();

            if (current_time == N) {
                return moves;
            }

            for (int jump = 1; jump <= C; ++jump) {
                int next_time = current_time + jump;
                if (next_time > N) {
                    continue; // 목표 시간을 초과하는 것은 무시
                }

                if (!visited[next_time]) {
                    visited[next_time] = true;
                    q.push({next_time, moves + 1});
                }
            }
        }

        return -1; // 도달 불가능한 경우
    }

    int main() {
        int t, N, C;
        cin >> t >> N >> C;
        cout << minMoves(t, N, C) << endl;
        return 0;
    }

코드 설명

위의 C++ 코드는 주어진 문제를 해결하기 위해 BFS 알고리즘을 구현한 것입니다.

<code>minMoves</code> 함수는 현재 시간, 목표 시간, 최대 이동 시간을 인자로 받습니다. 이 함수는 목표 시간 N에 도달하기 위한 최소 이동 횟수를 반환합니다.
우선 번째로 방문 여부를 저장하기 위한 배열 <code>visited</code>를 초기화하고, 큐를 준비합니다.
큐에서 현재 시간을 꺼내고, 목표 시간에 도달했다면 이동 횟수를 반환합니다.
현재 시간에서 최대 C초까지의 가능한 모든 이동을 시도하면서 새로운 시간을 큐에 추가합니다.
이 과정이 반복되면서 목표 시간에 도달할 경우, 해당 이동 횟수를 출력하게 됩니다.

결과 검증

여러 가지 입력에 대해 프로그램을 실행해 결과가 예상대로 출력되는지를 벤치마킹하고 검증해야 합니다. 예를 들면:

이렇게 입력을 주었을 때 각각의 이동 경로를 살펴보면, 최적 해가 나오는 것을 확인할 수 있습니다.

마무리

이번 강좌에서는 C++를 사용하여 “타임머신으로 빨리 가기” 문제를 해결하는 과정을 살펴보았습니다. BFS 알고리즘을 통해 최단 경로를 찾는 방법을 배웠으며, 실제 코드를 통해 문제를 해결하는 경험을 쌓았습니다. 이 지식은 실제 코딩 테스트 또는 알고리즘 문제 해결에 큰 도움이 될 것입니다. 다음 강좌에서도 더 흥미로운 문제를 다루기 기대해 주세요!