코테연습 - 재귀

오늘은 코딩테스트 재귀 알고리즘에 대해 알아볼것이다.

 

우선 재귀가 무엇인가 부터 알아야한다.

재귀란 함수가 자기 자신을 호출하는 것이다. 말그대로의 뜻이기 때문에 크게 더 설명할 부분이 없다.

쉬운 예시로 팩토리얼, 피보나치 수열등의 문제를 재귀로 풀 수 있다.

 

아래의 코드는 간단한 재귀 함수의 예시다.

void recur(int n) {
    if (n == 0) return; // 기저 조건 (종료 조건)
    recur(n - 1);       // 자기 자신 호출
}

재귀에는 반드시 기저조건(탈출, 종료 조건)이 필요한데 기저조건이 존재하지 않는다면 재귀함수를 무한히 호출하기 때문에 스택 오버플로우가 발생한다. 또한 재귀는 스택과 유사한 구조를 가지고 있는데 n = 3인 경우 위의 함수를 실행한다면

recur(3)
 └ recur(2)
     └ recur(1)
         └ recur(0)

이러한 형태로 스택처럼 3, 2, 1, 0 순으로 쌓인다. 그 후 필요한 값을 반환해 0, 1, 2, 3 순으로 LIFO(후입선출)순으로 가장 나중에 호출된 함수부터 종료되고 이전 상태로 되돌아간다.

 

이론상으로 재귀로 풀 수 있는 문제는 모두 반복문으로 해결 가능하긴 하지만 백트래킹, 분할 정복등의 유형은 반복문 만으로 구현하기 어려울 수 있으므로 재귀로 푸는게 낫다. 하지만 구현의 난이도가 높지 않다면 반복문이 재귀보다 훨씬 좋은 선택지가 될것이다. 왜냐하면 시간복잡도 면에서 재귀함수보다 반복문이 훨씬 낫기 때문이다.

 

그러면 이제 재귀함수를 사용하는게 더 유리한 부분을 알아보자 주로 백트래킹과 분할정복 유형이 있는데 백트래킹은 알고리즘을 따로 분류할것이기 때문에 이번 글에서 다루지않고 분할정복만 설명하겠다.

 

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

전형적인 분할정복 문제인 색종이 만들기 문제다.

색종이를 4등분 시키면서 같은색의 색종이만 남을때까지 분할시키는 문제다.

 

일단 재귀문제를 풀때 가장 중요한점인 기저조건이다. 이 문제는 색종이가 같지않으면 다시 4등분하는것이기 때문에 해당 영역의 색종이가 같은색으로 이뤄져있다면 더 이상 분할시킬 필요가 없다. 그러므로 기저 조건은 같은색의 색종이로 이루어져있으면 종료일것이다.

그 다음으로 기저조건을 찾았으니 재귀가 어떻게 진행될것인지 생각해야 할것이다. 답은 간단하다 기저조건과 다르다면 단순히 다시 4등분을 하면 된다. 그러면 이제 풀이법을 찾았으니 코드를 봐보자

public class S_2_2630 {
    public static int N;
    public static int[][] arr;
    public static int[] count = new int[2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recursion(0, 0, N);
        for (int i : count) {
            System.out.println(i);
        }
    }

    public static void recursion(int x, int y, int size) {
    //기저조건
        if (isSame(x, y, size)) {
            count[arr[x][y]]++;
            return;
        }
        //재귀
        int newSize = size / 2;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                recursion(x + i * newSize, y + j * newSize, newSize);
            }
        }

    }

//같은 색으로 이뤄져있는지 검사
    public static boolean isSame(int x, int y, int size) {
        int num = arr[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != num) {
                    return false;
                }
            }
        }

        return true;
    }
}

이런식으로 같은 색으로 이뤄진 색종이인지 검사하고 아니면 다시 4등분을 진행하는것이다. 그 후 4등분한 색종이도 같은색이 아니면 다시 4등분을 진행한다. 근데 왜 재귀에서 2중 for문을 쓰냐면 사분면을 나누기 위함이다. 4등분하고나서 그 안에서 4개의 색종이가 생기니 사분면 4개에 따른 4개의 재귀를 호출하는 것이다.

 

이러한 문제를 반복문으로 풀 수 있을까? 이론상으로는 가능하지만 적어도 나는 구현하는데 진짜 한세월을 보낼것 같다. 이러한 경우는 반복문보다 재귀로 푸는게 훨씬 유리할 것이다.