[Python] 알고리즘 상태 다이어그램 (Algorithm Phase Diagram) : 메모리 사용량, 실행 속도, 시간 복잡도로 비교하는 알고리즘 18종

이번에는 실무와 코딩 테스트에서 특히 자주 등장하는 핵심 알고리즘 패턴 5가지를 중심으로 정리해보겠습니다. 단순히 개념만 나열하는 것이 아니라, 이 5가지를 기준으로 실행 속도, 시간 복잡도, 메모리 사용량, 다른 알고리즘들과의 관계까지 종합하여 비교해보고자 합니다. 이 글에서는 "어떤 문제, 상황에서 어떤 알고리즘을 선택해야 하는지"를 한눈에 알아볼 수 있는 실전용 사고의 기준을 세우는 것이 목표입니다.
 

1. 핵심 알고리즘 5가지

• 탐욕 알고리즘 (Greedy)
• 투 포인터 (Two Pointer)
• 슬라이딩 윈도우 (Sliding Window)
• 백트래킹 (Backtracking)
• 분할 정복 (Divide & Conquer)

☞ 우선 각 알고리즘의 정의, 동작 원리, 복잡도, 장점/단점, 대표 문제 예시를 표로써 비교 정리해봅시다.

구분	탐욕 알고리즘 Greedy Algorithm	투 포인터 Two Pointer	슬라이딩 윈도우 Sliding Window	백트래킹 Backtracking	분할 정복 Divide & Conquer
정의	매 단계 상황에서 가장 최적의 선택을 반복하는 방식으로써, 국소적으로 최적의 선택을 반복하여 전역적인 최적의 해답에 근접하기를 기대하는 기법.	주로 정렬된 배열이나 연결 리스트에서 두 개의 포인터(인덱스)를 사용하여 특정 조건을 만족하는 쌍이나 구간을 찾는 기법.	배열이나 문자열 같은 순차적인 데이터에서 고정된 크기 또는 가변적인 크기의 구간를 유지하며 왼쪽, 오른쪽으로 동시키면서 해당 구간(윈도우) 내의 데이터를 처리하는 기법.	해를 찾기 위해 모든 가능한 경로(경우의 수)를 재귀적으로 탐색하다가, 해답이 될 가능성이 없는 경로는 버리고 즉시 이전 단계로 되돌아가(가지치기) 다른 경로를 탐색하는 기법.	주어진 문제를 더 이상 쪼갤 수 없을 때까지 작은 하위 문제로 재귀적으로 분할하고, 각각의 하위 문제를 해결한 뒤, 그 해답들을 결합하여 원래 문제의 해답을 구하는 기법.
동작 원리	전역 최적해를 분해 가능한 경우, 각 단계에서 가장 유리한 선택을 하면 전체도 최적에 가까워진다는 가정에 기반함.	왼쪽, 오른쪽 두 포인터를 이동하며 구간 길이를 줄이거나 늘려 가면서 조건(합, 차이, 개수 등)을 만족하는 지점을 찾음.	현재 윈도우(window)에 포함된 값들을 누적/통계로 관리하면서, 오른쪽을 확장, 왼쪽을 축소해가며 최적의 구간을 찾음.	"현재 선택 → 다음 단계 재귀 호출" 구조로 모든 조합과 배치를 시도하고, 유망하지 않은 경로는 즉시 되돌아감(backtrack)	문제를 절반씩 나누어 재귀 호출로 해결 예: 배열을 반씩 쪼갠 뒤 정렬하고 병합
시간복잡도 (Big-O)	대부분의 경우 O(n) 또는 O(n log n) - 정렬 후 Greedy, 스패닝 트리(Kruskal: O(E log V))	O(n) - 배열 한 번(또는 두 번) 훑으면서 포인터만 이동	O(n) - 윈도우의 양 끝이 각각 배열을 한 번씩만 지나감	보통 O(b^d) (분기 수 b, 깊이 d) → 지수 시간까지 치솟기 쉬움	대표적으로 O(n log n) (Merge/Quick 계열), 분할 비대칭, 안 좋은 피벗이면 O(n²)까지 악화 가능
공간복잡도 (대략)	대개 O(1) ~ O(n) - 정렬/우선순위 큐 사용 여부에 의존함.)	O(1) - 인덱스 두 개만 추가로 사용	O(1) - 윈도우 경계, 누적 값 등만 유지	최악 O(b*d) - 재귀 호출 스택 + 상태 저장량이 매우 큼	재귀 깊이 O(log n) + 보조 배열 예: Merge Sort에서 O(n)
장점	> 빠르고 구현이 간단하고 직관적임 > 실무 그리디 휴리스틱에 많이 쓰임	> 구현이 쉽고 매우 빠르며, 메모리를 거의 쓰지 않음. > O(N)의 시간 복잡도로 문제를 효율적으로 해결함.	연속 구간(부분합, 평균, 빈도) 문제에서 거의 최적의 선택임.	해가 존재하면 반드시 찾을 수 있고, 가지치기를 잘하면 실용 속도로 떨어뜨릴 수 있음.	코드 구조가 명확하고, 다른 알고리즘(정렬, 탐색, DP)의 기반이 되는 패턴.
단점	전역 최적해가 보장되지 않는 문제에 적용하면 그럴듯한 오답을 정답으로 내놓는 위험	배열이 정렬돼 있거나 단조 구조가 있어야 하고, 대부분 1D 연속 데이터에 한정.	불연속 집합 (예: 집합에서 임의 k개 선택)에는 바로 적용할 수 없음.	상태 공간이 크면 현실적으로 시간, 메모리 모두 감당 불가.	재귀 호출 오버헤드와 구현 난이도, 잘못된 분할로 인한 성능 저하
대표 문제 예시	> 동전 거스름돈 문제 (가장 큰 단위부터 거슬러 주는 방식), 활동 선택(Interval Scheduling), 최소 신장 트리(MST), 최소 스패닝 트리(Kruskal)	> 두 수의 합, 정렬된 배열에서 합이 target인 쌍 찾기, 물통 문제 등 양쪽에서 좁혀가는 탐색.	> 최대 부분 배열 합 구하기, 고정 길이의 평균 최대 구간, 특정 길이의 부분 문자열에서 중복 없는 문자 찾기.	> N-Queen, 순열/조합 생성, 부분집합 나열, 스도쿠 풀이, 조합 생성, 순열 생성 등 "모든 배치/조합" 문제	> 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search), 행렬 곱셈, Karatsuba 곱셈 등 "재귀 분할 + 합병" 구조 문제

 

2. 시간 복잡도와 메모리 사용량이 중요한 이유

실무에서 알고리즘을 선택한다는 것은 결국 제한된 시간과 메모리 안에서 해답을 찾는 전략을 선택하는 일입니다.

• 시간 복잡도: 입력 크기 n이 커질수록 연산 횟수가 어떻게 증가하는지 보여줍니다.
  → 같은 문제라도 O(n²) 대신 O(n log n)을 쓰면, 데이터가 10배로 커질 때 실행 시간 차이가 수십 ~ 수백 배까지 벌어질 수 있습니다.
  
  
• 공간 복잡도: DP 테이블, 해시 테이블, 캐시 등 추가 메모리를 얼마나 쓰는지 나타냅니다.
  → 속도를 위해 메모리를 더 쓰는지, 메모리를 아끼는 대신 속도가 느린 방식을 쓰는지를 결정해야 합니다.

실제 실행 시간은 프로그래밍 언어, 구현 상수, 캐시, 디스크 I/O 등에도 영향을 받지만, 입력이 충분히 커지면 시간 복잡도가 전체적인 성장 추세를 거의 결정합니다. 그래서 이 글은 핵심 5개 알고리즘을 먼저 구조적으로 이해한 뒤, 이를 기준으로 나머지 알고리즘들을 Phase Diagram(상태 다이어그램)과 비교 표로 정리하고자 합니다.
 
 

3. 알고리즘 상태 다이어그램 : 메모리 사용량 vs 실행 속도

알고리즘은 단순히 속도만으로 비교할 수 없습니다. 알고리즘 문제(백준/프로그래머스/LeetCode)를 해결하려면:

• 실행 속도 : 시간 복잡도
• 메모리 사용량 : 공간 복잡도
• 알고리즘 간 개념적 관계 : 패턴/발전 흐름

을 연관지어서 이해해야 합니다.
 
이를 위해 이번 글에서는 18개 알고리즘들을 다음 두 가지 관점으로 정리해보겠습니다.

• Algorithm Phase Diagram(알고리즘 상태 다이어그램)
  → 성능(연산 속도 × 메모리 사용량)으로 구성된 "알고리즘 상태 다이어그램"
  
  
• Algorithm Relationship Graph(알고리즘 관계도)
  → 알고리즘 간 개념적 연결과 발전 흐름을 한눈에 보여주는 “관계도”

그리고 핵심 알고리즘 5종(탐욕Greedy, 투 포인터 Two Pointer, Sliding Window, Backtracking, 분할 정복 Divide & Conquer)을 중심으로 문제 해결 전략까지 정리해보겠습니다.
 
 

3-1. 상태 다이어그램의 이론적 근거

알고리즘 상태 다이어그램의 가로 x축(메모리 사용량), 세로 y축(실행 속도)은 임의적 기준에 기반한 것이 아닌, MIT CLRS·Princeton Sedgewick 등 공신력 있는 자료에서 제시된 시간 복잡도 및 공간 복잡도 모델을 기반으로 상대적인 수치를 Mapping한 것입니다.

☞  x축, y축을 각각 2단계 기준선에서 나누어 4분면으로 표현했습니다.

FAST & LIGHT : 좌상단 (x↓, y↑) → 실행 속도가 빠른데(FAST) 메모리를 거의 안 씀(LIGHT) - Binary Search, Linear Search - Two Pointer, Sliding Window, Greedy	FAST but HEAVY : 우상단 (x↑, y↑) → 빠르지만 메모리를 많이 사용함(HEAVY) - Hash Table, 탐색(DFS/BFS) - 일부 DP(1D DP)
SLOW but LIGHT : 좌하단 (x↓, y↓) → 느리지만(SLOW) 메모리는 매우 적게 사용(LIGHT) - Bubble Sort, Selection Sort, Insertion Sort	SLOW & HEAVY : 우하단 (x↑, y↓) → 느리고 메모리를 많이 사용함. 일반적으로 어려운 문제를 풀 때 쓰임. - 2D DP, Backtracking

 

• x축 : Memory Usage (메모리 사용량)

x값 구간	의미	공간 복잡도	대표 알고리즘	참고
0.8~1.2	very low	O(1)	Linear Search, Two Pointer	ref.[2]
1.2~1.8	low	O(log n)	Binary Search, D&C stack	ref.[1]
2.0~2.4	normal	O(n)	Merge Sort 보조배열, 해시	ref.[3]
2.5~3.2	high	O(n), O(n²)	DP 테이블(1D/2D)	ref.[1]
3.2 이상	very high	O(n^d), 지수적	Backtracking	ref.[4]

 

• y축 : Runtime Speed (실행 속도)

y값 구간	의미	시간 복잡도	근거	참고
0.5~1.0	very slow	O(n^d)	연산 폭증 (Backtracking)	ref.[4]
1.0~1.9	slow	O(n²)	비교 기반 정렬(Bubble/Selection)	ref.[2]
2.0~2.9	normal	O(n log n)	Merge/Quick-like 재귀	ref.[3]
3.0~3.7	fast	O(n), O(n log n)	Greedy / Two-pointer	ref.[1],[2]
3.8~4.0	very fast	O(log n), O(n)	로그 탐색, 선형 스캔	ref.[1],[2]

 
각 알고리즘의 상대 좌표는 시간/공간 복잡도 분석을 구간으로 나누어 선형 스케일링해서 배치한 것입니다. 공식적인 복잡도 정의와 비교 자료는 다음 문헌을 참고했습니다.
 

• [ref1] MIT CLRS - Introduction to Algorithms
• https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• [ref2] Princeton Algorithms (Sedgewick & Wayne)
• https://algs4.cs.princeton.edu/home/
• [ref3] Sorting Complexity Analysis
  https://algs4.cs.princeton.edu/20sorting/
• [ref4] Backtracking & NP-Complete Research
  https://epubs.siam.org/doi/10.1137/0208012

 
각 문헌에서 제시하는 시간 복잡도 및 공간 복잡도 테이블을 바탕으로, "매우 빠름 - 빠름 - 보통 - 느림 - 매우 느림" 과 "매우 낮음 - 낮음 - 보통 - 높음 - 매우 높음" 을 0 ~ 4 범위의 상대 좌표로 끌어온 것이라고 이해하면 됩니다.
 
이렇게 하면, 속도-메모리에 대한 알고리즘의 상관관계를 직관적으로 비교할 수 있고, 특정 문제에 직면했을 때 "현재 상황에서 어느 것을 더 희생해도 되는가?"를 보다 쉽고 빠르게 판단할 수 있습니다.

3-2. 상태 다이어그램의 의미, 해석

파이썬을 활용하여, 각 알고리즘의 메모리 사용량(Memory usage), 실행 속도(Runtime speed)를 시간 복잡도(Time complexity)를 기준으로 각 알고리즘의 특징을 하나의 다이어그램 (Algorithm Phase Diagram)으로 구성하여 비교, 정리할 수 있습니다.

 
우선, 다이어그램의 알고리즘에 대한 정보를 축약한 라벨창들을 설명하고자 합니다.
 

▶ 첫 번째 라벨창 : Algorithm family (color)

같은 색은 같은 사고방식 및 문제 패턴을 공유하는 그룹 즉 Family를 의미합니다.
 

• 파랑색 : Searching / traversal
  → Linear Search, Binary Search, DFS, BFS
  → 배열/리스트 또는 그래프/트리에서 원소/경로를 찾는 역할
  
  
• 주황색: Pointer / window / Greedy
  → Greedy, Two Pointer, Sliding Window
  → 연속 구간 / 최적 부분 구조를 빠르고 메모리 적게 다루는 패턴 기반 기법
  
  
• 초록색: Sorting algorithms
  → Bubble, Selection, Insertion, Heap, Quick, Merge
  → 컬렉션을 정렬하는 알고리즘 계열
  
  
• 보라색 (Hash / table based)
  → Hash Table
  → Key : Value 매핑, 평균 O(1) 검색/삽입을 목표로 하는 구조
  
  
• 빨강색 (DP / Divide & Conquer)
  → Divide & Conquer, 1D DP, 2D DP (1D는 1차원, 2D는 2차원 *Dimension)
  → 큰 문제를 작은 하위 문제로 나누고, 하위 해결 결과를 재활용하는 계열
  
  
• 검정색 (Backtracking)
  → Backtracking
  → 완전 탐색과 가지치기로 답(해) 공간 탐색(search in state space)을 수행

 

▶ 두 번째 라벨창 : Time complexity (marker)

 

마커의 모양, 채움 여부(채워짐/비어 있음)로 시간 복잡도 수준을 구분했습니다. 다이어그램 그래프에서는 색 = 패밀리(그룹), 모양/채움 = 시간 복잡도 레벨을 동시에 표현하도록 설계했습니다. 또한 같은 모양의 마커도 채워진/빈 것들로 차이를 두어서 "실전에서 특히 더 무거운 편인지(heavy)"를 직관적으로 구분할 수 있게했습니다.

• 동그라미(●, ○) → 선형 O(n) 계열
• 다이아몬드(◆, ◇) → 상수 O(1) / 그래프 선형 O(V+E) 계열
• 별(★, ☆) → 로그/준선형 O(log n), O(n log n) 계열
• 네모(□, ■) → 제곱 O(n²) 및 고차 다항식 O(nᵈ) 같은 “무거운 다항식” 계열

그리고 가벼운 알고리즘(O(1), O(log n))에서 무거운 알고리즘(O(n²), O(n^d))으로 가면서 복잡도가 증가하는 순서로, 즉 시간 복잡도가 낮은 것에서 높은 것 순서로 마커의 순서를 배치했습니다.

 

• ◆ (다이아몬드) → O(1) avg
  → 평균 상수 시간 접근 : Hash Table 평균 조회
  
  
• ★ (별) → O(log n)
  → 로그 시간: 탐색 범위를 절반씩 줄이는 계열 : Binary Search
  
  
• ◇ (빈 다이아몬드) → O(V+E)
  → 정점/간선 개수에 선형인 그래프 탐색 : DFS, BFS
  
  
• ● (동그라미) → O(n)
  → 선형 시간: 데이터 전체를 1~2번 도는 계열 : Greedy, Two Pointer, Sliding Window, 1D DP, Linear Search 등
  
  
• ○ (빈 동그라미) → O(n) ~ O(n log n)
  → 보통은 O(n) 수준이지만, 정렬/전처리, 추가 구조에 따라 O(n log n)까지 올라갈 수 있는 "중간급" 복잡도.
  
  
• ☆ (빈 별) → O(n log n)
  → 고급 정렬/분할: Merge Sort/Quick Sort/Heap Sort, Divide & Conquer 패턴
  
  
• □ (빈 네모) → O(n²)
  → 쌍 비교 혹은 이중 반복문: Bubble/Selection/Insertion Sort
  
  
• ■ (네모) → O(n^d) / heavy 
  → 2D, 3D DP 같은 다차원 DP, 또는 상태 폭발이 심한 구조(MEM heavy) (2D DP, 일부 Backtracking 근사)

 

▶ 세 번째 라벨창 : Relationships (lines)

세 번째 라벨창은 실선 또는 점선으로 알고리즘 간에 개념-사용 패턴 연결을 보여줍니다. 즉 그 선들은 실제 성능 곡선이 아니라 "어떤 알고리즘이 어떤 알고리즘의 아이디어를 계승, 확장했는지"를 보여주는 개념적 연결 관계를 의미합니다.

• 파란 실선 : Searching / traversal relations
  → Linear Search ↔ Binary Search: 같은 “탐색”이지만 데이터 "정렬 X 전부 훑기 vs 정렬 O 절반씩 줄이기".
  → DFS ↔ BFS: 같은 그래프 탐색이지만 "깊이 우선 vs 너비 우선이라는 전략 차이"를 묶은 것.
  
  
• 주황 점선 : Pointer / window / Greedy pattern
  → Two Pointer → Sliding Window → Greedy
  → 인덱스 두 개로 구간 다루며, 구간을 "윈도우"로 유지하며 이동하고, 그 상태에서 매번 최선 선택(Greedy)으로 사고가 확장되는 흐름.
  
  
• 초록 긴 점선 : Sorting evolution (O(n²) → O(n log n))
  → Bubble/Selection/Insertion, Heap/Quick/Merge
  → 단순 이중 O(n²) 비교 정렬에서 힙, 분할 정복을 O(n log n) 고급 정렬로의 발전한 계열을 한 줄로 표현.
  
  
• 빨강 점선 : DP chain
  → Divide & Conquer → 1D DP → 2D DP
  → 문제를 나누는 단순 분할정복에서 중복 부분 문제 + 메모이제이션을 도입(하위 문제 해를 테이블에 저장해 재사용(1D DP))하고, 그것을 차원을 늘려 2차원 이상으로 확장(2D DP)한 흐름.
  
  
• 검정 점선 : Concept links
  → DFS ↔ Backtracking: Backtracking은 DFS를 해 공간(state space)에 적용하고 가지치기한 것이라 사실상 DFS의 강화 버전.
  → Insertion Sort ↔ Merge Sort: 둘 다 "이미 정렬된 부분을 이용해서 정렬을 완성한다"는 아이디어를 공유.

 

4. 알고리즘(18종) 통합 비교표와 그 의미

 
☞ 다이어그램의 18개 알고리즘을 그룹(패밀리)로 구별하고 속도 기준 상위, 메모리 기준 상위 우선 순서로 정렬하여 비교해봅시다.

Family (그룹)	알고리즘	시간 복잡도	공간 복잡도	실행 속도	메모리 사용량	대표 예시	특징 / 장단점 (요약)
Searching / Traversal	🤩Binary Search	O(log n)	O(1) (재귀 시 O(log n))	매우 빠름 (very fast)	매우 낮음 (very low)	정렬된 배열에서 값 찾기, 상한/하한 탐색	한 번 정렬해 두면 탐색 속도 압도적. 다만 정렬 + 정렬 유지 비용이 숨은 전제 조건.
	DFS (Depth-First Search)	O(V+E)	O(V + E) (스택/재귀)	빠름 (fast)	중간~높음 (normal~high)	그래프 경로 탐색, 사이클 탐지, 위상 정렬 보조	한 갈래를 끝까지 파고드는 방식. 백트래킹, 재귀, 트리 탐색의 기본 틀이 됨.
	BFS (Breadth-First Search)	O(V+E)	O(V + E) (큐)	빠름 (fast)	높음 (high, 레벨 큐)	최단 거리(무가중치), 레벨 탐색, 미로 최단 경로	최단 단계/최소 간선 수를 구할 때 정석. 하지만 큐에 노드가 많이 쌓여 메모리 부담이 큼.
	Linear Search	O(n)	O(1)	보통~약간 빠름 (normal~fast)	매우 낮음 (very low)	작은 배열, 정렬 안 된 리스트 검색	구현이 가장 단순. 데이터가 작을 때는 이게 오히려 실용적. 큰 데이터에서는 비효율적.
Pointer / Window / Greedy	😊Two Pointer	O(n)	O(1)	빠름 (fast)	매우 낮음 (very low)	정렬된 배열의 부분합, 투섬(two-sum) 변형	양 끝/좌우 포인터 이동으로 선형 시간에 문제 해결. 정렬·단조성 전제가 필요한 경우가 많음.
	😊Sliding Window	O(n)	O(1)	빠름 (fast)	매우 낮음 (very low)	부분합, 고정/가변 길이 구간의 최대·최소	구간을 "미는" 느낌으로 업데이트. 중복 계산 제거에 탁월. 윈도우 정의가 포인트.
	Greedy	일반적으로 O(n) ~ O(n log n)	O(1)~O(n) (문제에 따라 상이)	빠름 (fast)	낮음~중간 (low~normal)	동전 거스름, 활동 선택, 인터벌 스케줄링	매 단계에서 "지금 가장 좋은 선택"을 하되, 전역 최적이 성립하려면 탐욕 조건이 중요. 증명 없이는 위험.
Sorting	Quick Sort	평균 O(n log n) 최악 O(n²)	O(log n) (재귀 스택)	빠름 (fast)	낮음 (low)	실무 언어 내장 sort 구현(변형된 퀵/하이브리드)	평균적으로 매우 빠르고, 피벗 선택 실패 시 최악 O(n²) 라는 리스크.
	Merge Sort	O(n log n)	O(n) 추가 배열	빠름 (fast)	중간 (normal)	안정 정렬, 외부 정렬(external sort)	항상 O(n log n) 보장 + 안정 정렬. 대신 추가 메모리 필요.
	Heap Sort	O(n log n)	O(1) (배열 기반 힙)	빠름 (fast)	낮음 (low)	Top-k 추출, 우선순위 기반 정렬	최댓값/최솟값 반복 꺼내기 구조. 최악도 O(n log n). 단, 캐시 친화성이 떨어져 실제 속도는 퀵보다 느린 경우 많음.
	Insertion Sort	O(n²)	O(1)	느림 (slow), *작은 n에서만 실용	매우 낮음 (very low)	이미 거의 정렬된 배열, 작은 구간 정렬	작은 입력/거의 정렬에서 매우 효율적. 그래서 하이브리드 정렬(퀵+삽입)에서 뒷단 마무리로 자주 사용.
	Selection Sort	O(n²)	O(1)	느림 (slow)	매우 낮음 (very low)	교육용 예제, 메모리 절대 제한 환경	항상 n² 비교. 하지만 스왑 횟수가 적고 메모리는 거의 안 쓰는 배열 내 교환 정렬.
	Bubble Sort	O(n²)	O(1)	느림 (slow)	매우 낮음 (very low)	교육용, 정렬 개념 설명용	실전에서는 거의 쓰이지 않지만, 정렬 개념·안정성·스왑 아이디어를 설명하기 좋은 교재용 알고리즘.
DP / Divide & Conquer	Divide & Conquer (일반)	보통 O(n log n) (예: Merge Sort, 퀵 아이디어)	O(log n) 재귀 스택	빠름 (fast)	낮음~중간 (low~normal)	병합 정렬, 퀵 정렬, 분할 정복 최대값/최근접 점 쌍	문제를 "반으로 쪼개서 해결 후 합치는 패턴". 재귀 구조와 부분 문제 분리가 핵심.
	1D DP	O(n)	O(n)	보통~빠름 (normal~fast)	중간 (normal)	피보나치, 1차원 계단 오르기, LIS(단순 버전)	이전 상태만 잘 정의하면 빠르고 안정적. 점화식 설계와 상태 정의가 난이도 포인트.
	2D DP	O(n²) 이상	O(n²) 이상	느림~매우 느림 (slow~very slow)	높음~매우 높음 (high~very high)	LCS, 편집 거리(Edit Distance), 격자 경로	테이블이 2차원이라 메모리·시간 모두 폭발하기 쉬움. 하지만 강력한 풀이 도구.
Hash / Table based	Hash Table	평균 O(1), 최악 O(n)	O(n) + α (버킷)	매우 빠름 (very fast, avg)	중간~높음 (normal~high)	딕셔너리, 집합(Set), 캐시, 인덱스 테이블	검색·삽입·삭제 모두 평균 O(1). 충돌 관리, 해시 함수 설계, 메모리 여유 확보가 중요 포인트.
Backtracking	Backtracking	보통 O(b^d) 최악 O(n!) 등 지수급	상태 저장에 따라 O(d) ~ O(b·d·n)	매우 느림 (very slow)	중간~매우 높음 (normal~very high)	N-Queen, 순열/부분집합 생성, 수학 퍼즐(스도쿠 등)	모든 경우를 탐색하지만, 가지치기로 현실적인 시간 내에 해결을 노리는 알고리즘 템플릿. DFS의 특수한 형태.

 

4-1. FAST & LIGHT 구간

• Binary Search, Two Pointer, Sliding Window, Greedy, Linear Search 상단 구역
  
  → 이 영역은 속도는 최대치로, 메모리는 거의 사용하지 않는 실전형 도구들이 모여 있는 구간입니다. 정렬, 부분합, 구간 최적화, 간단 탐색 문제는 이 영역의 알고리즘들로 해결되는 경우가 많기 때문에, 코딩 테스트, 실무에서 가장 먼저 떠올려야 하는 1순위 후보군입니다.
  
  

4-2. FAST but HEAVY 구간

• Hash Table, 1D DP, 그래프 탐색(DFS/BFS)의 중간~우측 상단
  
  → 이 영역의 알고리즘을 선택한 것은 시간은 매우 빠른 대신, 자료구조나 테이블 때문에 메모리 비용을 감수하는 전략에 해당합니다. 해시 테이블, 캐시, 1D DP, 그래프 탐색처럼, 조회/접근 속도가 최우선일 때 메모리를 투자해서 성능을 끌어올리는 대표적인 패턴을 담고 있습니다.
  
  

4-3. SLOW but LIGHT 구간

• Bubble / Selection / Insertion Sort
  
  → 왼쪽 아래 구역은 연산은 느리지만, 메모리를 거의 사용하지 않는 전통적인 비교 기반 정렬들이 위치한 영역입니다. 자료가 작거나 이미 거의 정렬된 상황, 혹은 메모리를 극단적으로 아껴야 하는 교육/특수 환경에서만 의미가 있고, 그 외에는 보통 더 빠른 정렬(O(n log n))로 대체됩니다.
  
  

4-4. SLOW & HEAVY 구간

• 2D DP, Backtracking
  
  → 오른쪽 아래는 연산 속도도 느리고, 메모리도 많이 사용하지만, 그만큼 무거운 문제 해결 능력을 가진 알고리즘이 모여 있습니다. 2D DP와 Backtracking은 상태 공간이 폭증하는 어려운 문제(편집 거리, LCS, N-Queen, 순열/조합 생성 등)를 풀어내는 최후의 수단에 가까운 도구입니다.

 

5. 맺음말

알고리즘은 단순한 코드 기법이 아니라, 문제를 해결하기 위한 사고 방식과 바라보는 관점이라고 할 수 있습니다. 특히 5가지 핵심 알고리즘들은 실무 및 코딩 테스트에서 중요하고, 그것의 구조적 공통점, 특징, 차이점에 대한 이해는 실전 문제의 해결 전략을 세우기 위한 기반이 됩니다.
 
"알고리즘 상태 다이어그램"은 18개 알고리즘의 특징을 "메모리 사용량"과 "실행 속도"의 관점에서 비교함으로써, "어떤 상황에서 어떤 알고리즘을 선택하여 어떤 방식으로 문제를 해결할지"를 직관적으로 판단할 수 있게 도와줄 것으로 기대합니다!
 
 

즐거운 파이썬~ 즐 파이씽!
 
[주의] 내용에 오류가 있을 수 있습니다.