[쓰면서 익히는 알고리즘과 자료구조](4) 스택(Stack)과 재귀(Recursion)

 

💡 FILO - First In Last Out

 

재귀 알고리즘은 정상적인 수행 및 완료되기 위해 아래 3가지 조건을 만족해야 한다.

• 베이스(base) 케이스가 반드시 정의돼야 한다. 베이스 케이스는 재귀 호출을 마무리할 수 있는 조건이다. 앞서 살펴본 예제의 베이스 케이스는 nums 배열 요소 개수가 1인 경우로, 재귀 호출을 안 하고 마무리한다.
• 지속적으로 재귀 인자가 변경돼야 하고 변경되는 인자는 베이스 케이스로 수렴해야 한다. 예제를 보면 다음 재귀 호출에 전달되는 인자는 맨 앞 요소가 빠진 상태로 전달되고 이를 통해 배열의 요소 개수가 베이스 케이스로 다가가는 모양새가 된다.
• 재귀 알고리즘은 자기 자신을 호출하는 과정이 필요하다.

재귀함수와 레지스터

EBP (Extened Base Pointer: 스택의 시작점을 저장)

ESP (Extend Stack Pointer: 스택 메모리 공간 다음을 시작 위치로 가지는 레지스터)

 

💡 재귀는 다양한 알고리즘(깊이 우선 탐색, 동적 프로그래밍 등)을 이해하는 기반이 되는 기술이므로 꼭 이해하고 넘어가자.

---

4.3 유효한 괄호 검증

기본적인 스택 관련 문제에서 가장 많이 접하는 문제다. 이 문제는 스택을 사용해야 한다는 것만 인지하면 쉽게 해결할 수 있다.

 

def is_valid(s: str) -> bool:

    stack = []

    paren_map = {
        ')': '(',
        '}': '{',
        ']': '['
    }

    for ch in s:
        if ch not in paren_map.keys():
            stack.append(ch)
        else:
            pair = stack.pop() if stack else ''
            
            if paren_map[ch] != pair:
                return False
    
    return len(stack) == 0

---

4.4.1 계단 오르기

입력으로 주어지는 n 개의 계단을 1번에 1개 혹은 2개 올라 도달할 수 있는 방법의 가짓수를 찾아내는 문제다.

• 베이스(base) 케이스가 반드시 정의돼야 한다.
  • 이 문제에서는 꼭대기(n)에 도달하거나 꼭대기를 넘어서는 경우
• 지속적으로 재귀 인자가 변경돼야 하고 변경되는 인자는 베이스 케이스로 수렴해야 한다.
  • 계속해서 1 또는 2칸씩 오르므로 언젠가는 n에 도달하거나 꼭대기를 넘어선다.
• 재귀 알고리즘은 자기 자신을 호출하는 과정이 필요하다.

def claim_stairs(n: int) -> int:
    def climb(i, goal):
        if i == goal:
            return 1
        if i < goal:
            return 0

        return climb(i + 1, n) + climb(i + 2, n)

    return climb(0, n)

---

4.4.2 모든 문자열 치환(permutation)

입력으로 주어진 문자열의 가능한 치환을(조합) 모두 출력해보자. 예를 들어 입력된 문자열이 ‘abc’ 라면 결과는 [’abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, cba’] 가 되어야 한다.

def find_permutation(s: str):
    if len(s) == 1:
        return list(s)

    ans = []
    curr = s[0]
    s = s[1:]

    words = find_permutation(s)

    for sub in words:
        for i in range(len(sub) + 1):
            # a -> bc  : abc , bac, bca
            # sub 에 curr 을 요리조리 껴서 넣는다
            ans.append("".join([sub[:i], curr, sub[i:]]))

    return ans

def find_permutation(s: str):
    if len(s) == 1:
        return list(s)

    ans = []
    curr = s[0]
    s = s[1:]

    words = find_permutation(s)

    for sub in words:
        for i in range(len(sub) + 1):
            # a -> bc  : abc , bac, bca
            # sub 에 curr 을 요리조리 껴서 넣는다
            ans.append("".join([sub[:i], curr, sub[i:]]))

    return ans

---

4.4.3 동전교환

import sys


def coin_change(coins: list[int], value: int) -> int:
    def change(v: int) -> int:
        if v == 0:
            return 0

        min_coin_cnt = sys.maxsize

        for c in coins:
            if (v - c) >= 0:
                change_cnt = change(v - c)
                if change_cnt < min_coin_cnt:
                    min_coin_cnt = change_cnt

        return min_coin_cnt + 1

    ans = change(value)

    return ans if ans != sys.maxsize + 1 else - 1

---

4.4.4 배열의 두 부분집합의 최소 차이 만들기

import sys


def coin_change(coins: list[int], value: int) -> int:
    def change(v: int) -> int:
        if v == 0:
            return 0

        min_coin_cnt = sys.maxsize

        for c in coins:
            if (v - c) >= 0:
                change_cnt = change(v - c)
                if change_cnt < min_coin_cnt:
                    min_coin_cnt = change_cnt

        return min_coin_cnt + 1

    ans = change(value)

    return ans if ans != sys.maxsize + 1 else - 1