재귀 알고리즘 문제 해결하기

재귀란

어떤 사건이 자기 자신을 사용하여 정의 될 때 재귀적(recursive)라고 합니다. 대표적인 예로 팩토리얼이 있습니다. (팩토리얼의 10!는 10x9!로 설명할 수 있다.)

재귀는 스택이다.

재귀 알고리즘이 어렵다고 느껴지는 이유 중 하나는 사람의 머리로 컴퓨터가 실행하는 재귀적 행동을 따라 갈 수 없기 때문입니다. 재귀 알고리즘을 보다 쉽게 상상하려면,

1. 같은 함수가 호출 되는 것이 아니라, 복사된 함수가 호출 된다고 생각합니다.
2. 함수의 호출을 상상 할때는 스택(stack)으로 합니다. 함수 호출의 원리는 결국 스택으로 진행됩니다. 함수가 호출되면 기존 함수 스택 위에 호출된 함수가 쌓이게 되고, 더 이상 쌓을 함수(스택)이 없게 되면 위에서부터 차례대로 실행하게 됩니다.  

재귀 알고리즘 문제 풀이 전략

재귀 알고리즘을 풀이 할 때는 아래 3가지를 생각해봅니다. 

(아래 팁은 T아카데미 [토크ON세미나] - 함수형 프로그래밍이란? 우명인님의 강좌에서 참고했습니다.)

1. 어떻게 풀이 할지가 아니라 무엇을 해야할지 생각합니다. 그리고 전체과정을 생각하는 것이 아니라, N번째에 해야하는 행동만을 집중적으로 생각합니다. (N-1번째 이하의 과정은 재귀적으로 해결합니다.)
2. 종료조건이 무엇인지 생각합니다. (가능한 종료조건을 제일 먼저 검사합니다.)
3. 반복이 진행 될 수록 종료조건에 수렴하는지 생각합니다.

백준 알고리즘 문제 1074번 Z

위의 풀이 전략을 이용해서 실제 알고리즘 문제를 풀어 보겠습니다. 문제는 백준 알고리즘 1074번문제 'Z'입니다. ☞ 문제 링크  

(문제와 코드에 대한 자세한 설명은 하지 않습니다.) 

일단 배열을 4등분하고,  4등분한 기준으로 1x1짜리 칸이 앞쪽 위치에 몇칸이 존재하는지를 모두 합하는 방식으로 구하기로 했습니다.

1. N번째에 무엇을 해야 할까? (핵심은 아래 내용을 이해 하는 것이 아니라, N번째에 무엇을 해야하는지 생각하는 것이고 제가 생각한 내용이 아래와 같다는 겁니다.) 



• 배열을 4등분을 합니다.

  0	1
  2	3

  
  배열을 4등분 할때 Z자 모양으로 각 위치를 0,1,2,3 번째 위치라고 생각합니다.

• 현재 좌표(r,c)를 기준으로 0,1,2,3중 좌표가 어떤 위치인지 계산합니다. ((2^N)/2 -1)이라는 기준값을 이용하여서 r이 기준값 이하이고, c가 기준값 이하 일경우는 위치가 0  / r이 기준값 이하이고, c가 기준 값보다 큰 경우는 위치가 1 / r이 기준값보다 크고, c가 기준값 이하일 경우는 위치가 2 / r이 기준값보다 크고 c도 기준값보다 큰 경우는 위치가 4가 됩니다.

• 위치(0,1,2,3) x (2^N / 2)^2를 계산하면 앞쪽 위치의 1x1배열이 몇개 있는지 계산 해 낼 수 있습니다.

• 이제 현재 위치를 기준으로 다시 4등분 하고 계산하기 앞서서 좌표를 재조정합니다. (첫번째 좌표가 0,0이 되고, 이를 기준으로 (r,c)도 재조정)

2. 종료조건이 무엇인가?
   N==0인경우
3. 반복할 수록 종료조건에 수렴하는가?
   N--; 과정을 진행한다.

아래 풀이 예제는 java로 되어 있습니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int r = sc.nextInt();
        int c = sc.nextInt();
        System.out.println(solution(N, r, c));
    }

    static int solution(int N, int r, int c) {
        int result = 0;
        // 종료조건
        if (N == 0) {
            return result;
        }
        //가운데 기준점 찾아내기
        int midPoint = (int) ((Math.pow(2, N) / 2) - 1);

        //Z를 기준으로 0,1,2,3 중 어디에 위치한건지 찾아내기
        int position;
        if (r <= midPoint && c <= midPoint) {
            position = 0;
        } else if (r <= midPoint) {
            position = 1;
        } else if (c <= midPoint) {
            position = 2;
        } else {
            position = 3;
        }

        //위치(position)을 기준으로 앞에 몇칸이 존재하는지 계산하고 result에 더한다.
        result += position * ((int) Math.pow(Math.pow(2, N - 1), 2));

        //좌표를 조정한다. (맨 처음칸이 0,0이 되도록)
        switch (position) {
            case 1:
                c = (c - (midPoint + 1));
                break;
            case 2:
                r = (r - (midPoint + 1));
                break;
            case 3:
                r = (r - (midPoint + 1));
                c = (c - (midPoint + 1));
                break;
        }

        //종료조건에 수렴하도록 N을 1씩 뺀다.
        N--;

        //재귀적으로 result값을 구한다.
        result += solution(N, r, c);

        return result;
    }
}