[알고리즘 문제] Tobin

import java.util.Scanner;

public class Main {

    static int n;
    static int[] ary;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int k = sc.nextInt(); // 표시해야 할 남은 1을 의미
        ary = new int[n]; // 이진 패턴을 표현할 배열

        printPattern(0, k);

    }

    // printPattern는 x위치에서 1의 표시할 수 있는지 검사하고 표시.
    static void printPattern(int x, int k) {
        if (k == 0) { // 표시해야할 1이 없다면 출력
            for (int i = 0; i < n; i++) {
                System.out.print(ary[i]);
            }
            System.out.println();
        } else {
            for (int j = x; j < n; j++) {

                ary[j] = 1; // 아직 1을 표시할 수 있는 기회가 남아있다면 j번째 위치에 1을 표시
                printPattern(j + 1, k - 1); // j위치에 표시하고 j+1위치에서 1을 출력할 수 있는지 검사, k값은 1을 한번 출력했으니 -1;
                ary[j] = 0; // j위치에서 1을 표시할 수 있는지 모두 검사하였으면, j위치의 값은 0
            }
        }
    }
}

위의 문제는 "두 정수 n, k를 입력받아 k개의 1을 가진 n자리 이진 패턴을 출력하는 프로그램"을 작성하는 문제이다. 그냥 설명만 봐서는 좀 난해하다. 예를들어, n=4, k=2라면, 2개의 1을 가진 4자리 이진패턴을 출력하는 문제이다.

 

위의 결과는 1100,1010,1001,0110,0101,0011가 된다. 결국 k는 표시되는 1의 개수이고 n은 이진패턴이 출력되는 정수의 길이를 의미한다.

 

아이디어는 n의 각 위치에서 1을 출력할 수 있는지 모두 검사하는 것이다. 여기서 각 위치는 1100에서 1,1,0,0이 각 위치가 된다.

만약 첫번째 위치의 값이 0이면 1을 표시하고 다시 두번쨰 위치를 검사한다. 이런 방식은 재귀함수로 구현할 수 있다.

 

위의 모양은 우리가 자주사용하는 N중 for문에서도 같은 논리를 가진다.

  

      for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
          for(int k=0;k<3;k++){
            System.out.println(i+" "+j+" "+k);
          }
        }
      }
// 0 0 0
// 0 0 1
// 0 0 2
// 0 1 0
// 0 1 1
// 0 1 2
// 0 2 0
// 0 2 1
// 0 2 2
// 1 0 0
// 1 0 1
// .....

첫번째 for문은 2번쨰 for문이 끝날떄까지 기다린다. 두번째 for문은 3번째 for문이 끝날때까지 기다린다. 그리고 3번째 for문이 종료되면 2번째 for문을 j++하여 다시 3번째 for문이 끝날떄까지 기다리고, 2번째 for문이 모두 끝나면 첫번째 for문은 i++를 하여 위의 과정을 다시 반복한다.

 

여기서 중요한 점은 N+1 for문이 종료 되기전까지는 N for문의 값은 변하지 않는다. 결과에서 000,001,002,010,011,012....첫번째 for문은 두번쨰 for문이 끝날때까지 i값이 절대 변하지 않는다. 두번째 for문 역시 3번쨰 for문이 종료되기 전까지 j값은 변하지 않는다.

 

이와 같은 논리로 Tobin 코드는 동작한다. N번쨰 재귀함수(N번째 for문)는 N+1번째 재귀함수(N+1번째 for문)이 종료되기 전까지 그 상태를 그대로 유지한다. 여기서 중요한 점은, 각각의 재귀함수는 자신만의 상태를 가진다. 여기서는 static변수를 제외하고 함수에서 사용되는 모든 변수를 의미한다.

 

좀 더 설명은 하면 첫번째 자리에 1을 출력하고, 다시 재귀함수를 호출한다(N+1번째 for문 실행). 여기서 인자로 x+1, k-1을 넘겨주는데 x+1은 두번째 자리를 의미하고 k-1은 1은 한번 출력했으니 1을 출력할 수 있는 횟수가 된다. 항상 재귀함수가 시작되면 기저조건을 검사해준다. 즉 재귀함수의 탈출조건. 만약 k==0이라면, 즉 1을 출력할 수 있는 기회가 없다면 더이상 검사할 필요가 없다. 현재 상태를 출력한다.

 

좀 더 설명을 하자면 먼저 재귀함수의 인자는 x,k를 받는다. 이 값은 넘어오기 전 x+1,k-1인 값인데, x+1은 두번쨰 자리, 세번쨰 자리...n번째 자리의 수를 의미하고 k-1은 1을 한번 출력했으니 -1된 상태로 값이 전달된다.

 

이후 바로 기저조건을 확인한다(탈출조건). 만약 k=0이 아니라면, 배열의 현재 위치에 1을 출력하고 다음 자리에서의 경우를 검사한다. (printPatter(x-1,k-1)). 만약 k=0이라면 현재 상태를 출력한다. 여기서 중요한 점은 출력하고 종료된 재귀함수가 호출되었던 위치로 돌아간다. 당연한 말이다. 예를 들어 5번째 라인에서 f1이라는 함수를 실행시키고 해당 함수가 종료되면 다시 그 함수가 호출된 곳으로 간다. 그 다음 코드를 실행하기 위해서.

 

어쨋든 호출된 재귀함수가 종료되고 그 함수를 호출했던 곳으로 돌아가게 되면 즉3번째 for문이 종료되면 다시 2번째 for문으로 이동하게 된다. 여기서 ary[j]=0을 해주는데, 이는 j번째의 자리수에서 1을 출력할 수 있는 경우를 모두 출력했기 때문이다. 즉 해볼만큼 다 해보았다는 것. 이후 j++이 되면 그 다음 자리에서 검사를 하게된다.

 

이 문제는 N중 for문이 어떻게 동작하는지, 또 각 n for문에서의 상태(변수)는 N+1,N+2,N+3...for문이 실행되는데 그 값을 계속 유지한다는 것만 이해한다면 충분히 해결할 수 있는 문제이다.