자바 코딩테스트 강좌, 정수를 1로 만들기

코딩테스트 준비에 있어서 다양한 알고리즘 문제들을 풀어보는 것은 매우 중요합니다. 이번 강좌에서는 ‘정수를 1로 만들기’라는 문제를 통해 기본적인 문제 해결 능력을 기르고, 효율적인 알고리즘을 설계하는 과정을 살펴보겠습니다. 이 문제는 주어진 정수를 몇 가지 연산을 통해 1로 만들 수 있는 최소 횟수를 찾는 문제입니다.

문제 정의

주어진 정수 N이 있을 때, 아래의 세 가지 연산 중 하나를 선택하여 숫자를 변형할 수 있습니다:

  • 감소(Decrement): N - 1
  • 2로 나누기(Divide by 2): N / 2 (단, N이 짝수일 때만 가능)
  • 3으로 나누기(Divide by 3): N / 3 (단, N이 3으로 나누어 떨어질 때만 가능)

목표는 이러한 연산을 통해 N을 1로 만드는 최소의 연산 횟수를 구하는 것입니다.

예제 입력 및 출력

  • 입력: N = 10
  • 출력: 3 (10 → 9 → 3 → 1)

문제 해결을 위한 접근법

이 문제를 해결하기 위한 몇 가지 접근법이 있습니다. 여기서는 DFS(Depth-First Search)와 DP(Dynamic Programming) 두 가지 방법을 소개하겠습니다.

1. DFS (Depth-First Search)

먼저 DFS를 사용하여 모든 가능한 경로를 탐색하는 방법을 생각해볼 수 있습니다. 그러나 이 방법은 시간 복잡도가 매우 높아질 수 있습니다. 예를 들어, N=10의 경우 나올 수 있는 경로의 수가 많기 때문입니다. 그럼에도 불구하고 DFS로 접근해보도록 하겠습니다.

DFS 구현 코드

import java.util.HashMap;

public class Main {
    static int minSteps = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        int N = 10;
        findSteps(N, 0);
        System.out.println("Minimum steps to reach 1: " + minSteps);
    }
    
    private static void findSteps(int N, int steps) {
        if (N == 1) {
            minSteps = Math.min(minSteps, steps);
            return;
        }
        
        findSteps(N - 1, steps + 1); // Decrement
        if (N % 2 == 0) {
            findSteps(N / 2, steps + 1); // Divide by 2
        }
        if (N % 3 == 0) {
            findSteps(N / 3, steps + 1); // Divide by 3
        }
    }
}

상기 코드는 주어진 N에서 가능한 모든 경로를 탐색합니다. 그러나 이 방법은 중복 호출 및 비효율적인 경로 탐색으로 인해 시간 복잡도가 O(3^N)입니다.

2. DP (Dynamic Programming)

따라서 더 효율적인 방법은 DP를 사용하는 것입니다. DP를 사용하면 기존에 계산된 결과를 저장하고 필요할 때 재사용함으로써 불필요한 계산을 줄일 수 있습니다.

DP 구현 코드

public class Main {
    public static void main(String[] args) {
        int N = 10;
        System.out.println("Minimum steps to reach 1: " + minStepsDP(N));
    }

    private static int minStepsDP(int N) {
        int[] dp = new int[N + 1];
        dp[1] = 0; // 1로 가는 최소 연산 횟수는 0
        
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1; // Decrement

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); // Divide by 2
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1); // Divide by 3
            }
        }
        
        return dp[N];
    }
}

상기 DP 구현 코드는 배열 dp를 사용하여 각 숫자까지 가기 위한 최소 단계를 저장합니다. 알고리즘은 O(N)의 시간 복잡도를 가집니다. 각각의 숫자에 대해 이전 숫자들의 값을 참조하여 최소 단계를 계산합니다.

시간 복잡도 분석

DFS 접근법은 시간 복잡도가 O(3^N)로 매우 비효율적입니다. 반면 DP 접근법은 O(N)의 시간 복잡도를 가지며, 이는 모든 숫자에 대해 최대 한 번의 계산으로 최소 단계를 도출할 수 있습니다.

결론

이번 강좌에서는 정수를 1로 만들기 위한 알고리즘의 다양한 접근법을 살펴보았으며, DFS와 DP를 통해 효율적인 문제 해결 방식을 배웠습니다. 코딩 테스트를 준비하는 데 있어 실제 알고리즘을 이해하고, 그것을 기반으로 문제를 해결하는 능력을 기르는 것이 중요합니다. 이 문제처럼 복잡한 문제들을 해결하기 위해 여러 접근법을 익히고, 최적화된 방법을 선택하는 연습을 지속하시길 바랍니다.

연습문제

아래의 추가 문제를 풀어보며 연습해보세요:

  • 정수 N = 15일 때, 1로 만들기 위한 최소 연산 횟수를 구하세요.
  • 정수 N = 25일 때, 1로 만들기 위한 최소 연산 횟수를 구하세요.

문제를 풀어보면서 가능하다면, 다양한 입력값에 대해 결과를 출력해보세요. 코딩 테스트는 단순히 문제를 푸는 것이 아니라, 최적의 해결 방법을 찾아내는 것이 중요합니다.