[Algorithm] 재귀 알고리즘 정리(+ 추천 문제 list)

알고리즘

[Algorithm] 재귀 알고리즘 정리(+ 추천 문제 list)

Dobby-HJ 2023. 3. 13. 03:42

예비 대학원생을 지망하는 Dobby 최한준입니다.

최근에 Python 입문 스터디를 들어가서 재활 중에 있습니다. 그리고 이참에 전체 알고리즘을 한 번 크게 정리해 보려 합니다.

이번 주차에는 재귀 Recursive 관련해서 한 주 동안 7문제를 푸는 연습을 진행했고, 추가적으로 몇 문제 더 풀어보았습니다.

그러면서 재귀 관련해서 제가 어떻게 생각하고 있는지 백준 닦닦이가 한번 설명해 보겠습니다.

0. 들어가며

저는 보통 알고리즘을 크게 2가지로 분류하는데요. 찐 알고리즘/찐 알고리즘이 아닌 알고리즘입니다.

이게 무슨 헛소리냐구요? 조금 더 설명해보겠습니다.

재귀 알고리즘하면 어떤게 떠오르시나요?

재귀 알고리즘(함수) 하면 보통 "자기 자신을 호출하는 알고리즘(함수)" 정도로 생각날 거라 생각합니다. 그렇다면 어떻게 구현할까요? 브루트 포스 알고리즘은 어떤가요? 어떻게 구현하나요?

다른 예시로

다익스트라 알고리즘하면 어떤게 떠오르시나요? 구현을 어떻게 하면 될까요?

위 2개에서 저는 사실 "다름"을 느낍니다. 사실 남들에게는 적용되지 않을 수 있으나, 재귀, 브루트포스처럼 특별히 정해지지는 않았지만, 그 개념적인 맥락이 적용되어 구현되어지는 알고리즘이 있는가 하는 반면, 다익스트라 알고리즘처럼 규격화된 틀이 있고, 입출력을 해당 알고리즘에 잘 녹여내야 하는 알고리즘도 있는 것이죠.

지금부터 설명할 "재귀"알고리즘은 이 개념적인 맥락이 문제를 푸는데 굉장히 중요하다고 생각합니다. 저는 여기에 초점을 맞춰서 설명을 해보려고 합니다.

프로그래밍 언어가 개발되기 이전에는 재귀라는 개념이 어디서 사용되었을까요? 바로 수학입니다. 수학에서는 쉽게 재귀 함수를 사용하는 것을 볼 수 있습니다.
수학에서는 왜 재귀함수를 사용했을까요? 고등학교 때 배웠었던 것 같은데, 바로 수학적 귀납법입니다.

수학적 귀납법

조금 다르게는 다음과 같이 수학적으로도 작성가능할 듯 합니다.

$$\begin{align} F(0) &= 0 \\ F(1) &= 1\\ F(N) &= F(N-1) + F(N-2) \end{align}$$

수학에서는 우리가 사용하는 재귀하는 것보다 더 넓은 의미로 사용했습니다. 수학에서는 "반복"이라는 것을 의미하기 위해 재귀라는 것을 이용했다고 생각합니다. 이로인해 컴퓨터에서도 반복의 의미로 재귀 함수를 사용할 수 있고, 그 역도 성립합니다. 이에 영향을 받아 만들어진 LISP나 HASKELL 같은 함수형 프로그래밍 언어도 있습니다.(사실 맥락은 다른데 끼워넣었습니다 ^^7)

앞서 언급했던 것중에 재귀함수를 이용해 반복을 의미할 수 있다는 말이 컴퓨터에서는 반복문을 재귀함수로 표현할 수 있다는 것과 동일한 말입니다. 즉, 반복문을 재귀함수로 표현할 수 있고, 그 역도 가능합니다. 일반적으로 우리는 명령형 프로그래밍 언어를 이용해 재귀함수를 구현해 사용하게 됩니다. 그렇게 되면 메모리에 함수 호출 스택이 쌓이게 되고, 퍼포먼스 측면에서는 반복문이 일부 더 나을 수 있습니다. 꼬리재귀(Tail Recursion)와 같은 특별한 구현이 되어있다면 반복문과 큰 성능차이는 없지만, 이러한 배경도 있다는 것을 알려드리고 싶었습니다.

지금까지 대략적으로 제가 알고있는 재귀 관련된 지식들을 알려드렸습니다. 이제 우리가 코테 혹은 대회를 위해 공부해야할 재귀 알고리즘에 대해 들어가보겠습니다.

1. 재귀란

재귀로 문제를 해결하겠다고 말하는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 뜻이고, 쉽게 수학적 귀납법으로 문제를 해결하겠다고 생각하면 편합니다.

$$\begin{align} F(0) &= 0 \\ F(1) &= 1\\ F(N) &= F(N-1) + F(N-2) \end{align}$$

아까 봤던 피보나치 입니다.

우리는 문제를 풀 때 어떤것을 얻어내야 하냐면 마지막 $ F(N) = F(N-1) + F(N-2) $ 이 식을 얻어내야 합니다. 즉, 곧바로 결론을 알아내려고 하는 것이 아니라 특정 규칙성 혹은 일반화 과정을 얻어야 결론을 얻을 수 있다는 생각의 전환이 일어나야합니다.

기존의 생각의 흐름과는 다른 방향성으로 인해, 처음 재귀를 접하게 된다면 이러한 부분에서 복잡하다고 흔히 느낍니다.

2. 재귀 알고리즘인지 파악하는 방법.

수학적 귀납법 구조임을 알아차리기.
- 활성화한 재귀 함수가 일반적인 상황에서 잘 작동하고, 기저 사례(Base Condition)에서도 잘 작동하면 일반적으로 잘 동작합니다.
- 위 과정이 익숙하지 않다면, 좌변에 $f(x)$를 우변에는 함수 $f$를 넣어놓고 끼워맞춰 보는게 가장 빠릅니다.
- 어렵게 생각하지 말고 어거지로 한번 끼워보세요. 그렇다면 어려운 수학적 귀납법이라는 말이 아니더라도 재귀 알고리즘을 해결할 수 있습니다.
큰 문제가 작은 문제들의 정답들을 이용해 해결 가능한 경우.
- 사실 아마 대부분의 재귀 알고리즘은 "재귀" 알고리즘이 포커스가 아니라 DFS, DP(Top-Down), 분할정복과 같은 알고리즘을 구현할 때 "재귀"알고리즘이 필요한 경우라 생각됩니다.
- 그래서 저는 사실 DFS, DP, 분할정복으로 해결하려기 보다는 상태공간 탐색 DFS라는 전체를 포함하는 개념으로 생각하여 문제를 해결합니다.

3. 재귀 알고리즘을 구현하는 방법

우리는 특정 문제를 만났을 때 이제 "재귀" 알고리즘으로 해결된다는 것을 수학적 귀납법을 통해 알아냈다고 가정해보겠습니다. 그러면 우리가 이제 해야하는 일은 "구현"하는 것입니다. 재귀 알고리즘을 "구현"할 때 주의 해야하는 것은 다음과 같습니다.

초기 조건(Initalize Condition)
일반항 (General Terms)
기저조건 (Base Condition)

(여기서 초기 조건은 제가 만든 용어입니다. 다른 곳에서 사용하면 큰일 날 수도...)

기저조건(Base Condition)이 옳다면 상태공간 상에서 리프노드(최말단 노드)의 정당성을 부여하고, 일반항(General Term)이 옳다면 리프노드의 정당성이 확보 되었을 경우, 모든 부모노드들이 정당성을 확보한다는 말과 동일합니다. 이로 인해 이 2가지를 만족하면 전체 상태트리는 정상적으로 동작하게 됩니다.

다만 우리는 문제를 풀어야합니다. 즉 처음에 이 함수를 어떻게 호출해야하는가?에 대해서도 고민을 해야합니다.

이 3가지 맥락을 이용해 아래 문제들을 살펴보겠습니다.

저는 각 알고리즘의 문제들은 BOJ의 단계별로 풀어보기를 모두 풀어보고 필요하다면 알고리즘 분류를 이용해 찾아보는 편입니다.

4. 추천 문제 List

1. BOJ 10872 팩토리얼

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

10872번: 팩토리얼

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

www.acmicpc.net

어렵지 않게 일반항과 기저 조건을 알 수 있습니다.

팩토리얼의 정의상 $1! = 1 \text{and} 0! = 0$이므로, 다음 2개의 식이 기저조건이 되고, 일반항은 다음과 같습니다.

$$f(N) = N * f(N-1)$$

Python으로 작성한 코드는 다음과 같습니다.

import sys

N = int(sys.stdin.readline())

def r(i):
    if i == 1 or i == 0:
        return 1
    else:
        return i * r(i - 1);

print(r(N))

2. BOJ 10870번 피보나치 수 5

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

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

앞서 보았던 fibonacci 예시와 동일합니다.

$$\begin{align} F(0) &= 0 \\ F(1) &= 1\\ F(N) &= F(N-1) + F(N-2) \end{align}$$

여기서 추가된 건 초기 조건(Initalized Condition)으로 우리는 입력으로 받은 $n$값을 함수 $f$에 넣어주면 원하는 답을 얻을 수 있습니다.

3. BOJ 25501번 재귀의 귀재

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

25501번: 재귀의 귀재

각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다.

www.acmicpc.net

예시 코드는 파이썬으로 동일하게 구현한 뒤, 재귀 호출하는 함수 앞쪽에 전역변수 cnt를 두어 재귀 호출 갯수를 세어 문제를 해결하면 됩니다.
재귀에 익숙해지기 위해 내부 코드 동작에 대해서 공부해보시면 좋을 듯 합니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
cnt = None
S = None
def recursion(s, l, r):
    global cnt
    cnt += 1
    if l >= r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l+1, r-1)

def isPalindrome(s):
    global cnt 
    cnt = 0
    return recursion(s, 0, len(s)-1)


def set_variable():
    global N, cnt
    N = get_input()

def solution():
    global N, cnt, S
    for _ in range(N):
        S = sys.stdin.readline().rstrip()
        print(isPalindrome(S), cnt)

if __name__ == "__main__":
    set_variable()
    solution()

(여담이지만 저는 다음과 같은 code 규격을 사용하고 있습니다. 굉장히 코드가 난잡해지고 전역변수도 많이 쓰지만, 이미 익숙해져버렸네요...)

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

def set_variable():


def solution():


if __name__ == "__main__":
    set_variable()
    solution()

4. BOJ 24060 알고리즘 수업 - 병합 정렬 1

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

24060번: 알고리즘 수업 - 병합 정렬 1

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

www.acmicpc.net

합병 정렬의 Pseudo Code를 Python으로 구현한 뒤, 결과를 원본 배열 A에 저장할 때 저장횟수를 세어 문제의 조건에 맞게 출력하는 방향으로 문제를 해결했습니다.
재귀에 익숙해지기 위해 내부 코드 동작에 대해서 공부해보시면 좋을 듯 합니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, K = None, None
arr = None
cnt = None

def merge(A, l, mid, r):
    global K, cnt
    i, j = l, mid + 1 # python은 append로 구현하면 필요없음.
    tmp = []
    while i <= mid and j <= r:
        if A[i] <= A[j]:
            tmp.append(A[i])
            i = i + 1
        else:
            tmp.append(A[j])
            j = j + 1

    while i <= mid:
        tmp.append(A[i])
        i += 1
    while j <= r:
        tmp.append(A[j])
        j = j + 1

    i= l
    while i <= r:
        cnt += 1
        A[i] = tmp[i-l]
        if cnt == K:
            print(A[i])
            sys.exit(0)
        i += 1

def merge_sort(A, l, r):
    if l < r:
        mid = (l + r) // 2
        merge_sort(A, l, mid)
        merge_sort(A, mid + 1, r)
        merge(A, l, mid, r) #  병합


def set_variable():
    global N, K, arr, cnt
    cnt = 0
    N, K = get_line()
    arr = list(get_line())

def solution():
    global N, K, arr, cnt
    merge_sort(arr, 0, len(arr)-1)
    print(-1)

if __name__ == "__main__":
    set_variable()
    solution()

5. BOJ 2447번 별 찍기 - 10

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

2447번: 별 찍기 - 10

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이

www.acmicpc.net

수식적으로 설명하기는 어려우나 사각형의 크기가 3배수로 커지고 작아지고, 같은 규격 규칙이 반복되는 것을 관찰할 수 있습니다.
3x3 규격에 1~9까지 있다고하면 5번만 비어있는 형태이므로, 1~4, 6~9번의 사각형 모두 다시 호출되어 해당 사각형의 내부를 *로 채우도록으로 처리하도록 코드를 짜면 됩니다.

import sys

N = int(sys.stdin.readline())


def recursive_mapping(n, y, x):
    global b
    if n == 1:
        arr[y][x] = '*'
    else:
        for i in range(3):
            for j in range(3):
                if i != 1 or j != 1:
                    recursive_mapping(n // 3, y + (n // 3) * i, x + (n // 3) * j)


arr = [([' '] * N) for _ in range(N)]
recursive_mapping(N, 0, 0)
for i in arr:
    print(*i, sep='')

위 코드는 전체 배열이 공백으로 된 2차원 배열에 *을 채우는 형태로 구현되었습니다.
다르게 파이썬은 특정 크기의 배열을 재귀 level 상 자식 level의 재귀 배열의 return 결과를 이용해 구현하면 더 빠르게 실행됩니다.
2000ms -> 48ms

import sys

N = int(sys.stdin.readline())


def star(n):
    if n == 1:
        return ['*']
    n = n // 3
    a = star(n)
    top = [i * 3 for i in a]
    middle = [i + ' ' * n + i for i in a]
    return top + middle + top


mystar = '\n'.join(star(N))
print(mystar)

6. BOJ 11729 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

하노이 탑은 재귀에서 굉장히 유명한 문제입니다.
from(탑 옮기는 위치)에서 to(탑이 도착하는 위치)로 by(중간 과정)을 이용해 옮긴다면 다음과 같이 정의할 수 있습니다.
하노이 탑에서 최상단 탑을 옮기는 건 그냥 옮길 수 있습니다. (from -> to)
하노이 탑에서 여러 층의 탑을 옮기는 것은 조금 복잡합니다. 하지만 일반항은 쉽게 구할 수 있습니다.
from에서 K개의 탑을 to로 옮긴다면 다음과 같습니다.

from에서 K-1개의 탑을 by로 어떻게든 옮기고,
from에서 남은 1개를 to로 옮깁니다.
by에 있던 K-1개의 탑은 to로 옮기면 됩니다.

만약 10개를 옮기고 싶다면 먼저 9개를 by로 보낸 뒤에 10번째 칸을 to로 보내고 by에 있던 9개를 to로 보내면 됩니다.
여기서 헷갈리는 부분은 아마 K-1개를 어떻게는 by로 보내는 부분인데, 사실 by를 해당 재귀 시점의 from으로 생각하면 쉽게 납득할 수 있을거라 생각합니다.
코드는 다음과 같습니다.

import sys

N = int(sys.stdin.readline())

cnt = 0

def hanoi(n, st, mid, ed):
    global cnt
    cnt += 1
    if n == 1:
        print(f"{st} {ed}")
    else:
        hanoi(n - 1, st, ed, mid)
        print(f"{st} {ed}")
        hanoi(n - 1, mid, st, ed)


print((1 << N) - 1)
hanoi(N, 1, 2, 3)

7. BOJ 20164 홀수 홀릭 호석

개인적으로 좋아하는 류호석님의 문제입니다.

딱 코딩 테스트에서 낼법하게 내셔서 매번 연습하기 좋은 것 같습니다.

이 문제에서는 주어진 연산의 순서를 모두 지켜서 구현하면 됩니다.

다만 주의해야할 것은 재귀를 언제 해야하는가? 인데 문제에서 "새로운 수"로 생각한다의 부분에서 다시 한번더 재귀를 들어가면 됩니다.

또한 문제에서 최소값과 최대값 모두 물어봤으므로, 함수에서 둘 모두 return 하도록 구현하면 됩니다.

import sys
import math

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
def set_variable():
    global N 
    N = get_input()


def solution():
    def rec(num):
        cnt = 0
        for i in num:
            cnt += 1 if int(i) % 2 else 0
        if len(num) == 1:
            return cnt, cnt
        elif len(num) == 2:
            min_cnt, max_cnt  = rec(str(sum(map(int, num))))
            return cnt +  min_cnt, cnt + max_cnt
        else:
            min_cnt = math.inf
            max_cnt = 0
            for i in range(1, len(num) - 1):
                for j in range(i + 1, len(num)):
                    now_min, now_max = rec(str(sum(map(int, [num[:i], num[i:j], num[j:]]))))
                    min_cnt = min(min_cnt, now_min)
                    max_cnt = max(max_cnt, now_max)
            return cnt + min_cnt, cnt + max_cnt
    
    print(*rec(str(N)))
        
if __name__ == "__main__":
    set_variable()
    solution()

추가적으로 좋은 문제는

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

12919번: A와 B 2

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈

www.acmicpc.net

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

1662번: 압축

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이

www.acmicpc.net

(2023-3-14 추가)

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

9997번: 폰트

첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다.

www.acmicpc.net

처음 시도한 코드 모든 시행 횟수가 2^26으로 약 7천만 정도 되므로 대충 돌아갈거라고 생각함.

하지만 어림도 없지 바로 시간 초과

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
arr = None
cur_list = None
cnt = None

def set_variable():
    global N, arr, cur_list, cnt
    N = get_input()
    arr = [sys.stdin.readline().rstrip() for _ in range(N)]
    cur_list = []
    cnt = 0

def solution():
    global N, arr, cur_list, cnt
    def rec(pos):
        global N, arr, cur_list, cnt
        now_set = set()
        for i  in cur_list:
            for j in i:
                now_set.add(j)
        if len(now_set) == 26:
            cnt += 1
        if pos == N:
            return
        else:
            rec(pos+1)
            cur_list.append(arr[pos])
            rec(pos+1)
            cur_list.pop()
    
    rec(0)
    print(cnt)


if __name__ == "__main__":
    set_variable()
    solution()

그래서 bit masking + 필요없는 상수 컷팅

bit masking 기법도 상수 컷팅이지만, 더 의미 있다고 생각하는 것은

다음 코드 입니다.

if now_alphabet == full_alphabet:
    answer += 2 ** (N - pos)
    return

모든 노드를 탐색하기 전에 모든 알파벳을 다 모았다면 이후의 모든 남은 2^{K(N - pos) 단어 갯수 }만큼은 무조건 가능한 테스트 문장이 되므로 재귀 탐색 없이 $2^{N - pos}$로 계산함.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
alphabet_list = None
full_alphabet = None
answer = None
sum_all = None

def set_variable():
    global N, alphabet_list, full_alphabet, answer, sum_all
    N = get_input()
    full_alphabet = (1<<26) - 1
    def makedigit(s):
        ret_num = 0
        ret_list = [1 if alpha in s else 0 for alpha in 'abcdefghijklmnopqrstuvwxyz']
        for shift, num in enumerate(ret_list[::-1]): ret_num += num << shift
        return ret_num
    alphabet_list = [makedigit(sys.stdin.readline().rstrip()) for _ in range(N)]
    sum_all = 0
    for i in alphabet_list:
        sum_all |= i
    if sum_all != full_alphabet: 
        print(0)
        sys.exit(0)
    answer = 0


def solution():
    def rec(pos, now_alphabet):
        global N, alphabet_list, full_alphabet, answer
        if now_alphabet == full_alphabet:
            answer += 2 ** (N - pos)
            return
        if pos == N:return
        rec(pos + 1, now_alphabet | alphabet_list[pos])
        rec(pos + 1, now_alphabet)

    rec(0, 0)
    print(answer)      


if __name__ == "__main__":
    set_variable()
    solution()

등이 있습니다. (추가 예정)