1. 문제

https://www.acmicpc.net/problem/1463

• 문제 설명: n값이 주어지면 3개의 과정중 하나를 고르는 과정을 반복하여 1에 도달하기까지 최소 계산 횟수를 구하는 문제.
  선택 가능한 과정이 2개였다면 이진 트리 탐색이나 고등학교 확률과 통계 과목에서 배우는 ‘같은 것이 있는 순열’ 개념을 활용하여 수학적으로 풀수 있다.
  그러나 이문제는 과정이 3개이므로 이진트리는 해당사항이 없고, 수학적으로 풀기에는 알고리즘이 매우 복잡해질 가능성이 높다.
  따라서 기본적으로 깊이 우선으로 트리를 탐색(DFS)하도록 하고 다이나믹 프로그래밍(DP)를 활용하여 최적화를 진행하였다.
• 사용 알고리즘 : DP, DFS

2. 풀이

2.1. 초기 코드

• 코드:

  // 최적화 되지않은 DFS (전수조사)
  import java.io.*;
  
  public class Main
  {
      static int minDepth = 1000000;
      static void search(int n,int depth) {
          if (n == 1) {
              minDepth = Math.min(depth, minDepth);
              return;
          }
          for(int i=0; i<2; i+=1)
              if(n%(3-i) == 0) search(n/(3-i), depth+1);
          search(n-1,depth+1);
      }
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
          int n = Integer.parseInt(br.readLine());
          search(n,0);
          bw.write(Integer.toString(minDepth));
          bw.flush();
          bw.close();
      }
  }
  

• 문제점:
  • 오직 DFS 만으로 1을 만들수 있는 모든 경우를 전수 조사 함으로써 n값이 커질수록 실행시간이 기하 급수적으로 증가하게 된다.
• 결과 : 시간 초과

2.2. 최적화 과정

• 최적화 필요성: 트리 탐색 관점으로 봤을때 모든 노드를 전수조사함으로 매우 오랜시간이 걸리게 되고 비효율적이다.
• 최적화 전략: 조건을 추가해 불필요한 노드 탐색 과정 제거
  • 변경: 노드 탐색 중 현재까지의 최소 작업 횟수보다 더 깊은 노드의 탐색시 탐색 작업을 즉시 종료

2.3. 최적화된 코드 (1차)

• 코드:

  // DFS 최적화 (1차)
  import java.io.*;
  
  public class Main
  {
      static int minDepth = 1000000;
      static void search(int n,int depth) {
          if (n == 1) {
              minDepth = Math.min(depth, minDepth);
              return;
          }
          //추가되어진 조건
          if (minDepth == depth) return;
          for(int i=0; i<2; i+=1)
              if(n%(3-i) == 0) search(n/(3-i), depth+1);
          search(n-1,depth+1);
      }
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
          int n = Integer.parseInt(br.readLine());
          search(n,0);
          bw.write(Integer.toString(minDepth));
          bw.flush();
          bw.close();
      }
  }
  

• 코드 설명:

  • 노드를 모두 탐색하되, 탐색하려는 노드의 깊이(Depth)가 마지막으로 구한 1을 만들기 위한 최소 깊이를 초과하는 경우 과정을 중단하도록 하여 실행 시간을 단축 시켰음.

2.4. 결과

• 결과 설명: 기존 코드에 비해 탐색하는 노드의 갯수가 대폭 감소하였다.

• 비교 분석 (n=1234):

  • 탐색 노드 갯수
    • 초기 코드 : 결과 도출 불가 (시간 초과)
    • 최적화(1차) : 1970개
  • 실행 속도(제출 결과)
    • 초기 코드 : 결과 도출 불가 (시간 초과)
    • 최적화(1차) : 140 ms
• 문제점:
  • 초기 코드에 비해 탐색 노드 갯수는 줄었으나 여전히 횟수가 작진 않다.
• 결과 : 정답 (14340KB, 140ms)

2.5. 최적화 과정

• 최적화 필요성: 이미 최소 계산 횟수를 계산한 이력이 있는 노드에 대해서도 중복으로 계산을 함으로써 탐색 노드 갯수가 늘어남.
• 최적화 전략: 계산했던 값들을 다시 활용할 수 있도록 알고리즘 수정 (DP)
  • 변경: 계산한 최소 계산 횟수를 별도로 기록하고, 동일한 수를 가진 노드의 최소 계산 횟수를 구할때 다시 계산하지 않고 이미 구한 값을 활용하도록 수정

2.6. 최적화된 코드(2차)

• 코드:

  // DFS 최적화 (2차)
  import java.io.*;
  
  public class Main
  {
      static int minDepth = 1000000;
      static int[] depthDict;
      static int search(int n,int depth) {
          if (n == 1) {
              minDepth = Math.min(depth, minDepth);
              return 1;
          }
          if(minDepth == depth) return 0;
          if (depthDict[n-1] != 0) {
              minDepth = Math.min(depth+depthDict[n-1], minDepth);
              return depthDict[n-1]+1;
          }
          int partialMinDepth = 1000000;
          for(int i=0; i<2; i+=1)
              if(n%(3-i) == 0) {
                  int tmp = search(n/(3-i), depth+1);
                  if(tmp == 0) continue;
                  partialMinDepth = Math.min(tmp,partialMinDepth);
              }
          int tmp = search(n-1,depth+1);
          if (tmp != 0) partialMinDepth = Math.min(tmp,partialMinDepth);
          if (partialMinDepth != 1000000) depthDict[n-1] = partialMinDepth;
          return partialMinDepth+1;
      }
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
          int n = Integer.parseInt(br.readLine());
          depthDict = new int[n];
          search(n,0);
          bw.write(Integer.toString(minDepth));
          bw.flush();
          bw.close();
      }
  }
  

• 코드 설명:

  • 1차 코드에 추가로 DP 개념을 적용. 각 노드로 부터 1까지의 최소 과정횟수를 별도로 배열에 저장하고, 동일한 수 노드 검사시 저장한 최소 횟수값을 불러와 중복계산을 방지하였다.

2.7. 결과

• 결과 설명: 최적화 코드(1차)에 비해 탐색하는 노드의 갯수가 대폭 감소하였다.
• 비교 분석 (n=1234):
  • 탐색 노드 갯수
    • 최적화(1차) : 1970개
    • 최적화(2차) : 11개
  • 실행 속도(제출 결과)
    • 최적화(1차) : 140 ms
    • 최적화(2차) : 104 ms
• 결과: 정답 (18132KB, 104ms)

3. 결론

• 요약: 트리 탐색을 이용할때 노드의 갯수가 많은경우 실행 시간이 매우 길어질수 있다. 별도의 조건을 부여하거나 DP같은 추가적인 알고리즘을 같이 활용하여 노드 탐색횟수를 줄이면서 실행 시간을 단축 시킬 수 있다.

4. 참고 자료

• DFS 개념 : <게시글 준비 중>
• DP 개념 : <게시글 준비 중>