코딩 테스트를 위한 파이썬 문법과 알고리즘 정리 - v2

000.md

TODO 목차

원랜 이걸 썼는데, https://gist.github.com/YangSiJun528/dd3e23e99cec3675ae23b9df12556347

너무 길어지고 관리도 안되고, 잘못된 내용이 많아서 따로 정리하기로 함.

010.md

DFS, depth-first search

이진 트리를 DFS(depth-first search) 방식으로 순회하는 코드

def dfs(node):
    if node is None:
        return
    # preorder
    dfs(node.left)
    # inorder
    dfs(node.right)
    # postorder

그래프를 DFS로 순회하는 코드

graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}
visited = set()
def dfs(cur_v):
    visited.add(cur_v)
    # 처리(pre order): 함수 진입 직후 = 반복문의 pop 직후와 동치
    for v in graph[cur_v]:
        if v in visited:
            continue
        dfs(v)
    # post order

반복문+Stack을 사용해 구현한 예시

재귀 DFS는 노드에 진입할 때 visited를 마킹한다. 반복문에서 pop이 곧 "진입"이므로, pop 시점에 마킹해야 타이밍이 일치한다. push는 "나중에 방문할 후보를 쌓는 것"일 뿐 진입이 아니다.

def iterative_dfs(start):
    stack = [start]
    visited = set()
    result = []
    while stack:
        cur_v = stack.pop()
        if cur_v in visited:
            continue
        visited.add(cur_v)
        result.append(cur_v)  # 처리: pop 직후
        for v in reversed(graph[cur_v]):
            if v not in visited:
                stack.append(v)
    return result

BFS, breadth-first search

이진 트리를 BFS(breadth-first search) 방식으로 순회하는 코드

def bfs(node):
    visited = []
    if node is None:
        return 0
    q = collections.deque()
    q.append(node)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)  # 처리: popleft 직후
        for child in [cur_node.left, cur_node.right]:
            if child is None:
                continue
            else:
                q.append(child)
    return visited

그래프를 BFS로 순회하는 코드

graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}
def bfs(start):
    visited = {start}
    q = collections.deque([start])
    result = []
    while q:
        cur_v = q.popleft()
        result.append(cur_v)  # 처리: popleft 직후
        for v in graph[cur_v]:
            if v in visited:
                continue
            else:
                visited.add(v)
                q.append(v)
    return result

DFS/BFS 팁

DFS, BFS 특징

둘 다 자료구조가 빌 때까지 반복 수행한다. 처리는 pop/popleft 직후에 한다. BFS는 읽지 않은 이웃을 queue에, DFS는 stack에 담는다.

visited 체크 시점

• 넣을 때 체크: for문에서 if v in visited: continue로 걸러내고, 통과한 경우만 visited.add(v) + push. 중복 삽입을 막아 효율적이다. 재귀 DFS, BFS에서 사용한다.
• 뺄 때 체크: pop 직후 if cur_v in visited: continue로 걸러냄. 같은 노드가 여러 번 들어갈 수 있어 공간이 O(V + E)까지 늘어날 수 있다. 반복문 DFS에서 사용한다.

반복문 DFS는 뺄 때 체크를 써야 재귀 DFS와 동일한 방문 순서가 보장된다. 넣을 때 체크를 쓰면 이웃을 전부 스택에 넣은 뒤 하나를 꺼내는 구조 때문에 재귀 DFS와 방문 순서가 달라질 수 있다.

시간·공간 복잡도

정점 V, 간선 E일 때 DFS/BFS 모두 시간 O(V + E), 공간 O(V). 반복문 DFS는 뺄 때 체크를 사용하므로 중복 삽입으로 공간이 O(V + E)까지 늘어날 수 있다.

순회 종류

• 이진 트리 DFS: preorder, inorder, postorder 세 가지.
• 그래프 DFS: preorder, postorder 두 가지. 자식이 둘로 고정되지 않으므로 inorder 없음.
• BFS: 레벨 순서 순회 하나뿐.

DFS 구현 방식 선택

반복문(Stack) DFS는 preorder는 자연스럽지만, postorder는 상태 플래그나 스택 두 개 등 별도 장치가 필요하다. postorder가 필요하면 재귀를 추천한다.

DFS vs BFS 선택 기준

• 최단 거리/최소 횟수(가중치 없는 그래프): BFS. 처음 도달한 경로가 최단 경로.
• 모든 경로 탐색, 백트래킹, 순열/조합: DFS.
• 연결 요소, 단순 도달 가능성: 둘 다 무방.
• 트리 깊이/높이: DFS. 재귀 반환값으로 깊이 계산이 자연스럽다.
• 레벨 단위 처리: BFS. len(q)로 레벨 구분이 쉽다.

011.md

위상 정렬, topological sort

DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서 간선 방향을 거스르지 않는 순서로 정점을 나열하는 알고리즘. 진입 차수(indegree)가 0인 정점부터 시작하여, 해당 정점을 제거하고 연결된 간선을 제거하는 과정을 반복한다. BFS(Kahn's algorithm) 기반으로 구현한다.

from collections import deque

def topological_sort(vertices, edges):
    indegree = {v: 0 for v in range(vertices)}
    graph = {v: [] for v in range(vertices)}
    for u, v in edges:
        graph[u].append(v)  # 단방향
        indegree[v] += 1

    result = []
    queue = deque(v for v in indegree if indegree[v] == 0)

    while queue:
        u = queue.popleft()
        result.append(u)  # 처리: popleft 직후
        for v in graph[u]:
            indegree[v] -= 1  # u 제거 → u→v 간선 제거 → v의 진입 차수 감소
            if indegree[v] == 0:
                queue.append(v)

    return result

Dijkstra

가중치 그래프에서 단일 출발점 최단 경로를 구하는 그리디 알고리즘. 접근 가능한 정점 중 가장 비용이 작은 것을 우선 처리하며, 우선순위 큐(힙)를 사용해 구현한다.

import heapq

graph = {
    'A': [(2, 'B'), (5, 'C')],
    'B': [(2, 'A'), (3, 'C'), (1, 'D')],
    'C': [(5, 'A'), (3, 'B'), (2, 'D')],
    'D': [(1, 'B'), (2, 'C')]
}

def dijkstra(graph, start, final):
    costs = {}
    pq = []
    heapq.heappush(pq, (0, start))
    while pq:
        cur_cost, cur_v = heapq.heappop(pq)
        if cur_v in costs:
            continue
        costs[cur_v] = cur_cost
        for cost, next_v in graph[cur_v]:
            if next_v in costs:
                continue
            else:
                next_cost = cur_cost + cost
                heapq.heappush(pq, (next_cost, next_v))
    return costs[final]

위상 정렬 / Dijkstra 팁

위상 정렬 특징

• 단방향 그래프이므로 visited 처리가 필요 없다. 진입 차수가 0이 되는 시점에 큐에 넣으므로 중복 방문이 구조적으로 불가능하다.
• 결과 길이가 정점 수보다 작으면 사이클이 존재한다는 뜻이다. len(result) < vertices로 사이클 검출 가능.
• 큐 대신 힙을 쓰면 사전순/번호순 등 특정 순서의 위상 정렬을 구할 수 있다.

Dijkstra 특징

• 구조가 BFS와 유사하다. queue 대신 heap, visited 대신 costs dict를 사용한다.
• costs에 이미 있는 정점은 skip한다. 이는 반복문 DFS의 뺄 때 체크(if cur_v in visited: continue)와 같은 패턴이다. 힙에 같은 정점이 여러 번 들어갈 수 있고, 가장 작은 비용으로 꺼낸 첫 번째가 최단 비용이므로 나머지는 버린다.
• 음수 가중치가 있으면 사용할 수 없다. 음수 가중치가 필요하면 Bellman-Ford를 사용한다.

시간·공간 복잡도

• 위상 정렬: 시간 O(V + E), 공간 O(V + E).
• Dijkstra (힙 기반): 시간 O((V + E) log V), 공간 O(V + E). 힙에 중복 삽입이 있으므로 공간이 O(V + E)까지 늘어날 수 있다.

BFS에 heap을 붙이면 Dijkstra다

BFS의 큐를 힙으로, visited를 costs dict로 바꾸면 Dijkstra다. 가중치가 전부 1이면 FIFO 순서가 곧 최소 비용 순서이므로 힙이 필요 없는 것이고, 가중치가 다양해지면 최소 비용 보장을 위해 힙이 필요해진다.

위상 정렬에 힙을 붙이면 우선순위 처리가 된다

큐를 힙으로 바꾸면 진입 차수 0인 정점 중 원하는 기준(번호순 등)으로 처리 가능. 진입 차수가 0이 되는 시점에만 힙에 들어가므로 중복 삽입이 구조적으로 불가능하고, 별도 중복 처리가 필요 없다.

선택 기준

• 가중치 없는 최단 경로: BFS.
• 가중치 있는 최단 경로 (음수 없음): Dijkstra.
• 가중치 있는 최단 경로 (음수 있음): Bellman-Ford.
• 선후 관계/순서 결정: 위상 정렬.

998.md

문자열 입력받기

입출력은 input 대신, sys.stdin.readline()를 사용해야 한다. 왜?: [Python] input()과 sys.stdin 참고.

import sys
from collections import defaultdict

# ------------------------
# 기본 문자열 / 숫자 입력
# ------------------------

# 문자열 한 줄 입력
line = sys.stdin.readline().strip()

# 정수 한 줄 입력
num = int(sys.stdin.readline())

# 문자열 여러 값 입력
values = sys.stdin.readline().split()

# 정수 여러 값 입력
values = list(map(int, sys.stdin.readline().split()))

# 여러 줄 여러 값 입력 1
cnt = int(sys.stdin.readline())
values = [sys.stdin.readline().split() for _ in range(cnt)]

# 여러 줄 여러 값 입력 2
cnt = int(sys.stdin.readline())
values = [list(map(int, sys.stdin.readline().split(','))) for _ in range(cnt)]


# ------------------------
# 딕셔너리 처리
# ------------------------
# 그래프 (인접 리스트 처리 템플릿)
n, m = map(int, sys.stdin.readline().split())
graph = defaultdict(list)

for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

# 기본값 있는 dict (lambda)
graph = defaultdict(lambda: {"children": [], "parent": None})
graph = defaultdict(list)

# 딕셔너리 정렬
sorted_items = sorted(d.items())
sorted_items = sorted(d.items(), key=lambda x: x[1])

999.md

기타 정보

시간복잡도별 최대 N 기준표 (1초, ~10^8 연산 기준)

• N ≤ 7~8 → 제약 없는 brute-force 배정, 가지치기 전 전수탐색 (N^N)
• N ≤ 10~11 → 완전탐색, 순열 (N!)
• N ≤ 20~25 → 비트마스크, 부분집합 (2^N)
• N ≤ 400~500 → 삼중루프, 플로이드 (N³)
• N ≤ 10,000 → 이중루프, 단순 DP (N²)
• N ≤ 10^5~10^6 → 정렬, 세그트리, 이분탐색 (N log N)
• N ≤ 10^7~10^8 → 선형 스캔, 투포인터, 누적합 (N)
• N ≤ 10^18+ → 수학 공식, 빠른 거듭제곱, GCD (log N / O(1))

10^8을 넘지 않는 N^M 정리

왜 필요한가?

프로그래머스 삼총사 같이 조합(Combination) 문제에서 모든 수를 개산해서 풀 수 있는지 파악하는데 사용할 수 있다. (에시로 든 삼총사는 3^13으로 풀 수 있으므로 모든 경우의 수를 for 구문으로 풀 수 있다.)

• 2^26
• 3^16
• 4^13
• 5^11
• 6^10
• 7^9
• 8^8
• 9^8
• 10^8