[알고리즘] 재귀 알고리즘 접근 방법, 선언형 프로그래밍(Declarative Programming)

하노이 탑 예제

• 재귀 알고리즘의 대표 문제인 하노이 탑 문제이다.
• 1번에 있는 원판을 3번으로 옮겨야 하는데 아래와 같은 조건이 있다.
  • 한 번의 하나의 원판만 이동시킬 수 있다.
  • 항상 자기보다 큰 원판 위에만 이동할 수 있다.
• 이 문제를 재귀를 이용해 풀면 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int cnt = 0;

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

        hanoi(n, 1, 3, 2);

        System.out.println(cnt + "\n" + sb);
    }

    public static int hanoi(int n, int start, int end, int mid) {

        cnt++;

        if (n == 1) {
            sb.append(start + " " + end + "\n");
        }

        else {
            hanoi(n-1, start, mid, end);
            sb.append(start + " " + end + "\n");
            hanoi(n-1, mid, end, start);
        }

        return cnt;
    }
}

• 처음 원판이 쌓여있는 장대를 start, 그리고 모두 이동시켜야 할 장대를 end라고 정의하고 중간의 이동시키기 위해 거쳐가는 장대를 mid라고 정의한다.
• 그리고 재귀 탐색을 하게 되는데 이것을 이해하기 위해 로그를 찍어서 따라가면 대략 이런 식으로 나온다.
  • n = 3 이라고 정의
  • 처음 hanoi 메서드를 호출하면 start = 1, end = 3, mid = 2이다.
  • 그리고 hanoi(2, 1, 2, 3)을 호출한다. (첫번째 재귀)
  • 그리고 hanoi(1, 1, 3, 2)를 호출한다. (두번째 재귀)
  • 이 때 n == 1이므로 1 3 을 출력하고 첫번째 재귀로 돌아가서 else문 두번째줄을 타며 1 2 를 출력한다.
• 그런데 n = 3 인 경우도 이렇게 복잡한데 그 외는 로그를 찍어서 따라가기조차 버겁고 이해하려고 하다보면 도대체 이런 발상을 어떻게 하고 어떻게 식을 만들어내는지 신기하기만 하다.

재귀 접근 방법

명령형 프로그래밍과 선언형 프로그래밍

• 언어적인 스타일로만 본다면 Java가 명령형, SQL이 선언형이라고 볼 수 있으나 코딩 스타일에 따라 달라질 수 있다.
• 명령형 프로그래밍은 알고리즘을 명시하고 목표는 명시하지 않는다.
  • 예시) A로 가서 B를 호출하고 C로 가라.
• 선언형 프로그래밍은 목표를 명시하고 알고리즘은 명시하지 않는다.
  • 예시) 출발지는 A이고 목적지는 서울이며 이동수단은 자동차이고 시속 30km로 운행한다.
• 선언형 프로그래밍은 문제를 정의하고 이를 재귀적으로 분석하는 것이 필요하다.
  • 종료 조건, 문제 정의가 중요!
• 재귀는 선언형 프로그래밍(Declarative Programming) 을 이용하는데, 목표와 중간과정에서 필요한 요소들만 명시하고 어떻게 해야하는가는 굳이 명시하지 않는다.

피보나치 수열 예제

• 그러면 선언형 프로그래밍의 접근 방식으로 피보나치 수열을 나타내보자.
• 피보나치 수열이란 어떤 수열의 항이 앞의 두 항의 합과 같은 수열이다.
  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ....
• N = 7 이라고 가정하고 이 때 문제의 종료조건과 정의를 구하면,
  • 종료조건 : N < 3 인 경우(1, 2번 항)는 1을 return한다.
  • 문제 정의 : 피보나치 수열은 앞의 두 항의 합이 현재 항의 값이 된다.
    • fibo(N-2) + fibo(N-1);
• 이것을 코드로 나타내면 아래와 같다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 1; i <= N; i++) {
            System.out.println(fibo(i));
        }
    }
    public static int fibo(int N) {

        // 종료 조건
        if (N < 3) return 1;

        // 문제 정의
        else {
            return fibo(N-2) + fibo(N-1);
        }
    }
}

연산자 끼워넣기 예제

문제링크

• 연산자 끼워넣기는 백트래킹을 이용하는 문제로,
• 주어진 수들과 주어진 연산자를 이용해 만들 수 있는 모든 식을 만든 후 가장 큰 값과 작은 값을 출력하는 문제이다.
• 이 문제 또한 하나하나 상황을 구상해서 재귀식을 만들려고 하면 매우 어려운데 선언형 프로그래밍 방식을 적용해서 목표만 명시해주면 신기하게 풀리는 것을 볼 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] numbers, operator;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;

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

        numbers = new int[N];       // 수를 담을 배열
        operator = new int[4];      // 연산자를 담을 배열

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < operator.length; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }

        dfs(numbers[0], 1);

        System.out.println(max + "\n" + min);
    }

    public static void dfs(int num, int depth) {
        // 종료 조건
        if (depth == N) {
            min = Math.min(min, num);
            max = Math.max(max, num);
            return;
        }

        // 문제 정의
        for (int i = 0; i < 4; i++) {

            // 연산자가 존재한다면
            if (operator[i] > 0) {

                // 연산자의 개수만큼만 연산하기 위해 해당 연산자의 개수를 마이너스한다.
                operator[i]--;

                switch(i) {
                    case 0: dfs(num + numbers[depth], depth+1); break;
                    case 1: dfs(num - numbers[depth], depth+1); break;
                    case 2: dfs(num * numbers[depth], depth+1); break;
                    case 3: dfs(num / numbers[depth], depth+1); break;
                }

                // 모든 케이스가 끝나면 다른 연산을 위해 연산자의 개수를 복구한다.
                operator[i]++;
            }
        }
    }
}

• 백트래킹 문제가 늘 그렇듯이 depth가 특정 수가 될 때 종료하게 된다. 이 문제에서는 현재 항까지의 계산 결과와 다음 항을 연산하는 것이므로(1 2 3 4 라면 1과 2 연산 그리고 그 결과로 3과 연산, 그 결과로 4와 연산) depth == N 이 될 때를 종료조건으로 설정하고 종료되기 전 최솟값과 최댓값을 저장하도록 하였다.
• 그리고 문제 정의!
  • 각 연산자는 operator = [+, -, *, / ] 이다.
    • operator[i]
  • 연산자의 개수만큼 연산해야 한다.
    • operator--;
  • 연산 조건에 따라 연산한다.
    • switch문
  • 모든 연산이 끝나면 다른 연산을 위해 연산자 개수를 복구한다.
    • operator++;
• 저 재귀식이 순열로 풀어진다는 것은 또 학습을 해야 되는 부분이고 많은 문제를 접해서 익숙해지는 게 중요한 것 같다.
• 하지만 재귀를 하나하나 따라가면서 어떤 식으로 동작하는지를 보고 거꾸로 그러한 식을 만들기 위해서 재귀를 하나하나 구상하기보다 종료조건과 문제의 정의라는 선언적 프로그래밍 방식으로 접근해보는 것도 좋을 것 같다는 생각이 들었다.