알고리즘 레퍼런스

Overview

완전 탐색

• 가능한 모든 경우를 직접 탐색해야 할 때
• 경우의 수가 작거나, 조합/순열 개수가 제한적일 때
• “최적의 해를 찾는 문제지만 탐색 범위가 작아서 완전 탐색으로 충분한 경우”

BFS / DFS 정리

BFS

• “최단 거리” 문제가 나오면 무조건 BFS
• 그래프에서 레벨 탐색이 필요한 경우
• 이동 비용이 모두 동일(=간선 가중치가 1)인 경우

DFS

• 조합/경로 탐색
• 백트래킹 문제(가능한 경로 탐색하면서 중간 가지치기)
• 사이클 탐지, 연결 요소 찾기

대표 문제

• 타겟 넘버(DFS), 네트워크(BFS/DFS), 여행 경로(DFS), 단어 변환(BFS)

---

다익스트라(Dijkstra)

• 하나의 시작점에서 다른 모든 노드까지 최단거리
• 간선 가중치가 양수
• 우선순위 큐(힙) 사용 → O(E log V)
• BFS의 확장판(= 비용이 있는 BFS)

플로이드-워셜(Floyd-Warshall)

• 모든 노드 쌍 간 최단거리(All-Pairs Shortest Path)
• DP 기반
• O(N³) → 노드 수가 작을 때만 사용
• 전체 그래프 최단거리 테이블이 필요할 때 사용

---

그리디(Greedy)

• “현재 가장 좋은 선택”을 했을 때 이후 선택에 영향 없을 때
• 정렬 기반의 선택 문제에서 자주 등장
• 항상 최적해가 보장되는 조건 필요 (증명 관건)
• 최적 부분 구조: 부분 문제의 최적해가 전체 문제에도 최적
• 탐욕적 선택 속성: 지금 선택이 미래 선택과 독립적

대표 문제

• 회의실 배정(끝나는 시간 정렬)
• 동전 0 (동전 가치가 배수 관계일 때)
• 체육복 문제
• 구명보트(정렬 + 투포인터 조합)

---

다이나믹 프로그래밍(DP)

• 중복되는 부분 문제
• 재귀 사용 시 같은 계산 반복 → DP로 최적화
• 가능한 값 범위가 작을 때(예: sum ≤ 1000, 길이가 10000 이하)

점화식 세우기

• “이 문제를 더 작은 문제들로 나눌 수 있는가?”
• “현재 정답 = 이전 결과 기반 계산”
• 예: dp[i] = min(dp[i-1], dp[i-3]) + cost[i]

탑다운 / 바텀업

• 탑다운: 재귀 + 메모이제이션
• 바텀업: 반복문으로 dp 테이블 채우기 (보통 더 빠름)

대표 문제

• 정수 삼각형
• 피보나치
• 동전 교환
• 효율적인 화폐 구성
• 배낭 문제(Knapsack)

---

해시 / 정렬

• 정렬 key 정리: 코테 90%는 “정렬 + 조건 선택” 문제로 해결됨
• 우선순위 조건을 key 튜플로 표현 가능

대표 문제

• 정렬 + 해시 조합 빈도 계산 후 정렬하는 문제 매우 흔함
• “신고 결과 받기”, “완주하지 못한 선수”, “베스트앨범” 등이 대표적

---

우선순위 큐 & 힙

• (우선순위1, 우선순위2, …) → 앞에서부터 비교
• 디스크 컨트롤러 문제의 핵심

대표 문제

• 프로그래머스 디스크 컨트롤러
• 더 맵게
• 이중 우선순위 큐
• 작업 스케줄링 문제

---

투 포인터(Two Pointers)

정렬 + 양방향 탐색

• 배열이 정렬되어 있을 때 양 끝을 좁히며 탐색
• “합이 특정 값 되는 두 수” 문제

연속 부분합

• 구간합/슬라이딩 윈도우
• 합이 M 이하/이상일 때 최소 길이 구하기 등

슬라이딩 윈도우

• 고정/가변 크기 윈도우로 “최근 K개” 문제 해결
• 예: 문자열 안의 특정 패턴 찾기

대표 문제

• 부분합, 연속된 자연수의 합
• 수들의 합 2
• 주식 가격

---

이분 탐색(Binary Search)

lower_bound / upper_bound

from bisect import bisect_left, bisect_right

• 값 존재 여부
• 특정 범위 개수 세기

parametric search

• “정답을 직접 찾는 대신 정답을 판별하는 함수 작성”
• 예: 랜선 자르기, 징검다리, 배 배치, 공유기 설치

대표 문제

• 원하는 값 찾기
• 조건을 만족하는 최소/최대 값 찾기

---

트리 / 그래프 기본

BFS/DFS + 트리 성질

• 트리는 사이클 없음
• 루트 기준 거리, 부모 노드 저장 등 BFS로 해결
• DFS로 서브트리 탐색/노드 개수 계산 가능

LCA (최소 공통 조상)

• 트리에서 두 노드의 가장 가까운 공통 부모 찾기
• 깊이 맞추고 부모 테이블 이용

MST / 유니온파인드

• MST: Kruskal(정렬 + Union Find), Prim
• Union-Find: 집합 병합/연결 여부 판단

대표 문제

• 트리의 부모 찾기
• 전력망을 둘로 나누기
• 네트워크(Union-Find)
• 최소 신장 트리

구현 문제 팁

문자열 처리

• replace, split, join, strip
• 슬라이싱으로 빠른 조작
• 정규식은 되도록 피하고 직접 구현(CT 기준)

좌표 시뮬레이션

• dx, dy 배열로 이동 처리
• 방향 전환
• 그리드 기반 문제에서 필수 패턴

파이썬 문법 팁 모음

• enumerate
• zip
• sorted(key=)
• any(), all()
• 리스트 컴프리헨션
• 딕셔너리 get(), setdefault(), Counter
• deepcopy 대신 리스트 컴프리헨션 활용

---

완전 탐색(Brute Force)

• DFS 형태로 구현하거나
• for문 2~3중첩으로 모든 조합을 순회하기도 함

1) 단순 중첩 반복문

arr = [1, 2, 3, 4]
 
best = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        val = arr[i] + arr[j]
        best = max(best, val)

2) 재귀로 모든 조합 만들기

n = len(arr)
choice = []
 
def dfs(idx):
    if idx == n:
        # choice 사용
        return
    # 현재 원소 선택 O
    choice.append(arr[idx])
    dfs(idx + 1)
    choice.pop()
    # 현재 원소 선택 X
    dfs(idx + 1)
 
dfs(0)

3) itertools 순열/조합

from itertools import permutations, combinations
 
for p in permutations(arr, 3):
    pass
 
for c in combinations(arr, 2):
    pass

---

BFS / DFS

1) 그래프 DFS (재귀)

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
 
def dfs(x):
    visited[x] = True
    for nxt in graph[x]:
        if not visited[nxt]:
            dfs(nxt)
 
dfs(1)

2) 그래프 BFS (최단 거리)

from collections import deque
 
graph = [[] for _ in range(n + 1)]
dist = [-1] * (n + 1)
 
def bfs(start):
    q = deque([start])
    dist[start] = 0
    while q:
        cur = q.popleft()
        for nxt in graph[cur]:
            if dist[nxt] == -1:
                dist[nxt] = dist[cur] + 1
                q.append(nxt)
 
bfs(1)

3) 2차원 격자 DFS/BFS (상하좌우)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
def in_range(x, y):
    return 0 <= x < n and 0 <= y < m
 
def bfs_grid(sx, sy):
    from collections import deque
    q = deque([(sx, sy)])
    visited[sx][sy] = True
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if in_range(nx, ny) and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))

---

그래프 최단 거리

1) 다익스트라 (단일 시작점 최단 거리,start에서 각 노드까지의 최단거리 배열)

import heapq
 
INF = 10**15
graph = [[] for _ in range(n + 1)]   # graph[u] = [(v, w), ...]  (u→v, 비용 w)
 
def dijkstra(start):
    dist = [INF] * (n + 1)          # 최대거리로 다 초기화 해놓고 시작
    dist[start] = 0
    hq = [(0, start)]               # (현재까지 비용, 노드)
 
    while hq:
        cost, cur = heapq.heappop(hq)  # cost: 최소인 금액, cur: 최소인 노드
        if cost > dist[cur]:  # 이미 더 싼 경로가 기록됐으면 넘어감
            continue
        for nxt, w in graph[cur]:  # 현재 노드 cur에서 갈 수 있는 모든 다음 간선 탐색
            nc = cost + w  # nxt로 갈 때의 새로운 비용
            if nc < dist[nxt]:  # nxt로 가는 더 싼 경로를 찾았다면 갱신 
                dist[nxt] = nc
                heapq.heappush(hq, (nc, nxt))  # 갱신된 값 push
 
    return dist                      # start에서 각 노드까지 최단 거리

s, a, b 대상으로만 각각 다익스트라 돌려서 합계 최소값 구하는 문제

import heapq
INF = 10**15   # "무한대"처럼 사용할 큰 값 (초기 거리값용)
 
def solution(n, s, a, b, fares):
    """
    n : 전체 노드 수
    s : 출발 지점
    a : A의 도착 지점
    b : B의 도착 지점
    fares : 간선 정보 [(x, y, 비용), ...]
    """
 
    answer = INF
 
    # graph[u] = [(v, w), (v2, w2), ...]
    # u → v 비용이 w인 간선들을 저장하는 인접 리스트
    graph = [[] for _ in range(n + 1)]
    
    # 간선 정보 구성 (무방향 그래프이므로 양쪽에 모두 추가)
    for x, y, z in fares:
        graph[x].append((y, z))  # x -> y 비용 z
        graph[y].append((x, z))  # y -> x 비용 z
    
    # print(graph)  # 그래프 구조 확인용 
 
    # s → 모든 노드 최단거리
    s_d = daik(s, n, graph)
 
    # a → 모든 노드 최단거리 (무방향이므로 k → a == a → k)
    a_d = daik(a, n, graph)
 
    # b → 모든 노드 최단거리
    b_d = daik(b, n, graph)
    
    # k를 합승을 끊는 지점(경유지)라고 할 때,
    # s→k 비용 + k→a 비용 + k→b 비용의 최솟값을 찾는다.
    for k in range(1, n + 1):
        if s_d[k] == INF or a_d[k] == INF or b_d[k] == INF:
            # 도달 불가능한 노드는 건너뜀
            continue
        
        # 세 경로의 합 중 최소를 정답으로 갱신
        answer = min(answer, s_d[k] + a_d[k] + b_d[k])
    
    return answer
 
 
def daik(start, n, graph):
    """
    start : 시작 노드
    n : 전체 노드 수
    graph : 인접 리스트
    return : start에서 각 노드까지의 최단거리 배열
    """
 
    # dist[i] = start → i 최단거리
    dist = [INF] * (n + 1)
    dist[start] = 0
 
    # 우선순위 큐: (현재까지 비용, 노드)
    hq = [(0, start)]  
    
    while hq:
        cost, cur = heapq.heappop(hq)  # 현재 비용이 가장 작은 노드 pop
        
        # 이미 더 싼 경로가 기록됐으면 넘어감
        if cost > dist[cur]:
            continue
 
        # 현재 노드 cur에서 갈 수 있는 모든 간선 탐색
        for (nxt, w) in graph[cur]:
            # nxt로 갈 때의 새로운 비용
            nc = cost + w
            
            # nxt로 가는 더 싼 경로를 찾았다면 갱신
            if nc < dist[nxt]:
                dist[nxt] = nc
                heapq.heappush(hq, (nc, nxt))  # 갱신된 값 push
 
    return dist
 

---

2) 플로이드-워셜 (모든 쌍 최단 거리)

INF = 10**15
dist = [[INF] * (n + 1) for _ in range(n + 1)]
 
# 자기 자신까지 거리는 0
for i in range(1, n + 1):
    dist[i][i] = 0
 
# 간선 정보 입력 (a → b, 비용 c)
for a, b, c in edges:
    dist[a][b] = min(dist[a][b], c)
 
# 플로이드-워셜
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
 
# dist[i][j] = i에서 j까지의 최단 거리

---

그리디(Greedy)

1) 정렬 후 순차 선택 (회의실 배정류)

intervals.sort(key=lambda x: x[1])  # 끝나는 시간 기준
 
cnt = 0
end_time = 0
for s, e in intervals:
    if s >= end_time:
        cnt += 1
        end_time = e

2) 정렬 + 양 끝에서 선택 (예: 구명보트)

people.sort()
i, j = 0, len(people) - 1
boat = 0
 
while i <= j:
    if people[i] + people[j] <= limit:
        i += 1
    j -= 1
    boat += 1

3) 동전 거스름 (배수 관계일 때)

coins.sort(reverse=True)
cnt = 0
for c in coins:
    use = n // c
    cnt += use
    n -= use * c

---

다이나믹 프로그래밍(DP)

1) 1차원 DP (예: 계단 오르기, 피보나치)

dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

2) 2차원 DP (예: 정수 삼각형)

dp = [[0] * len(row) for row in triangle]
dp[0][0] = triangle[0][0]
 
for i in range(1, len(triangle)):
    for j in range(len(triangle[i])):
        if j == 0:
            dp[i][j] = dp[i - 1][j] + triangle[i][j]
        elif j == len(triangle[i]) - 1:
            dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

3) 배낭 문제(0/1 Knapsack) 템플릿

# weight[i], value[i], 최대 무게 W
dp = [[0] * (W + 1) for _ in range(n + 1)]
 
for i in range(1, n + 1):
    w, v = weight[i], value[i]
    for cur_w in range(0, W + 1):
        if cur_w < w:
            dp[i][cur_w] = dp[i - 1][cur_w]
        else:
            dp[i][cur_w] = max(dp[i - 1][cur_w],
                               dp[i - 1][cur_w - w] + v)

---

해시 / 정렬

1) 빈도수 세기 패턴

from collections import Counter
 
cnt = Counter(arr)
for k, v in cnt.items():
    pass

2) 딕셔너리로 카운팅

d = {}
for x in arr:
    d[x] = d.get(x, 0) + 1

3) 정렬 key 템플릿

# 단일 기준
arr.sort(key=lambda x: x[1])
 
# 복합 기준
arr.sort(key=lambda x: (x[0], -x[1]))

---

우선순위 큐 & 힙

1) 최소 힙 기본

import heapq
 
hq = []
heapq.heappush(hq, (priority, data))
priority, data = heapq.heappop(hq)

2) 최대 힙 (음수 변환)

import heapq
 
hq = []
heapq.heappush(hq, (-value, value))
max_value = heapq.heappop(hq)[1]

3) 작업 스케줄링 패턴 (도착 시간 + 소요시간)

jobs.sort()  # 도착 시간 기준 정렬
time = 0
idx = 0
import heapq
hq = []
 
while idx < len(jobs) or hq:
    while idx < len(jobs) and jobs[idx][0] <= time:
        start, duration = jobs[idx]
        heapq.heappush(hq, (duration, start))
        idx += 1
    if hq:
        duration, start = heapq.heappop(hq)
        time += duration
    else:
        time = jobs[idx][0]

---

투 포인터 (Two Pointers)

1) 두 수의 합 (정렬 필요)

arr.sort()
i, j = 0, len(arr) - 1
 
while i < j:
    s = arr[i] + arr[j]
    if s == target:
        # 정답 처리
        break
    if s < target:
        i += 1
    else:
        j -= 1

2) 슬라이딩 윈도우(연속 부분합, 고정 길이)

k = 3
window_sum = sum(arr[:k])
best = window_sum
 
for i in range(k, len(arr)):
    window_sum += arr[i] - arr[i - k]
    best = max(best, window_sum)

3) 슬라이딩 윈도우(연속 부분합, 가변 길이, 합 ≤ S)

left = 0
cur_sum = 0
ans = 0
 
for right in range(len(arr)):
    cur_sum += arr[right]
    while cur_sum > S:
        cur_sum -= arr[left]
        left += 1
    ans = max(ans, right - left + 1)

---

이분 탐색 (Binary Search)

1) 값 직접 찾기

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

2) lower_bound / upper_bound

from bisect import bisect_left, bisect_right
 
left = bisect_left(arr, x)       # x 이상 처음 위치
right = bisect_right(arr, x)     # x 초과 처음 위치
cnt = right - left

3) Parametric Search(정답 범위에 대한 이분 탐색)

def can(mid):
    # mid가 조건을 만족하면 True, 아니면 False
    return True
 
lo, hi = 0, MAX
ans = hi
while lo <= hi:
    mid = (lo + hi) // 2
    if can(mid):
        ans = mid
        hi = mid - 1   # 최소값 찾기
    else:
        lo = mid + 1

---

트리 / 그래프 기본

1) 인접 리스트 생성

graph = [[] for _ in range(n + 1)]
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)

2) 트리에서 부모 찾기 (DFS)

parent = [0] * (n + 1)
visited = [False] * (n + 1)
 
def dfs(x):
    visited[x] = True
    for nxt in graph[x]:
        if not visited[nxt]:
            parent[nxt] = x
            dfs(nxt)
 
dfs(1)

3) Union-Find (Disjoint Set)

parent = [i for i in range(n + 1)]
 
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
 
def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        if ra < rb:
            parent[rb] = ra
        else:
            parent[ra] = rb

4) Kruskal MST

edges.sort(key=lambda x: x[2])  # (u, v, w)
 
mst = 0
for u, v, w in edges:
    if find(u) != find(v):
        union(u, v)
        mst += w

---

구현 문제 팁 (문자열/좌표)

1) 문자열 자주 쓰는 패턴

s = s.strip()
s = s.replace("a", "b")
parts = s.split(":")
joined = "-".join(parts)

2) 좌표 시뮬레이션 기본

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
x, y = sx, sy
for cmd in commands:
    if cmd == "U":
        nx, ny = x - 1, y
    elif cmd == "D":
        nx, ny = x + 1, y
    # ...
    if 0 <= nx < n and 0 <= ny < m:
        x, y = nx, ny