넌 과감해질 필요가 있어

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/7C9RgOcvkvo?si=p-_dsBcTLy0K_6WN

스택 Stack

Last-In First-Out

먼저 들어온 데이터가 나중에 나가는 선입후출 자료구조.

stack = []

stack.append(5) # push
stack.append(3)
stack.append(2)
stack.pop() # pop

print(stack) # [5, 3]

python에서 stack은 리스트로 구현할 수 있다.

• 삽입: append(요소) # O(1)
• 삭제: pop() # O(1)

큐 queue

First-In First-Out

먼저 들어온 데이터가 먼저 나가는 선입선출 자료구조.

from collections import deque

queue = deque()

queue.append(5) # push
queue.append(3)
queue.popleft() # pop
queue.append(2)

print(queue) # [3, 2]

python에서 queue는 deque을 사용해서 구현한다.

삽입: append(요소) # O(1)

삭제: popleft() # O(1)

deque은 내부적으로 연결 리스트로 구현이 되어 있다.

따라서 삽입, 삭제가 O(1)으로 가능하다.

단 random access가 불가능하기에, 요소 접근에는 O(N)이 소요된다.

재귀 함수 Recursive Fuction

재귀 함수란? 자기 자신을 다시 호출하는 함수.

재귀 함수는 반복문으로 동일하게 구현이 가능하다. 역도 그렇다.

코드의 길이는 짧아지지만, 인간에게 직관적이지 않으므로 신중하게 사용해야 한다.

문제 풀이에 활용하려면 종료 조건을 반드시 명시해야 한다.

종료 조건 없이 함수가 무한히 호출되면, stack overflow가 발생하기 때문.

import sys
sys.setrecursionlimit(10 ** 5)

python3는 기본적으로 재귀 깊이를 1,000으로 제한해 놓았다.

그러나 문제를 풀다보면 이 제한을 해제해야 하는 경우가 있다.

sys.setrecursionlimit()으로 이 제한을 늘려주자

직접 해본 결과 재귀 깊이가 29945를 넘어가면, segmentation fault 에러가 발생한다.

프로그램이 메모리를 잘못 액세스 했을 때 발생하는 오류로, stack overflow를 원인으로 발생하는 오류 중 하나이다.

정해진 메모리 공간을 넘어가면, 다른 데이터를 건드릴 수 있기에 이를 방지하기 위한 에러이다.

실전에서는 재귀 깊이 제한을 10 ** 5 정도로 설정한 뒤에, 종료 조건을 반드시 작성하자.

예시1. 팩토리얼

def factorial_recursive(n)
    if n <=1 :
        return 1
    return n * factorial_recursive(n - 1)
    
# 0! == 1
# 1! == 1

예시2. 유클리드 호제법

def gcd(a, b)
    if a % b == 0 :
        return b
    else :
        return gcd(b, a % b)
        
# 성질: a와 b의 나머지가 r이라면, a와 b의 최대 공약수 == b와 r의 최대 공약수
# a, b의 대소 관계와 상관없이 동작한다.

DFS (Depth First Search)

정의

깊이 우선 탐색.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.

뼈대

def dfs(graph, v, visited):
    
    visited[v] = True # 현재 노드 방문 처리
    print(v, end = " ") # 방문한 노드를 순서대로 출력
    
    for i in graph[v]: # 인접한 노드를 모두 확인
        if not visited[v]: # 방문하지 않은 노드가 있다면
            dfs(graph, i, visited) # 재귀적으로 탐색

스택 혹은 재귀 함수를 이용한다.

1. 탐색 시작 노드를 스택에 삽입 / 방문 처리
2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리.
   방문하지 않은 인접한 노드가 없으면 스택 최상단 노드 꺼냄.
3. 2번 과정을 수행할 수 없을 때 까지 반복

BFS (Breadth First Search)

정의

너비 우선 탐색.

가까운 노드부터 우선적으로 탐색하는 알고리즘.

뼈대

from collections import deque

def bfs(graph, start, visited):
    
    queue = deque([start]) # deque에 시작 노드를 추가해서 초기화
    visited[start] = True # 현재 노드 방문 처리
    
    while queue: # 큐가 빌 때까지 반복
        v = queue.popleft() # 가장 먼저 들어온 노드를 제거 # 처음에는 시작 노드
        print(v, end = " ") # 순서대로 출력
        
        for i in graph[v]: # 인접한 노드를 모두 확인
            if not visited[i]: # 방문하지 않은 노드가 있다면
                queue.append(i) # 큐에 추가하고
                visited[i] = True # 방문 처리

큐를 이용한다.

1. 탐색 시작 노드를 큐에 삽입 / 방문 처리
2. 큐에서 노드 꺼내고 해당 노드의 인접 노드 중에서, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번 과정을 수행할 수 없을 때까지 반복