학교에서 제공하는 여름방학 코딩 테스트 대비 캠프 with 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석에 수록된 문제 풀이 및 강의 정리 내용입니다.

재귀(Recursion) in Coding Test

재귀함수는 자기 자신을 직간접적으로 호출하는 함수를 의미한다. 이를 쉽게 이야기하면 어떤 함수 f안에 동일함 함수 f를 다시 이용하는 경우이다. "피보나치 수열" 및 "1부터 N까지 자연수의 합 계산" 은 재귀함수를 활용하는 대표적인 예이다. 이 둘을 for문을 사용하여 구하는 것 보단 재귀로 구하게 되면 코드를 깔끔하게 짤 수 있다.

재귀 함수 사용이 어렵다면 재귀트리를 먼저 그려보자!

재귀 함수 사용 시 주의 사항

재귀를 사용할 때는 가장 먼저 함수의 정의와 함수가 받는 인자의 의미를 명확하게 해야한다. 그 후에 재귀를 통해 함수를 반복해야만 실수를 방지 할 수 있다. 두 번째로는 종료 조건을 지극히 당연한 걸로 둬야 하는데 그래야만 언제 재귀를 빠져나가야 하는지 한 눈에 알 수 있기 때문이다. 마지막으로는 재귀함수에서 빠져나가 다시 돌아가는 경우에는 원래 상태(재귀 함수에 들어가기 전 상태)로 다시 돌아가야 한다 그렇지 않으면 재귀함수 이후에 실행되는 코드에 Side Effect를 불러일으킬 수 있기 때문이다. 이를 쉽게 이해하기 위해서는 여러 선택지를 연속해서 고를 때 하나의 선택을 한 후에는 다시 처음 선택했을 때와 동일한 환경으로 돌아와야만 다음 선택을 진행할 때 공정해짐을 떠올리면 된다.

재귀함수를 사용한 Backtracking

1. K개 중 하나를 N번 선택하기

n이 주어졌을 경우 만들 수 있는 n자리의 모든 2진수를 증가하는 순서대로 출력하는 경우를 생각해보자. 만약 n이 2인경우에는 00, 01, 10, 11 순서로 출력해야 한다. 밑에 이미지와 같이 이 첫 번째 자리 부터 n번 째 자리 까지 0또는 1 값을 넣어주는 행위를 n번 반복하는 방식으로 문제를 접근해보자

문제

1이상 K이하의 숫자를 하나 고르는 행위를 N번 반복하여 나올 수 있는 모든 서로 다른 순서쌍을 구해주는 프로그램을 작성해보세요.

풀이

k, n = map(int, input().split())
#k이하의 수로 이루어진 n자리수가 되는 모든 경우의 수 1부터 출력

arr = [] #선택한 숫자를 담을 리스
#cur_num : 현재 가리키는 곳이 앞에서 부터 몇 번째 자리 수 인지
def choose(cur_num):  #cur_num번째 위치에 k이하의 숫 중 하나를 선택하는 함수
    if cur_num == n+1: #cur_num이 n보다 클 경우 종료
        for elem in arr:
            print(elem, end=' ')
        print()
        return
    for i in range(1, k+1):
        arr.append(i)
        choose(cur_num+1) #재귀 호출
        arr.pop() #원래 상태로 다시 돌려줌
        
    # for문을 사용하지 않을 경우(k가 3일 경우 예)
    # arr.append(1)
    # solve(cur_num+1)
    # arr.pop()
    # 
    # arr.append(2)
    # solve(cur_num+1)
    # arr.pop()
    # 
    # arr.append(3)
    # solve(cur_num+1)
    # arr.pop()

    return
#cur_num 1부터 시작하므로 인자로 1을 넘겨
choose(1)

• choose(cur_num)이라는 함수 작성 시 주석으로 함수의 정의를 먼저 명확하게 한다.
• 출력 양식이 오름 차순이므로 for문을 사용하여 해당 자리에 입력할 수를 증가시킨다.
• cur_num을 증가시켜 다음 자리 수에 값을 넣어주기 위해 재귀 호출
• append 후 다시 원래 상태로 돌아가기 위해 pop()을 진행한다.

2. 특정 조건을 추가한 K개 중 하나를 N번 선택하기(Conditional)

단순히 k개중 하나를 n번 선택하는 것이 아닌 조건이 붙는다면(ex 1은 연속할 수 없다.) 종료 조건에 재귀 함수가 도달 했을 때 주어진 조건에 부합하는지 확인해도 되지만 애초에 주어진 조건을 값을 선택할 때 확인한다면 재귀트리의 가지(경우의 수)를 줄일 수 있어 효율성을 높일 수 있다.

문제

1이상 K이하의 숫자를 하나 고르는 행위를 N번 반복하여 나올 수 있는 모든 서로 다른 순서쌍을 구해주는 프로그램을 작성해보세요. 단, 연속하여 같은 숫자가 3번 이상 나오는 경우는 제외합니다.

풀이

k, n = map(int, input().split())
#k이하의 수로 이루어진 n자리수가 되는 모든 경우의 수 1부터 출력

arr = []
#cur_num : 현재 가리키는 곳이 앞에서 부터 몇 번째 자리 수 인지
def choose(cur_num):  #cur_num번째 위치에 1~k 중 하나를 선택하는 함수
    if cur_num == n+1:
        for elem in arr:
            print(elem, end=' ')
        print()
        return
    for i in range(1, k+1): 
        if cur_num >= 3 and arr[-2] == arr[-1] == i: #앞선 두 숫자와 현재 추가할 값이 같은지 확인
            continue #연속한다면 선택하지 않고 return
        arr.append(i)
        choose(cur_num+1) #재귀 호출
        arr.pop() #원래 상태로 다시 돌려줌

#cur_num 1부터 시작하므로 인자로 1을 넘겨
choose(1)

• 값을 넣어주기 전 주어진 조건에 부합하는지 먼저 if문으로 확인 후 조건에 부합하다면 append 부합하지 않다면 continue
• 앞서 이야기 했듯이 출력할 때가 아닌 값을 선택할 때 주어진 조건을 확인한다.

3. N개중에 M개 고르기 == 조합(Combination)

1번 예제(k중 하나를 n번 선택하기)에서 n자리 이진수를 만들어 보았는데 여기에 n자리 이진 수 중 1의 개수가 정확히 m개인 경우만 출력하라는 조건이 붙는다면 밑에 이미지와 같을 것이다.

위 이미지 속 첫 번째 칸에는 1, 두 번째 칸에는 2와 같이 네모 칸 마다 1부터 k가 할당되어 있고 칸의 값이 0이면 사용하지 않는 것, 값이 1이면 사용하는 것이라고 생각한다면 이는 k개의 숫자 중 n개를 뽑는 kCn 으로 생각할 수 있다. 리스트의 인덱스에 1~k가 할당된다고 생각하고 인덱스에 해당하는 값이 1이면 사용, 0이면 사용하지 않는다고 생각하면 이해가 편하다.

n, m = map(int, input().split())

arr = []
#cur_num : 현재 가리키는 곳이 앞에서 부터 몇 번째 자리 수 인지
#cnt : 현재까지 나온 1의 개수
def find_combination(cur_num, cnt):  #cur_num번째 위치에 0또는 1을 넣어준다.
    if cur_num == n+1:
        if cnt == m:
            for elem in arr:
                print(elem, end=' ')
            print()
        return
    
    #=================이 부분이 단계별로 변경된다=================#
    arr.append(0)
    find_combination(cur_num+1, cnt) #0을 선택했을 경우 cnt 유지
    arr.pop()

    arr.append(1)
    find_combination(cur_num+1, cnt+1) #1을 선택했을 경우 cnt 증가
    arr.pop()
    #==========================================================#

#첫 번째 자리 부터 시작하고 나온 1의 개수가 0부터 시작
find_combination(1, 0)

위 코드는 앞서 얘기한 n자리의 이진 수 중 1의 개수가 m개인 경우만 출력하는 코드이다. 우리는 이 코드에서 부터 시작하여 몇 가지 단계를 거쳐 n개의 숫자 중 M개를 뽑아 만들 수 있는 모든 조합을 오름차순으로 출력하는 코드로 바꿔나갈 것이다.

1. 1을 선택했을 경우 1을 cur_num을 arr에 추가

    arr.append(0)
    find_combination(cur_num+1, cnt)
    arr.pop()

    arr.append(cur_num) #이 부분이 1에서 cur num으로 변경
    find_combination(cur_num+1, cnt+1)
    arr.pop()

• 첫 번째 칸(자리) 부터 마지막 칸 까지 1에서 N까지의 숫자가 할당된다고 생각하면 cur_num이 가리키는 게 곧 자리에 해당된 숫자와 같다.
• 단순히 1이 아닌, 자리에 할당된 숫자를 arr에 append하여 출력 시 사용된 숫자를 보여준다.

2. 0을 선택했을 경우, 즉 해당 숫자를 사용하지 않을 경우 apppend 안 함

    #기존 append, pop 제거
    find_combination(cur_num+1, cnt)


    arr.append(cur_num)
    find_combination(cur_num+1, cnt+1)
    arr.pop()

• 기존에는 선택되지 않은 경우에 0이 arr에 들어갔는데 0을 넣지 않는다면 출력 시 선택된 숫자만 보여줄 수 있다.

3. 오름차순으로 보여주기 위해 처음에 0이 아닌 1을 선택

    #기존 순서를 바꿈
    arr.append(cur_num)
    find_combination(cur_num+1, cnt+1)
    arr.pop()

    find_combination(cur_num + 1, cnt)

• 오름차순으로 보여주기 위해 1을 선택하는 경우, 즉 해당 자리수에 할당된 값을 사용하는 경우를 먼저 수행한다.

이해가 잘 되지 않을 경우 순서를 바꾸기 전 후의 재귀 트리를 그려보자!

순열 만들기

n이 주어졌을 때 1부터 n까지의 수들을 이용해 중복 없이 모든 수들이 나오는 순열을 증가하는 순으로 출력하는 경우를 살펴보자. 방법은 밑에 이미지와 같이 첫 번째 자리 부터 1~n까지의 숫자를 넣어주는데 앞서 선택한 숫자는 제외한 나머지 숫자 중에서 선택한다.

이는 기존 n자리의 이진수의 경우의 수를 구하는 문제에 특정 조건을 부여한 것이다.

문제

1부터 n까지의 수를 정확히 한 번씩만 사용하여 만들 수 있는 가능한 모든 수열을 구해주는 프로그램을 작성해보세요. 단, 사전순으로 가장 앞에 있는 수열부터 먼저 출력하도록 합니다.

풀이

n = int(input())
arr = []
visited = [0 for _ in range(11)] #선택 여부를 확인하기 위한 배열 선언


def solve(cur_num): #1~n까지의 숫자 중 앞에서 선택되지 않은 수를 결정하는 함
    if cur_num == n+1:
        for elem in arr:
            print(elem, end=' ')
        print()
        return
    for i in range(1, n+1):
        if visited[i] == 1: #현재 선택하려는 숫자가 이미 선택했던 숫자라면 continue
            continue
        else:
            visited[i] = 1
            arr.append(i)
            solve(cur_num+1)
            arr.pop()
            visited[i] = 0

solve(1)

• 앞서 선택했던 건지 확인하기 위해 visited 배열 사용
• 재귀에 들어가기 전 visited 값을 1로 바꿔주고 재귀에서 벗어난 경우 다시 visited 값을 0으로 바꿔준다.

조합에 경우 현재 값을 고를 때 이전 값이 영향을 주지 않지만 순열의 경우는 현재 값을 고를 때 이전 값을 고려해야 한다. 따라서 조합에서는 애초에 값이 순서대로 등장하여 체크했던 걸 다시 체크할 일이 없는 반면 순열의 경우 값이 뒤죽박죽으로 등장하기 때문에 visited 배열을 필요로한다.