재귀 알고리즘

개념을 먼저 익힌 후에 백준 알고리즘을 푸는식으로 해야겠다. 맨땅에 헤딩식으로 하면 나는 잘 이해가 안되는 것 같다. 천천히 하더라도 깊이있게 해보자❗

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.

바로 예제로 가보도록 하자

팩토리얼 구하기

재귀의 예시로 팩토리얼이 있다.
n!(팩토리얼) 은 n * n-1 * n-2 * ... 이다.
이것을 그대로 코드로 표현하면 다음과 같다.

import java.util.Scanner;

public class Factorial {
    static int factorial(int n) {
        if(n > 0)
            return n * factorial(n - 1);
        else
            return 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n + "! = " + factorial(n));
    }
}

동작형식을 자세하게 보면 factorial(int n)은 n이 0보다 크면 n * factorial(n - 1) 를 호출하고 아니면 1을 반환한다.

풀어서 써보자.

예를 들어 n값에 3을 넣었다고 가정한다.

• n = 3
  • 3 * factorial(2);
  • 2 * factorial(1);
  • 1 * factorial(0);
  • return 1

이 순서로 들어가게 될텐데,

맨 마지막의 1부터 1 * 2 * 3 이 되는 것이다.
호출은 n = 3부터 시작했으니 정렬이 되면 3 * 2 * 1이 되게 된다.

이렇게 해서 3! 의 답인 6을 얻게된다.

내가 재귀를 볼때 막힘없이 봐야 이해가 쏙 되는것 같은 느낌 😂

한번에 안읽히면 머릿속에서 무한루프를 도는느낌이다.

항상 끝부터 쭉 나간다음 생각해 보는것이 이해가 잘된다❗

재귀 안썼을 때

static int factorial(int n) {
        int count = 1;

        for(int i = n; i > 0; i--) {
            count *= i;
        }

        return count;
    }

유클리드 호제법

최대공약수를 재귀로 구할 수 있다.

두 정수를 직사각형 두 변의 길이라고 가정하면 최대 공약수를 구하는 문제는 다음과 같아질 수 있다.

직사각형을 정사각형으로 완전히 채우고, 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하자

4와 22 의 최대 공약수를 구해보자고 가정하면

1. 22 x 4에서 4를 한변으로 하는 정사각형으로 분할한다.
2. 5개의 4 x 4 정사각형이 생기고 2 x 2 두개가 남는다.
3. 이렇게 더이상 나눌 수 없는 2 x 2 정사각형이 생겼으므로 2가 최대 공약수이다.

public class Euclid {
    static int solution(int x, int y) {
        if(y == 0) {
            return x;
        }

        return solution(y, x % y);
    }

    public static void main(String[] args) {
        int x = 22;
        int y = 4;
        System.out.println(solution(x, y));
    }
}

단순하게 해석하면 0일때까지 계속 solution 자기 자신을 호출하면서 맨 마지막에 남은 x를 돌려주는 것이다.

재귀 안썼을 때

static int gcd2(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

배열 모든 요소의 최대 공약수

public class EucArray {

    static int euc(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    static int eucArray(int[] arr, int index, int length) {
        if(length == 1) {
            return arr[index];
        }

        if(length == 2) {
            return euc(arr[index], arr[index + 1]);
        }

        return euc(arr[index], eucArray(arr, index + 1, length - 1));
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 12, 15};
        System.out.println(eucArray(arr, 0, arr.length));
    }
}

막상 풀어보니까 이렇게 복잡한거는 재귀보다는 다른 방법이 나아보이는....

그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
단어 그대로 번역하자면 탐욕법이다.
이 부분에서 탐욕적이라 함은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이다.
이 알고리즘은 매 순간 가장 좋아 보이는 것만 선택하고, 그 선택이 나중에 어떤 영향을 미치는지에 대해서는 고려하지 않는다.

거스름돈을 예시로 살펴보자
당신은 음식점의 계산을 도와주는 점원이 되었다고 가정하자.
500원, 100원, 50원, 10원짜리 동전은 무한히 존재한다. 손님에게 거슬러줘야 하는 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구해라
(단, 거슬러줘야 할 돈 N은 항상 10의 배수이다.)

이럴때는 단순하게 가장 가격이 큰 동전 부터 돈을 거슬러 주는 것이다.
이렇게 되면 N원으로 설정된 가격을 금방 차감시켜 0원으로 만들기 적합하다.

coin.py

n = 1260 # 거슬러줘야할 가격
count = 0 # 코인의 개수

# 화폐 단위가 큰 것부터 차례로 거슬러준다.
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 원래 가격을 코인값으로 나눈 몫만큼 동전으로 추가해줌
    n %= coin

print(count)

화폐의 종류가 K개 라고 할때, 위 소스의 시간복잡도는 BigO 표기법으로 O(K)이다. 시간복잡도에서는 총 화폐인 N을 찾을 수 없다.
그래서 이 알고리즘은 동전의 종류에만 영향을 받지 거슬러 줘야하는 금액에는 초점이 맞춰지지 않는다.

알고리즘 문제 유형을 바로 파악하기 어렵다면, 그리디 알고리즘을 의심해 볼 수 있다.

그리디 알고리즘의 예제를 많이 풀어봐야겠다.