반응형
flowchart TD
START([문제]) --> Q1
Q1{"노드/칸 사이를\n이동하는 문제?\nex) 미로, 지도, 네트워크"}
Q1 -->|YES| Q1a{"최단 거리/비용\n을 구해야 함?"}
Q1 -->|NO| Q2
Q1a -->|YES| Q1b{"간선마다\n비용이 다름?\nex) 도로마다 거리 다름"}
Q1a -->|NO| Q1c{"가능한 모든 경로/조합\n을 탐색해야 함?\nex) 모든 순열, N-Queen"}
Q1b -->|YES| DIJKSTRA
Q1b -->|NO| BFS
Q1c -->|YES| DFS
Q1c -->|NO| BFS_DFS(["BFS or DFS\n연결 확인, 영역 탐색"])
Q2{"정렬된 배열에서\n값/경계를 찾아야 함?\nex) 이 값이 있나?\n최소 X 이상인 첫 위치는?"}
Q2 -->|YES| BINARY
Q2 -->|NO| Q3
Q3{"최적값(최대/최소)을\n구해야 함?"}
Q3 -->|YES| Q3a{"부분 결과가 반복적으로 겹침?\n= 같은 계산을 여러 번 하게 됨\nex) f(n) = f(n-1) + f(n-2)"}
Q3 -->|NO| UNKNOWN([문제 재검토 / 유형 불명확])
Q3a -->|YES| Q_DP1
Q3a -->|NO| Q3b{"매 순간 가장 좋은 것만\n골라도 전체 최적?\nex) 동전 거스름돈, 회의실 배정\n반례가 없음을 증명 가능?"}
Q3b -->|YES| GREEDY
Q3b -->|NO| UNKNOWN
Q_DP1{"무게/용량/합 제한 안에서\n최대 가치/최소 비용?\nex) 배낭에 물건 담기"}
Q_DP1 -->|YES| KNAPSACK
Q_DP1 -->|NO| Q_DP2
Q_DP2{"수열에서 순서 유지하며\n가장 긴 증가/감소 부분?\nex) 탑 쌓기, 가장 긴 증가 수열"}
Q_DP2 -->|YES| LIS_NODE
Q_DP2 -->|NO| Q_DP3
Q_DP3{"두 문자열/수열의\n공통 부분 최장 길이?\nex) 두 문자열의 공통 부분"}
Q_DP3 -->|YES| LCS_NODE
Q_DP3 -->|NO| Q_DP4
Q_DP4{"작은 구간 결과로\n큰 구간 결과를 계산?\nex) 행렬 곱셈 순서, 괄호 묶기"}
Q_DP4 -->|YES| INTERVAL_DP
Q_DP4 -->|NO| OTHER_DP
BFS["BFS
──────────────
시간복잡도: O(V+E)
자료구조: Queue
──────────────
방법: 레벨 단위 탐색
방문 배열로 중복 차단
──────────────
dist[next] = dist[cur] + 1
──────────────
백준 2178 미로 탐색"]
DIJKSTRA["다익스트라
──────────────
시간복잡도: O((V+E) log V)
자료구조: PriorityQueue
──────────────
방법: 최소 비용 노드부터 확정
──────────────
dist[next] = min(dist[next],
dist[cur] + weight)
──────────────
백준 1753 최단경로"]
DFS["DFS / 백트래킹
──────────────
시간복잡도: O(V+E) / O(N!)
자료구조: Stack / 재귀
──────────────
방법: 깊이 우선 탐색
조건 불만족 시 가지치기
──────────────
백준 9663 N-Queen"]
BINARY["이분탐색
──────────────
시간복잡도: O(log N)
자료구조: 정렬 배열
──────────────
방법: mid 기준으로 lo/hi 이동
──────────────
while lo <= hi:
mid = (lo+hi)/2
if arr[mid] < target: lo=mid+1
else: hi=mid-1
──────────────
백준 1920 수 찾기"]
GREEDY["그리디
──────────────
시간복잡도: O(N log N)
자료구조: 정렬 배열 / PQ
──────────────
방법: 정렬 후
매 순간 최선 선택
──────────────
백준 11047 동전 0"]
KNAPSACK["DP - 냅색
──────────────
시간복잡도: O(N x W)
자료구조: 1D/2D 배열
──────────────
방법: 아이템 순회 x 용량 순회
──────────────
dp[j] = max(dp[j],
dp[j-w] + v)
──────────────
백준 12865 평범한 배낭"]
LIS_NODE["DP - LIS
──────────────
시간복잡도: O(N²) / O(N log N)
자료구조: 1D 배열
──────────────
방법: 정렬 후 이전 원소와
대소 비교하며 갱신
──────────────
dp[i] = max(dp[j] + val[i])
if val[j] < val[i]
──────────────
백준 2655 가장 높은 탑 쌓기"]
LCS_NODE["DP - LCS
──────────────
시간복잡도: O(N x M)
자료구조: 2D 배열
──────────────
방법: 두 수열 동시 순회
──────────────
if A[i]==B[j]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j],
dp[i][j-1])
──────────────
백준 9251 LCS"]
INTERVAL_DP["DP - 구간 DP
──────────────
시간복잡도: O(N³)
자료구조: 2D 배열
──────────────
방법: 구간 길이를
점점 늘려가며 계산
──────────────
for len 2→n:
for i:
j = i+len
dp[i][j] = min/max(...)
──────────────
백준 11049 행렬 곱셈 순서"]
OTHER_DP["DP - 기타
──────────────
트리 DP: O(N)
비트마스크 DP: O(N x 2^N)
──────────────
백준 2533 사회망 서비스
백준 2098 외판원 순회"]상세 설명
BFS (너비 우선 탐색)
- 시간복잡도: O(V+E)
- 자료구조: Queue
- 사용 조건: 가중치 없는 그래프에서 최단 거리
- 핵심 점화식
dist[next] = dist[cur] + 1 - 예제 문제
- 백준 2178 - 미로 탐색 (Silver 1)
- 백준 7569 - 토마토 (Gold 5)
다익스트라
- 시간복잡도: O((V+E) log V)
- 자료구조: PriorityQueue (최소 힙)
- 사용 조건: 가중치 있는 그래프에서 단일 출발 최단 거리
- 핵심 점화식
dist[next] = min(dist[next], dist[cur] + weight) - 예제 문제
- 백준 1753 - 최단경로 (Gold 4)
- 백준 1916 - 최소비용 구하기 (Gold 5)
DFS / 백트래킹
- 시간복잡도: O(V+E) 탐색 / O(N!) 백트래킹 최악
- 자료구조: 재귀 스택
- 사용 조건: 모든 경우의 수 탐색, 조합/순열, 조건 만족 여부
- 핵심 구조
void dfs(상태) { if (종료 조건) { 결과 처리; return; } for (다음 선택지) { if (가지치기 조건) continue; dfs(다음 상태); } } - 예제 문제
- 백준 9663 - N-Queen (Gold 4)
- 백준 15649 - N과 M(1) (Silver 3)
이분탐색
- 시간복잡도: O(log N)
- 자료구조: 정렬된 배열
- 사용 조건: 정렬된 배열에서 값 탐색, 파라메트릭 서치
- 핵심 점화식
while lo <= hi: mid = (lo + hi) / 2 if arr[mid] < target: lo = mid + 1 elif arr[mid] > target: hi = mid - 1 else: return mid - 예제 문제
- 백준 1920 - 수 찾기 (Silver 4)
- 백준 2805 - 나무 자르기 (Silver 2)
그리디
- 시간복잡도: O(N log N) (정렬 포함)
- 자료구조: 정렬 배열 / PriorityQueue
- 사용 조건: 현재 최선 선택이 전체 최선을 보장할 때
- 핵심 구조
배열 정렬 for 각 원소: 현재 기준으로 최선 선택 - 예제 문제
- 백준 11047 - 동전 0 (Silver 1)
- 백준 1931 - 회의실 배정 (Silver 1)
DP - 냅색 (Knapsack)
시간복잡도: O(N × W)
자료구조: 1D 또는 2D 배열
사용 조건: 용량/합 제한 안에서 최대 가치
핵심 점화식
// 0/1 냅색 (아이템 1번만 사용) for i in 1..N: // 아이템 순회 for j in W..w[i]: // 용량 역순 순회 dp[j] = max(dp[j], dp[j - w[i]] + v[i]) // 무한 냅색 (아이템 반복 사용) for i in 1..N: for j in w[i]..W: // 용량 정순 순회 dp[j] = max(dp[j], dp[j - w[i]] + v[i])예제 문제
- 백준 12865 - 평범한 배낭 (Gold 5)
- 백준 7579 - 앱 (Gold 3)
DP - LIS (최장 증가 부분 수열)
시간복잡도: O(N²) 기본 / O(N log N) 이분탐색 최적화
자료구조: 1D 배열
사용 조건: 원소 간 순서와 값 대소 관계가 모두 중요할 때
핵심 점화식
// O(N²) dp[i] = bricks[i].h // 기저: 자기 자신 for j in 0..i: if val[j] < val[i]: dp[i] = max(dp[i], dp[j] + val[i]) // O(N log N) - tails 배열 유지 for x in arr: pos = lower_bound(tails, x) tails[pos] = x예제 문제
- 백준 2655 - 가장 높은 탑 쌓기 (Gold 3)
- 백준 14003 - 가장 긴 증가하는 부분 수열 5 (Platinum 5)
DP - LCS (최장 공통 부분 수열)
- 시간복잡도: O(N × M)
- 자료구조: 2D 배열
- 사용 조건: 두 수열의 공통된 부분 수열 최대 길이
- 핵심 점화식
if A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - 예제 문제
- 백준 9251 - LCS (Gold 5)
- 백준 9252 - LCS 2 (Gold 4)
DP - 구간 DP
- 시간복잡도: O(N³)
- 자료구조: 2D 배열
- 사용 조건: 구간 [i, j]를 점점 넓혀가며 최적값 계산
- 핵심 점화식
for len in 2..N: // 구간 길이 for i in 0..N-len: // 시작점 j = i + len // 끝점 for k in i..j: // 분할점 dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + cost) - 예제 문제
- 백준 11049 - 행렬 곱셈 순서 (Gold 3)
- 백준 1918 - 후위 표기식 (Gold 2)
반응형
'DEV > Algorithm' 카테고리의 다른 글
| [java][알고리즘] 비트마스크(Bit Mask)를 통한 배열의 부분집합 구하기 (0) | 2023.11.13 |
|---|---|
| [알고리즘] [java] 피보나치 수열과 메모이제이션 (1) | 2023.10.29 |
| [Java, 알고리즘] 이진 탐색(Binary Search) (0) | 2023.10.13 |
| [java, 알고리즘] 삽입 정렬(Insertion Sort) (2) | 2023.10.10 |
| [java, 알고리즘] 버블 정렬(Bubble Sort) (0) | 2023.10.09 |