알고리즘 (Algorithms)¶
문제를 해결하기 위한 단계적 절차. LLM/VLM에서는 탐색, 샘플링, 최적화 등 다양한 알고리즘이 핵심적으로 사용됨.
왜 알고리즘을 알아야 하는가¶
- 효율성: O(n^2)와 O(n log n)의 차이는 데이터가 커질수록 극적
- 문제 해결 능력: 알고리즘 패턴을 알면 새로운 문제도 접근 가능
- 시스템 이해: LLM의 Beam Search, Top-k 샘플링 등은 알고리즘 지식 필수
- 면접: 코딩 테스트의 핵심
복잡도 분석¶
Big-O 표기법¶
최악의 경우 성능을 나타내는 점근적 표기법.
| 복잡도 | 이름 | n=10 | n=100 | n=1000 | n=10000 |
|---|---|---|---|---|---|
| O(1) | 상수 | 1 | 1 | 1 | 1 |
| O(log n) | 로그 | 3 | 7 | 10 | 13 |
| O(n) | 선형 | 10 | 100 | 1000 | 10000 |
| O(n log n) | 선형로그 | 33 | 664 | 9966 | 132877 |
| O(n^2) | 이차 | 100 | 10000 | 10^6 | 10^8 |
| O(2^n) | 지수 | 1024 | 10^30 | - | - |
| O(n!) | 팩토리얼 | 3.6M | - | - | - |
복잡도 계산 규칙:
# 1. 상수 무시
O(2n) = O(n)
O(500) = O(1)
# 2. 낮은 차수 무시
O(n^2 + n) = O(n^2)
# 3. 다른 변수는 분리
O(n + m) # n과 m이 독립적일 때
# 4. 중첩 반복문은 곱셈
for i in range(n): # O(n)
for j in range(m): # O(m)
pass # 총 O(n*m)
공간 복잡도:
# O(1) - 상수 공간
def sum_array(arr):
total = 0
for x in arr:
total += x
return total
# O(n) - 입력 크기에 비례
def copy_array(arr):
return arr[:] # n개 요소 복사
# O(n) - 재귀 호출 스택
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1) # 깊이 n
정렬 알고리즘 (Sorting)¶
비교 기반 정렬¶
| 알고리즘 | 평균 | 최악 | 공간 | 안정성 | 특징 |
|---|---|---|---|---|---|
| 버블 정렬 | O(n^2) | O(n^2) | O(1) | 안정 | 교육용 |
| 선택 정렬 | O(n^2) | O(n^2) | O(1) | 불안정 | 스왑 최소화 |
| 삽입 정렬 | O(n^2) | O(n^2) | O(1) | 안정 | 거의 정렬된 데이터에 효율적 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 안정 | 일정한 성능 |
| 퀵 정렬 | O(n log n) | O(n^2) | O(log n) | 불안정 | 실무에서 가장 빠름 |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 불안정 | 메모리 효율적 |
안정 정렬이란?
같은 키 값을 가진 요소들의 상대적 순서가 유지됨
예: [(A, 1), (B, 2), (C, 1)]을 두 번째 값으로 정렬
안정: [(A, 1), (C, 1), (B, 2)] # A가 C보다 앞에 유지
불안정: [(C, 1), (A, 1), (B, 2)] # 순서 바뀔 수 있음
퀵 정렬 (Quick Sort)¶
def quicksort(arr, low=0, high=None):
"""
분할 정복: 피벗 기준으로 분할 후 재귀 정렬
평균 O(n log n), 최악 O(n^2) - 피벗 선택에 따라
"""
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quicksort(arr, low, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, high)
def partition(arr, low, high):
"""Lomuto 파티션"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 간단한 버전 (메모리 비효율적이지만 이해 쉬움)
def quicksort_simple(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 quicksort_simple(left) + middle + quicksort_simple(right)
퀵 정렬 최적화:
# 1. 랜덤 피벗 선택 (최악 케이스 방지)
import random
pivot_idx = random.randint(low, high)
arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
# 2. 3-중앙값 피벗 (첫, 중간, 끝 중 중앙값)
def median_of_three(arr, low, high):
mid = (low + high) // 2
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
return mid
# 3. 작은 배열은 삽입 정렬로 전환
if high - low < 10:
insertion_sort(arr, low, high)
병합 정렬 (Merge Sort)¶
def mergesort(arr):
"""
분할 정복: 반으로 나누고, 정렬 후 병합
항상 O(n log n), 안정 정렬, 공간 O(n)
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(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
힙 정렬 (Heap Sort)¶
def heapsort(arr):
"""
힙 구성 후 루트(최대값)를 끝으로 이동 반복
O(n log n), in-place, 불안정
"""
n = len(arr)
# 최대 힙 구성 (아래에서 위로)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 하나씩 추출
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 최대값을 끝으로
heapify(arr, i, 0)
def heapify(arr, n, i):
"""최대 힙 속성 유지"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
비교 기반 정렬의 하한¶
비비교 정렬¶
특정 조건에서 O(n)으로 정렬 가능.
# 계수 정렬 (Counting Sort)
# 조건: 정수, 범위가 제한적
def counting_sort(arr, max_val):
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
result = []
for i, c in enumerate(count):
result.extend([i] * c)
return result
# 기수 정렬 (Radix Sort)
# 자릿수별로 정렬
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
LLM에서의 활용: - Top-k 토큰 선택 (부분 정렬) - 로그 확률 순 정렬 - 배치 정렬 (길이순)
탐색 알고리즘 (Search)¶
이진 탐색 (Binary Search)¶
정렬된 배열에서 O(log n) 탐색.
def binary_search(arr, target):
"""기본 이진 탐색"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # 오버플로우 방지
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def lower_bound(arr, target):
"""target 이상인 첫 번째 위치"""
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
def upper_bound(arr, target):
"""target 초과인 첫 번째 위치"""
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
bisect 모듈:
import bisect
arr = [1, 3, 5, 7, 9]
# lower_bound
idx = bisect.bisect_left(arr, 5) # 2
# upper_bound
idx = bisect.bisect_right(arr, 5) # 3
# 삽입하면서 정렬 유지
bisect.insort(arr, 4) # [1, 3, 4, 5, 7, 9]
이진 탐색 응용:
# 1. 회전 정렬 배열에서 검색
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 왼쪽이 정렬됨
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# 오른쪽이 정렬됨
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# 2. 최솟값/최댓값 찾기 (이진 탐색 on answer)
def min_days_to_make_bouquets(bloomDay, m, k):
"""
m개의 꽃다발, 각각 k개 연속 꽃 필요
가능한 최소 일수 찾기
"""
def can_make(days):
bouquets = flowers = 0
for bloom in bloomDay:
if bloom <= days:
flowers += 1
if flowers == k:
bouquets += 1
flowers = 0
else:
flowers = 0
return bouquets >= m
if len(bloomDay) < m * k:
return -1
left, right = min(bloomDay), max(bloomDay)
while left < right:
mid = (left + right) // 2
if can_make(mid):
right = mid
else:
left = mid + 1
return left
Beam Search¶
LLM 디코딩에서 핵심적으로 사용되는 탐색 알고리즘.
import torch
import torch.nn.functional as F
def beam_search(model, input_ids, beam_width=5, max_length=50):
"""
Beam Search 디코딩
- 매 스텝 상위 beam_width개 시퀀스 유지
- 다양성과 품질의 균형
"""
device = input_ids.device
# 초기 빔: [(log_prob, sequence)]
beams = [(0.0, input_ids[0].tolist())]
completed = []
for _ in range(max_length):
all_candidates = []
for score, seq in beams:
# 이미 종료된 시퀀스
if seq[-1] == model.config.eos_token_id:
completed.append((score, seq))
continue
# 다음 토큰 확률 계산
input_tensor = torch.tensor([seq], device=device)
with torch.no_grad():
outputs = model(input_tensor)
logits = outputs.logits[:, -1, :]
log_probs = F.log_softmax(logits, dim=-1)
# Top-k 후보 추출
top_k_probs, top_k_ids = torch.topk(log_probs[0], beam_width)
for log_prob, token_id in zip(top_k_probs, top_k_ids):
new_seq = seq + [token_id.item()]
# 길이 정규화 (선택적)
new_score = score + log_prob.item()
all_candidates.append((new_score, new_seq))
# 상위 beam_width개 선택
beams = sorted(all_candidates, key=lambda x: x[0], reverse=True)[:beam_width]
# 모든 빔이 종료되면 중단
if all(seq[-1] == model.config.eos_token_id for _, seq in beams):
break
# 완료된 것과 진행 중인 것 합쳐서 최고 점수 반환
all_seqs = completed + beams
best = max(all_seqs, key=lambda x: x[0] / len(x[1])) # 길이 정규화
return best[1]
Beam Search의 문제점:
1. 반복 생성: 같은 문구 반복
-> n-gram 패널티, 반복 토큰 점수 감소
2. 다양성 부족: 비슷한 시퀀스들만 유지
-> Diverse Beam Search, 그룹별 다양성 강제
3. 길이 편향: 짧은 시퀀스에 높은 점수
-> 길이 정규화: score / len(seq)^alpha
A* 탐색¶
휴리스틱을 활용한 최적 경로 탐색.
import heapq
def astar(start, goal, neighbors, heuristic, cost):
"""
A* 알고리즘
f(n) = g(n) + h(n)
- g(n): 시작부터 n까지 실제 비용
- h(n): n부터 목표까지 추정 비용 (휴리스틱)
"""
open_set = [(heuristic(start, goal), 0, start, [start])]
closed_set = set()
while open_set:
f, g, current, path = heapq.heappop(open_set)
if current == goal:
return path
if current in closed_set:
continue
closed_set.add(current)
for neighbor in neighbors(current):
if neighbor in closed_set:
continue
new_g = g + cost(current, neighbor)
new_f = new_g + heuristic(neighbor, goal)
new_path = path + [neighbor]
heapq.heappush(open_set, (new_f, new_g, neighbor, new_path))
return None # 경로 없음
# 예시: 그리드에서 최단 경로
def manhattan_distance(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def grid_neighbors(pos, grid):
x, y = pos
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
if grid[nx][ny] != '#': # 벽이 아니면
yield (nx, ny)
동적 프로그래밍 (Dynamic Programming)¶
복잡한 문제를 부분 문제로 나누어 해결. 중복 계산을 메모이제이션으로 방지.
핵심 조건¶
- 최적 부분 구조 (Optimal Substructure): 최적해가 부분 문제의 최적해로 구성
- 중복 부분 문제 (Overlapping Subproblems): 동일한 부분 문제가 반복
Top-Down (메모이제이션) vs Bottom-Up (타뷸레이션)¶
# 피보나치 - Top-Down (재귀 + 캐싱)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_topdown(n):
if n <= 1:
return n
return fib_topdown(n - 1) + fib_topdown(n - 2)
# 피보나치 - Bottom-Up (반복)
def fib_bottomup(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 공간 최적화 (O(1) 공간)
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
대표 문제들¶
편집 거리 (Edit Distance / Levenshtein Distance)¶
두 문자열 간의 최소 편집 연산 수.
def edit_distance(s1, s2):
"""
dp[i][j] = s1[0:i]와 s2[0:j]의 편집 거리
연산: 삽입, 삭제, 교체
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 초기화: 빈 문자열과의 거리
for i in range(m + 1):
dp[i][0] = i # i번 삭제
for j in range(n + 1):
dp[0][j] = j # j번 삽입
# DP 테이블 채우기
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] # 같으면 연산 불필요
else:
dp[i][j] = 1 + min(
dp[i-1][j], # 삭제
dp[i][j-1], # 삽입
dp[i-1][j-1] # 교체
)
return dp[m][n]
# 예시
print(edit_distance("kitten", "sitting")) # 3
LLM에서의 활용: 텍스트 유사도, 오타 교정
최장 공통 부분 수열 (LCS)¶
def lcs_length(s1, s2):
"""
dp[i][j] = s1[0:i]와 s2[0:j]의 LCS 길이
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def lcs_string(s1, s2):
"""실제 LCS 문자열 추출"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 역추적
result = []
i, j = m, n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
result.append(s1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
0/1 배낭 문제 (Knapsack)¶
def knapsack(weights, values, capacity):
"""
dp[i][w] = i번째 아이템까지 고려, 용량 w일 때 최대 가치
"""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# 선택 안함
dp[i][w] = dp[i-1][w]
# 선택함 (용량 가능하면)
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][capacity]
# 공간 최적화 (1D DP)
def knapsack_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# 역순 순회 (같은 아이템 중복 선택 방지)
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
최장 증가 부분 수열 (LIS)¶
# O(n^2) 방법
def lis_n2(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # dp[i] = nums[i]로 끝나는 LIS 길이
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# O(n log n) 방법 - 이진 탐색 활용
def lis_nlogn(nums):
from bisect import bisect_left
tails = [] # tails[i] = 길이 i+1인 LIS의 마지막 원소 중 최솟값
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
DP 문제 접근법¶
1. 상태 정의
- dp[i]가 무엇을 의미하는지 명확히
- 필요한 차원 결정 (1D, 2D, ...)
2. 점화식 찾기
- 현재 상태를 이전 상태들로 표현
- 작은 예시로 패턴 찾기
3. 초기값 설정
- 베이스 케이스 정의
4. 순서 결정
- Top-Down: 재귀 + 메모이제이션
- Bottom-Up: 작은 것부터 큰 것으로
5. 공간 최적화
- 필요한 이전 상태만 유지
그리디 알고리즘 (Greedy)¶
각 단계에서 최적의 선택을 하는 방식. 전역 최적을 보장하지 않지만 효율적.
그리디가 최적인 경우¶
- 그리디 선택 속성: 현재 최선의 선택이 전체 최선으로 이어짐
- 최적 부분 구조: 부분 문제의 최적해가 전체 최적해의 일부
대표 문제들¶
# 1. 활동 선택 문제 (Activity Selection)
def activity_selection(activities):
"""
종료 시간 기준 정렬 후, 겹치지 않는 최대 활동 선택
"""
# (시작, 종료) 쌍을 종료 시간 기준 정렬
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# 2. 동전 교환 (특정 조건에서만 그리디 최적)
def coin_change_greedy(coins, amount):
"""
큰 동전부터 사용 (동전이 배수 관계일 때만 최적)
예: [1, 5, 10, 25] - 최적
예: [1, 3, 4] - 비최적 (6 = 3+3, 그리디는 4+1+1)
"""
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount == 0:
break
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# 3. 분할 가능 배낭 (Fractional Knapsack)
def fractional_knapsack(items, capacity):
"""
가치/무게 비율로 정렬 후 담기
items: [(weight, value), ...]
"""
# 비율 기준 내림차순 정렬
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total_value = 0
for weight, value in items:
if capacity >= weight:
capacity -= weight
total_value += value
else:
# 일부만 담기
total_value += (capacity / weight) * value
break
return total_value
LLM에서의 그리디 디코딩¶
def greedy_decode(model, input_ids, max_length=50):
"""
매 스텝 최고 확률 토큰 선택
장점: 빠름, 결정론적
단점: 다양성 부족, 반복 생성
"""
generated = input_ids.tolist()
for _ in range(max_length):
input_tensor = torch.tensor([generated])
with torch.no_grad():
logits = model(input_tensor).logits[:, -1, :]
next_token = torch.argmax(logits, dim=-1).item()
generated.append(next_token)
if next_token == model.config.eos_token_id:
break
return generated
샘플링 알고리즘¶
LLM 텍스트 생성의 핵심.
온도 (Temperature)¶
확률 분포의 날카로움 조절.
def apply_temperature(logits, temperature):
"""
T < 1: 분포가 날카로워짐 (확신 증가, 다양성 감소)
T = 1: 원본 분포
T > 1: 분포가 평평해짐 (다양성 증가, 품질 저하 가능)
"""
return logits / temperature
Top-k Sampling¶
상위 k개 토큰에서만 샘플링.
def top_k_sampling(logits, k=50, temperature=1.0):
"""
상위 k개 외의 토큰 확률을 0으로 설정
"""
logits = logits / temperature
# Top-k 외 마스킹
top_k_values, top_k_indices = torch.topk(logits, k)
# 새로운 분포 생성
probs = F.softmax(top_k_values, dim=-1)
# 샘플링
idx = torch.multinomial(probs, num_samples=1)
return top_k_indices[idx]
Top-p (Nucleus) Sampling¶
누적 확률이 p를 초과하는 최소 집합에서 샘플링.
def top_p_sampling(logits, p=0.9, temperature=1.0):
"""
확률 상위부터 누적합이 p를 넘을 때까지만 포함
적응적: 확률 분포에 따라 토큰 수가 달라짐
"""
logits = logits / temperature
probs = F.softmax(logits, dim=-1)
# 확률 내림차순 정렬
sorted_probs, sorted_indices = torch.sort(probs, descending=True)
# 누적 확률 계산
cumsum_probs = torch.cumsum(sorted_probs, dim=-1)
# p 초과하는 토큰 마스킹 (첫 번째 초과 토큰은 유지)
mask = cumsum_probs - sorted_probs > p
sorted_probs[mask] = 0.0
# 재정규화
sorted_probs = sorted_probs / sorted_probs.sum()
# 샘플링
idx = torch.multinomial(sorted_probs, num_samples=1)
return sorted_indices[idx]
반복 패널티¶
def apply_repetition_penalty(logits, generated_ids, penalty=1.2):
"""
이미 생성된 토큰의 확률을 낮춤
"""
for token_id in set(generated_ids):
if logits[token_id] > 0:
logits[token_id] /= penalty
else:
logits[token_id] *= penalty
return logits
분할 정복 (Divide and Conquer)¶
문제를 작은 부분으로 분할하여 해결 후 결합.
대표 예시¶
# 거듭제곱 - O(log n)
def power(base, exp):
if exp == 0:
return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half
else:
return base * power(base, exp - 1)
# 최대 부분 배열 합 (Kadane's Algorithm - O(n)도 가능)
def max_subarray_dc(nums, left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
# 왼쪽, 오른쪽, 중간 걸치는 것 중 최대
left_max = max_subarray_dc(nums, left, mid)
right_max = max_subarray_dc(nums, mid + 1, right)
cross_max = max_crossing_subarray(nums, left, mid, right)
return max(left_max, right_max, cross_max)
def max_crossing_subarray(nums, left, mid, right):
# 중간에서 왼쪽으로 확장
left_sum = float('-inf')
curr_sum = 0
for i in range(mid, left - 1, -1):
curr_sum += nums[i]
left_sum = max(left_sum, curr_sum)
# 중간에서 오른쪽으로 확장
right_sum = float('-inf')
curr_sum = 0
for i in range(mid + 1, right + 1):
curr_sum += nums[i]
right_sum = max(right_sum, curr_sum)
return left_sum + right_sum
LLM에서의 활용: - 긴 문서의 분할 처리 - MapReduce 패턴 - 병렬 어텐션 계산
그래프 알고리즘¶
위상 정렬 (Topological Sort)¶
DAG(방향 비순환 그래프)의 선형 순서화.
from collections import deque
def topological_sort_kahn(graph):
"""
Kahn's Algorithm (BFS 기반)
graph: {node: [neighbors]}
"""
# 진입 차수 계산
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
# 진입 차수 0인 노드로 시작
queue = deque([node for node in in_degree if in_degree[node] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph.get(node, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 사이클 감지
if len(result) != len(in_degree):
return None # 사이클 존재
return result
def topological_sort_dfs(graph):
"""DFS 기반 위상 정렬"""
visited = set()
result = []
def dfs(node):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
result.append(node) # 후위 순서로 추가
for node in graph:
if node not in visited:
dfs(node)
return result[::-1] # 역순
최단 경로¶
# 다익스트라 (이미 위에서 다룸)
# 벨만-포드 (음수 가중치 허용)
def bellman_ford(graph, start, n):
"""
graph: [(u, v, weight), ...]
음수 사이클 감지 가능
"""
dist = [float('inf')] * n
dist[start] = 0
# n-1번 반복
for _ in range(n - 1):
for u, v, w in graph:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 음수 사이클 감지
for u, v, w in graph:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # 음수 사이클 존재
return dist
# 플로이드-워셜 (모든 쌍 최단 경로)
def floyd_warshall(graph, n):
"""
O(n^3), 모든 노드 쌍 간 최단 거리
"""
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in graph:
dist[u][v] = w
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Union-Find (Disjoint Set)¶
집합의 합치기와 찾기 연산을 효율적으로 수행.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
"""경로 압축"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""랭크 기반 합치기"""
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
핵심 개념¶
자주 나오는 질문¶
- 시간 복잡도가 O(n log n)인 정렬 알고리즘의 원리
- 퀵 정렬: 피벗 기준 분할, 평균 O(n log n)
-
병합 정렬: 분할 후 병합, 항상 O(n log n)
-
퀵 정렬의 최악 케이스와 해결법
- 이미 정렬된 배열 + 첫/끝 피벗 -> O(n^2)
-
해결: 랜덤 피벗, 3-중앙값 피벗
-
DP와 그리디의 차이
- DP: 모든 부분 문제 해결, 최적해 보장
-
그리디: 현재 최선만 선택, 최적해 미보장 (특정 조건에서만)
-
이진 탐색 구현 시 주의점
- 무한 루프 방지: left < right vs left <= right
-
오버플로우: mid = left + (right - left) // 2
-
다익스트라 vs 벨만-포드
- 다익스트라: O(E log V), 음수 가중치 불가
- 벨만-포드: O(VE), 음수 가중치 가능, 음수 사이클 감지
코딩 테스트 접근법¶
1. 문제 이해
- 입력/출력 형식
- 제약 조건 (n의 범위로 복잡도 추정)
2. 예제 분석
- 손으로 풀어보기
- 패턴 찾기
3. 알고리즘 선택
- n <= 20: 완전 탐색, 백트래킹
- n <= 1000: O(n^2)
- n <= 10^5: O(n log n) 또는 O(n)
- n <= 10^7: O(n)
4. 구현
- 엣지 케이스 고려
- 디버깅용 출력
5. 검증
- 예제 테스트
- 경계값 테스트