Python 알고리즘 유형 및 대표 문제 총정리
업무에 잘 쓰이지는 않지만 SW 전문가라면 필수로 알아야 할 상식
각 알고리즘 별 설명
1. Two Pointers
정의: 배열의 양 끝이나 시작부터 두 개의 포인터를 움직이며 조건을 만족하는 쌍을 찾는 기법
활용: 정렬된 배열에서 합, 구간, 중복 쌍 등을 찾을 때
구현: left, right 포인터를 두고 조건에 따라 둘 중 하나를 이동시키며 탐색
2. Sliding Window
정의: 배열이나 문자열에서 일정 길이의 연속된 범위를 윈도우처럼 이동하며 최적해를 찾는 기법
활용: 고정/가변 길이 구간 내 최댓값, 합, 문자열 포함 여부
구현: 윈도우의 시작과 끝 인덱스를 조절하면서 합계나 빈도 등을 업데이트
3. BFS (Breadth-First Search)
정의: 그래프를 레벨 단위로 탐색하는 방법
활용: 최단 거리, 레벨 탐색, 상태 공간 탐색
구현: queue를 사용해 FIFO 방식으로 인접 노드를 순서대로 탐색
4. DFS (Depth-First Search)
정의: 그래프나 트리를 한 방향으로 끝까지 파고드는 방식으로 탐색
활용: 경로 찾기, 사이클 탐지, 조합/순열 생성
구현: 재귀 함수 또는 stack을 이용
5. Union-Find (Disjoint Set)
정의: 여러 원소가 같은 집합에 속하는지를 빠르게 확인하고 합칠 수 있는 자료구조
활용: 사이클 탐지, MST(최소 신장 트리), 집합 관리
구현: find, union 함수 사용 + 경로 압축(Path Compression) 최적화
6. Topological Sort
정의: 방향 그래프에서 선후 관계를 만족하는 순서를 찾는 정렬 방식
활용: 작업 순서, 빌드 순서, 의존성 해결
구현: 진입 차수가 0인 노드부터 순서대로 제거하며 정렬
7. Set / HashMap (collections)
정의: 중복 제거 또는 빠른 키 기반 조회를 위한 자료구조
활용: 빈도수 세기, 존재 여부 확인, 매핑
구현: Python의 set, dict 사용
8. Stack
정의: 후입선출(LIFO) 구조의 자료구조
활용: 괄호 파싱, 수식 계산, 백트래킹, 구간 최소/최대
구현: append, pop으로 Python 리스트로 구현 가능
9. Priority Queue / Heap
정의: 우선순위가 높은 요소를 빠르게 꺼낼 수 있는 큐
활용: 최소/최대값 유지, Dijkstra, K개 중 Top 요소 유지
구현: Python의 heapq 사용 (min-heap), (-val)로 max-heap 가능
10. Queue
정의: 선입선출(FIFO) 구조의 자료구조
활용: BFS, 캐시, 순차 처리
구현: collections.deque 또는 queue.Queue
11. Bottom-up DP
정의: 작은 문제부터 차례로 해결해 큰 문제를 푸는 방식
활용: 피보나치 수열, 배낭 문제, 문자열 편집 거리
구현: DP 테이블을 만들어 반복문으로 채워나감
12. Memoization (Top-down DP)
정의: 재귀 + 캐시를 통해 중복 계산을 줄이는 방식
활용: 조합/경로 개수, 재귀적 상태 전이
구현: 재귀 함수에 @lru_cache 혹은 dict로 캐시 추가
13. Tabulation
정의: DP 테이블을 완전히 채우는 Bottom-up DP의 다른 이름
활용: 상태 전이가 명확한 경우 선형/2D 테이블 구성
구현: 보통 반복문 사용
14. Binary Search
정의: 정렬된 배열에서 탐색 대상의 위치를 절반씩 좁혀가며 찾는 알고리즘
활용: 특정 값 탐색, 조건을 만족하는 최소/최대값 탐색
구현: 반복문 혹은 재귀로 low, mid, high 포인터 조절
15. Custom Comparator (정렬 기준 정의)
정의: 정렬 시 비교 기준을 사용자 정의하는 방식
활용: 특정 조건에 따른 정렬, 문자열/객체 정렬
구현: Python의 sorted에 key=lambda 전달
16. Backtracking
정의: 가능한 모든 후보를 탐색하되, 조건을 만족하지 않으면 돌아가는 방식
활용: 순열/조합, N-Queen, 의사결정 트리
구현: DFS + 조건 체크 + 상태 복원
17. Pruning
정의: 백트래킹 중 불필요한 탐색 경로를 조기에 차단하는 기법
활용: 시간 절약, 중복 제거
구현: 조건문으로 가지치기 로직 추가 (if 조건으로 건너뛰기)
1. Two Pointers
문제: Container With Most Water (LeetCode 11)
두 수직선이 x축에 그려져 있고, 그 사이에 물을 채울 수 있을 때, 가장 많은 물을 담을 수 있는 두 선을 구하세요.
def maxArea(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
Time Complexity: O(n)
Space Complexity: O(1)
2. Sliding Window
문제: Longest Substring Without Repeating Characters (LeetCode 3)
중복되지 않은 가장 긴 부분 문자열의 길이를 구하세요.
def lengthOfLongestSubstring(s):
char_set = set()
left = max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
Time Complexity: O(n)
Space Complexity: O(min(n, m)) (m: unique characters)
3. BFS
문제: Number of Islands (LeetCode 200)
1로 표시된 육지가 몇 개의 섬을 이루고 있는지 구하시오.
from collections import deque
def numIslands(self, grid: List[List[str]]) -> int:
n_row, n_col = len(grid), len(grid[0])
def bfs(r, c):
queue = deque([(r, c)])
while queue:
row, column = queue.popleft()
for dx, dy in [(-1,0), (0,-1), (1,0), (0,1)]:
new_row, new_column = row + dx, column + dy
if 0 <= new_row < n_row and 0 <= new_column < n_col and grid[new_row][new_column] == "1":
queue.append((new_row, new_column))
grid[new_row][new_column] = "0"
island = 0
for r in range(n_row):
for c in range(n_col):
if grid[r][c] == "1":
grid[r][c] = "0"
bfs(r, c)
island += 1
return island
Time Complexity: O(m * n)
Space Complexity: O(min(m, n))
4. DFS
문제: Clone Graph (LeetCode 133)
그래프의 모든 노드를 복사하시오.
def cloneGraph(node):
if not node:
return None
visited = {}
def dfs(n):
if n in visited:
return visited[n]
copy = Node(n.val)
visited[n] = copy
for nei in n.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node)
Time Complexity: O(N + E)
Space Complexity: O(N)
5. Union-Find
문제: Graph Valid Tree (LeetCode 261)
그래프가 트리인지 확인하시오 (사이클이 없어야 하며 연결되어 있어야 함).
def validTree(n, edges):
parent = [i for i in range(n)]
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
parent[px] = py
return True
for a, b in edges:
if not union(a, b):
return False
return len(edges) == n - 1
Time Complexity: O(n * α(n)) (α: inverse Ackermann)
Space Complexity: O(n)
6. Topological Sort (w/ Queue)
문제: Course Schedule II (LeetCode 210)
모든 과목을 수강할 수 있는 순서를 구하시오.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
indegree = [0] * numCourses
graph = defaultdict(list)
for dest, src in prerequisites:
graph[src].append(dest)
indegree[dest] += 1
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
for neighbor in graph[course]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else []
Time Complexity: O(V + E)
Space Complexity: O(V + E)
7. HashMap / Set
합이 target인 두 숫자의 인덱스를 반환하시오.
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_map = {}
for i in range(len(nums)): #O(n)
num_map[nums[i]] = i
for i in range(len(nums)): #O(n)
diff = target - nums[i]
if diff in num_map and num_map[diff] != i: #O(1)
return [i, num_map[diff]]
Time Complexity: O(n)
Space Complexity: O(n)
8. Stack Parsing
문제: Decode String (LeetCode 394)
압축된 문자열을 복원하세요. 예: "3[a2[c]]" → "accaccacc"
def decodeString(s):
stack = []
curr_num = 0
curr_str = ''
for c in s:
if c.isdigit():
curr_num = curr_num * 10 + int(c)
elif c == '[':
stack.append((curr_str, curr_num))
curr_str, curr_num = '', 0
elif c == ']':
last_str, num = stack.pop()
curr_str = last_str + num * curr_str
else:
curr_str += c
return curr_str
Time Complexity: O(n)
Space Complexity: O(n)
9. Priority Queue (Heap)
문제: Merge k Sorted Lists (LeetCode 23)
k개의 정렬된 리스트를 하나의 정렬 리스트로 합치세요.
import heapq
def mergeKLists(lists):
min_heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(min_heap, (node.val, i, node))
dummy = curr = ListNode(0)
while min_heap:
val, i, node = heapq.heappop(min_heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(min_heap, (node.next.val, i, node.next))
return dummy.next
Time Complexity: O(N log k)
Space Complexity: O(k)
10. Dynamic Programming (DP) - Bottom-Up
문제: House Robber (LeetCode 198)
인접한 집은 털 수 없을 때, 훔칠 수 있는 최대 금액을 구하시오.
def rob(nums):
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
dp = [0] * len(nums)
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
Time Complexity: O(n)
Space Complexity: O(n) → O(1)로도 최적화 가능
11. Memoization (Top-Down DP)
문제: Climbing Stairs (LeetCode 70)
한 번에 1칸 또는 2칸 오를 수 있을 때 n칸까지 오르는 방법의 수는?
from functools import lru_cache
@lru_cache(None)
def climbStairs(n):
if n <= 2:
return n
return climbStairs(n - 1) + climbStairs(n - 2)
Time Complexity: O(n)
Space Complexity: O(n)
12. Binary Search
문제: Find Minimum in Rotated Sorted Array (LeetCode 153)
회전된 정렬 배열에서 최솟값을 찾으세요.
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
Time Complexity: O(log n)
Space Complexity: O(1)
13. Custom Sort
문제: Sort Characters By Frequency (LeetCode 451)
문자열을 빈도 수로 정렬하시오.
from collections import Counter
def frequencySort(s):
count = Counter(s)
return ''.join(sorted(s, key=lambda c: (-count[c], c)))
Time Complexity: O(n log n)
Space Complexity: O(n)
14. Backtracking
주어진 집합의 모든 부분 집합을 구하시오.
def subsets(nums):
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return res
Time Complexity: O(2^n)
Space Complexity: O(n)
15. Backtracking with Pruning
문제: Palindrome Partitioning (LeetCode 131)
문자열을 palindrome 단위로 쪼개는 모든 조합을 구하시오.
def partition(s):
res = []
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start + 1, len(s) + 1):
if is_palindrome(s[start:end]):
path.append(s[start:end])
backtrack(end, path)
path.pop()
backtrack(0, [])
return res
Time Complexity: O(2^n)
Space Complexity: O(n)
