이제 골라 쓰자냥! 실전 종합
안녕, 나 코딩냥이다냥! 드디어 마지막 장이라냥. 지금까지 무기를 잔뜩 배웠지냥? 오늘은 새 기법을 배우는 게 아니라, 문제를 보고 어떤 무기를 꺼낼지 고르는 눈을 기른다냥.
실전에서 제일 어려운 건 "이게 무슨 유형이냥?" 을 알아채는 거라냥.
오늘의 학습 목표
- 문제를 만나면 크기부터 보고 복잡도 예산을 잡는다.
- 이분 탐색 유형을 알아챈다 (LIS, 답을 이분 탐색).
- DP 유형을 알아챈다 (최대 부분합).
- 그래프 유형을 알아챈다 (가중치 격자 = 다익스트라).
- 정렬·스위핑 유형을 알아챈다 (구간 겹침).
1단계 · 문제를 만나면 (10분)
코드부터 짜지 말자냥. 먼저 무엇을 묻는지와 입력이 얼마나 큰지를 본다냥. 크기가 복잡도 예산을 정해준다냥.
- 무엇을 구하냥? — 최댓값이냥, 개수냥, 순서냥, 거리냥?
- 입력이 얼마나 크냥? —
n이 100이냥, 10만이냥, 10억이냥? - 그 크기에 맞는 복잡도의 기법을 고른다냥
크기로 복잡도를 짐작한다냥. 대략 1초에 1억(10⁸) 번쯤이라 치면 —
n ≤ 20→ 완전탐색·비트마스킹(2ⁿ)도 된다냥n ≤ 5000→O(n²)도 된다냥n ≤ 100000→O(n log n)이어야 한다냥 (정렬·이분탐색·힙)값이 10억인데 다 훑어야 하면 → 답을 이분 탐색한다냥
"n 이 10만인데 이중 반복문?" 이면 잘못 고른 거라냥. 3장·14장에서 계속
본 이야기라냥.
2단계 · 이분 탐색 유형 (13분)
6장의 이분 탐색이 두 가지 모습으로 나온다냥. 하나는 정렬된 것에서 자리 찾기, 하나는 답 자체를 이분 탐색하기라냥.
"가장 긴 증가 부분 수열" 은 O(n²) DP 로도 되지만, n 이 크면 느리다냥.
이분 탐색을 쓰면 O(n log n) 이라냥.
tails[k] 에 "길이 k+1 짜리 증가 수열의 마지막 값 중 최소" 를 유지한다냥.
새 원소가 들어갈 자리를 이분 탐색으로 찾아 갱신한다냥.
import bisect
tails = []
for x in a:
pos = bisect.bisect_left(tails, x) # 엄격히 증가라냥
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
print(len(tails))오늘 1번 문제라냥. tails 의 길이가 곧 LIS 길이라냥.
답을 이분 탐색하는 유형도 있다냥.
"나무를 잘라 m 만큼 얻는 절단기 높이의 최댓값" 같은 문제라냥. 높이 H
를 직접 이분 탐색하고, 그 H 로 얼마나 얻는지 O(n) 에 확인한다냥.
H 가 클수록 얻는 양이 줄어드는 단조성이 있어서 이분 탐색이 된다냥.
값 범위가 10억이어도 log 번만 확인하니 빠르다냥. 오늘 2번 문제라냥.
3단계 · DP 유형 (12분)
13장의 DP 라냥. "연속한 부분에서 최대·최소" 나 "여기서 끝나는 최적값" 이 보이면 DP 를 떠올린다냥.
"연속한 부분 배열의 최대 합" 은 cur 에 여기서 끝나는 최대합 을
유지하며 훑는다냥.
cur = a[0]
best = a[0]
for i in range(1, n):
cur = max(a[i], cur + a[i]) # 새로 시작하냥, 이어가냥
best = max(best, cur)
print(best)cur + a[i] 가 a[i] 보다 작으면(앞이 손해면) 새로 시작한다냥. 오늘
3번 문제라냥.
전부 음수여도 하나는 골라야 한다냥.
부분 배열은 비어 있을 수 없다냥. 그래서 best 를 0 으로 시작하면
안 된다냥. 전부 음수인 입력에서 0 을 답으로 내버린다냥.
best 와 cur 를 첫 원소로 시작하면 이 함정을 피한다냥. 오늘 3번의
숨겨진 테스트가 이걸 잡는다냥.
4단계 · 그래프 유형 (12분)
"격자에서 최소 비용으로 이동" 이 나오면 10장 격자와 18장 다익스트라를 같이 떠올린다냥.
칸마다 비용이 다르면 BFS 가 아니라 다익스트라라냥.
10장의 미로는 모든 칸이 "한 걸음" 이라 BFS 로 됐다냥. 그런데 칸마다 밟는 비용이 다르면, 가까운 칸 순서가 걸음 수와 달라진다냥. 그때는 다익스트라 라냥.
격자를 그래프로 보면, 각 칸이 점이고 상하좌우가 간선이라냥. 8장의 방향표를 그대로 쓰되, 큐 대신 우선순위 큐를 쓰는 거라냥.
import heapq
dist = [[INF] * m for _ in range(n)]
dist[0][0] = g[0][0] # 시작 칸 비용도 포함이라냥
pq = [(g[0][0], 0, 0)]
while pq:
d, r, c = heapq.heappop(pq)
if d > dist[r][c]:
continue
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
nd = d + g[nr][nc]
if nd < dist[nr][nc]:
dist[nr][nc] = nd
heapq.heappush(pq, (nd, nr, nc))이렇게 여러 장의 기법이 한 문제에서 만난다냥. 격자(8·10장) + 다익스트라 (18장) 라냥. 실전 문제는 대개 이런 조합이라냥. 오늘 4번 문제라냥.
5단계 · 정렬·스위핑 유형 (11분)
"구간이 잔뜩 있는데 가장 많이 겹치는 순간" 같은 문제라냥. 12장 회의실의 사촌이라냥. 사건을 정렬해 훑는 스위핑이라냥.
구간마다 시작에서 +1, 끝난 직후에 -1 인 사건을 만든다냥. 좌표 순으로 정렬해 훑으며 현재 겹친 수를 세면, 그 최댓값이 답이라냥.
events = []
for s, e in segs:
events.append((s, 1))
events.append((e + 1, -1)) # 끝점 포함이라 e+1 에서 줄인다냥
events.sort()
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)17장 MST 의 두 그룹 나누기, 12장 회의실이 전부 이 "정렬해서 훑기" 라냥. 오늘 5번 문제라냥.
배운 것을 한눈에
무기고를 정리하면 이렇다냥
- 훑기·누적 → 리스트·문자열·누적합 (1·2·3·14장)
- 정렬·이분 탐색 → 정렬·이분탐색·투 포인터 (4·6·14장)
- 자료구조 → 딕셔너리·스택·큐·트라이·세그먼트 트리 (5·9·21·22장)
- 재귀·완전탐색 → 재귀·완전탐색·비트마스킹 (7·11·20장)
- 그리디·DP → 그리디·동적계획법 (12·13장)
- 그래프 → 격자·BFS·DFS·유니온파인드·MST·다익스트라·위상정렬 (8·10·16·17·18·19장)
문제를 보면 이 중 어느 서랍을 열지 고르는 거라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번 LIS(이분 탐색), 2번 나무 자르기(답을 이분 탐색), 3번 최대 부분합(DP), 4번 가중치 격자(다익스트라), 5번 구간 겹침(스위핑)이라냥.
각 문제를 보면서 "이건 무슨 유형이냥?" 을 먼저 맞혀보자냥. 그게 오늘의 진짜 연습이라냥.
여기까지 온 너는 이제 알고리즘 문제를 스스로 분석하고 푸는 힘이 생겼다냥. 정말, 정말 수고했다냥. 코딩냥이는 언제나 응원한다냥~