[패스트캠퍼스] Upstage AI Lab 3기 학습 블로그_코딩 테스트:자료구조 및 알고리즘 개론 (재귀 recursion)

재귀와 코딩 테스트 문제

재귀란?

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 이를 통해 복잡한 문제를 더 작은 문제로 나누어 해결할 수 있습니다.

재귀의 이해

유치원생도 이해할 수 있도록 재귀를 설명하자면, "러시안 돌 속에 돌" 장난감을 생각하면 됩니다. 큰 인형 속에 더 작은 인형이 들어있고, 가장 작은 인형을 찾을 때까지 계속 작은 인형을 열어보는 것과 비슷합니다. 문제를 계속 작은 문제로 나누고, 가장 작은 문제를 해결해나가면 전체 문제를 해결할 수 있습니다.

재귀의 예시

계단 오르기 문제

어린이가 계단을 오르는 방법을 여러 가지 방법으로 계산해봅시다. 각 단계에서 한 계단 또는 두 계단을 오를 수 있다고 가정합니다. 예를 들어 계단이 3개라면 다음과 같은 방법으로 오를 수 있습니다:

1. 한 계단, 한 계단, 한 계단 (1+1+1)
2. 한 계단, 두 계단 (1+2)
3. 두 계단, 한 계단 (2+1)

이를 재귀적으로 생각해보면, 마지막 계단을 한 번에 한 계단 오르면 남은 계단 수는 ( n-1 )이 되고, 두 계단을 한 번에 오르면 ( n-2 )가 됩니다. 따라서 ( n )개의 계단을 오르는 방법의 수는 ( n-1 )개의 계단을 오르는 방법의 수와 ( n-2 )개의 계단을 오르는 방법의 수를 더한 것과 같습니다.

def climb_stairs(n):
    # 기저 사례: 계단이 0개 또는 1개일 때, 오를 수 있는 방법은 1가지입니다.
    if n == 0 or n == 1:
        return 1

    # 두 번째 계단부터는 재귀적으로 문제를 해결합니다.
    return climb_stairs(n - 1) + climb_stairs(n - 2)

# 예제 실행
print(climb_stairs(3))  # 출력: 3

재귀를 사용할 때 주의해야 할 점

1. 기저 사례의 설정: 모든 재귀 함수는 종료 조건이 있어야 합니다. 기저 사례가 없거나 잘못 설정되면 함수가 영원히 자기 자신을 호출하며 프로그램이 멈추거나 "스택 오버플로" 오류가 발생할 수 있습니다.
2. 스택 오버플로: 재귀 함수는 호출할 때마다 호출 스택에 자신의 정보를 저장합니다. 재귀가 너무 깊어지면 스택 공간이 부족해져서 스택 오버플로 오류가 발생할 수 있습니다. 이를 방지하려면 재귀의 깊이를 적절히 제어하거나 반복문으로 대체할 수 있는지 고려해야 합니다.
3. 성능 문제: 일부 재귀 함수는 동일한 계산을 반복하여 수행할 수 있습니다. 이러한 중복을 피하기 위해 메모이제이션(memoization) 기법을 사용하거나, 가능하다면 반복적 방법(iterative method)을 사용하는 것이 좋습니다.
4. 호출 스택의 크기: 일부 프로그래밍 환경에서는 호출 스택의 크기가 제한되어 있어 깊은 재귀를 사용할 때 문제가 발생할 수 있습니다. 이 경우 스택 크기를 조정하거나 꼬리 재귀 최적화(tail recursion optimization)를 사용하여 문제를 해결할 수 있습니다.
5. 재귀 설계의 복잡성: 재귀 함수는 때로는 이해하기 어렵고 디버깅하기 힘들 수 있습니다. 함수가 자기 자신을 호출하는 방식은 종종 프로그램의 흐름을 따라가기 어렵게 만들며, 에러 발생 시 그 원인을 찾기 어려울 수 있습니다.

재귀가 필요한 코딩 테스트 문제 예시

1. 트리의 깊이나 높이 찾기

문제 설명: 이진 트리의 높이를 구하는 문제입니다.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def max_depth(root):
    if root is None:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return max(left_depth, right_depth) + 1

# 예제 트리
#      3
#     / \
#    9  20
#      /  \
#     15   7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(max_depth(root))  # 출력: 3

2. 그래프의 깊이 우선 탐색(DFS)

문제 설명: 그래프에서 DFS를 구현하여 모든 노드를 방문하는 문제입니다.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

# 예제 그래프
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

dfs(graph, 'A')  # 출력: A B D E F C

def dfs(graph, start, visited=None):
    if visited is None:
        visited = []
    visited.append(start)
    print(f"Visited: {visited}")  # 방문한 노드 출력
    for next in graph[start]:
        if next not in visited:
            print(f"Next: {next}")  # 다음에 방문할 노드 출력
            dfs(graph, next, visited)
    return visited

# 예제 그래프
graph = [
    [1, 2],    # 노드 0과 연결된 노드들
    [0, 3, 4], # 노드 1과 연결된 노드들
    [0, 5],    # 노드 2와 연결된 노드들
    [1],       # 노드 3과 연결된 노드들
    [1, 5],    # 노드 4와 연결된 노드들
    [2, 4]     # 노드 5와 연결된 노드들
]

dfs(graph, 0)  # DFS 시작

 

 

3. 백트래킹을 통한 조합, 순열 문제

문제 설명: 주어진 요소들로 만들 수 있는 모든 순열을 찾는 문제입니다.

def permute(nums):
    result = []

    def backtrack(path, options):
        if not options:
            result.append(path)
        for i in range(len(options)):
            backtrack(path + [options[i]], options[:i] + options[i+1:])

    backtrack([], nums)
    return result

# 예제 실행
print(permute([1, 2, 3]))
# 출력: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

문제 설명: 주어진 요소들로 만들 수 있는 모든 조합을 찾는 문제입니다.

def combine(n, k):
    result = []
    
    def backtrack(start, path):
        if len(path) == k:
            result.append(path)
            return
        for i in range(start, n + 1):
            backtrack(i + 1, path + [i])
    
    backtrack(1, [])
    return result

# 예제 실행
print(combine(5, 3))  # 출력: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

 

4. 분할 정복 알고리즘

병합 정렬

문제 설명: 배열을 병합 정렬로 정렬하는 문제입니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 예제 실행
print(merge_sort([3, 6, 8, 10, 1, 2, 1]))  # 출력: [1, 1, 2, 3, 6, 8, 10]

퀵 정렬

문제 설명: 배열을 퀵 정렬로 정렬하는 문제입니다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# 예제 실행
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))  # 출력: [1, 1, 2, 3, 6, 8, 10]

5. 동적 계획법 문제의 재귀적 풀이

문제 설명: 피보나치 수열의 값을 구하는 문제입니다.

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

# 예제 실행
print(fib(10))  # 출력: 55

6. 이진 검색

문제 설명: 정렬된 배열에서 이진 검색을 통해 특정 값을 찾는 문제입니다.

def binary_search(arr, target):
    def search(left, right):
        if left > right:
            return -1