29_practice.py

Download
python 634 lines 18.4 KB 
  1"""
  2์‹ค์ „ ๋ฌธ์ œํ’€์ด (Practice Problems)
  3Comprehensive Practice Problems
  4
  5๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์กฐํ•ฉํ•˜์—ฌ ํ•ด๊ฒฐํ•˜๋Š” ์ข…ํ•ฉ ๋ฌธ์ œ๋“ค์ž…๋‹ˆ๋‹ค.
  6"""
  7
  8from typing import List, Tuple, Dict, Set, Optional
  9from collections import defaultdict, deque, Counter
 10from heapq import heappush, heappop
 11from functools import lru_cache
 12from bisect import bisect_left, bisect_right
 13import sys
 14
 15
 16# =============================================================================
 17# 1. ํˆฌ ํฌ์ธํ„ฐ + ์ด๋ถ„ํƒ์ƒ‰: ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ
 18# =============================================================================
 19
 20def subarray_sum_k(arr: List[int], k: int) -> int:
 21    """
 22    ํ•ฉ์ด k์ธ ๋ถ€๋ถ„ ๋ฐฐ์—ด์˜ ๊ฐœ์ˆ˜
 23    ์‹œ๊ฐ„๋ณต์žก๋„: O(n)
 24    """
 25    count = 0
 26    prefix_sum = 0
 27    sum_count = defaultdict(int)
 28    sum_count[0] = 1
 29
 30    for num in arr:
 31        prefix_sum += num
 32        # prefix_sum - k๊ฐ€ ์ด์ „์— ๋‚˜์™”๋‹ค๋ฉด
 33        count += sum_count[prefix_sum - k]
 34        sum_count[prefix_sum] += 1
 35
 36    return count
 37
 38
 39def longest_subarray_sum_at_most_k(arr: List[int], k: int) -> int:
 40    """
 41    ํ•ฉ์ด k ์ดํ•˜์ธ ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ๋ฐฐ์—ด
 42    (์–‘์ˆ˜๋งŒ ์žˆ๋Š” ๊ฒฝ์šฐ)
 43    ์‹œ๊ฐ„๋ณต์žก๋„: O(n)
 44    """
 45    n = len(arr)
 46    max_len = 0
 47    current_sum = 0
 48    left = 0
 49
 50    for right in range(n):
 51        current_sum += arr[right]
 52
 53        while current_sum > k and left <= right:
 54            current_sum -= arr[left]
 55            left += 1
 56
 57        max_len = max(max_len, right - left + 1)
 58
 59    return max_len
 60
 61
 62# =============================================================================
 63# 2. BFS + DP: ์ตœ๋‹จ ๊ฒฝ๋กœ + ๋น„์šฉ
 64# =============================================================================
 65
 66def shortest_path_with_fuel(n: int, edges: List[Tuple[int, int, int]],
 67                            start: int, end: int, fuel: int) -> int:
 68    """
 69    ์—ฐ๋ฃŒ ์ œํ•œ์ด ์žˆ๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ
 70    edges: (u, v, fuel_cost)
 71    ๋ฐ˜ํ™˜: ์ตœ์†Œ ๊ฑฐ๋ฆฌ (๋ถˆ๊ฐ€๋Šฅํ•˜๋ฉด -1)
 72    ์‹œ๊ฐ„๋ณต์žก๋„: O(V * F + E)
 73    """
 74    graph = defaultdict(list)
 75    for u, v, cost in edges:
 76        graph[u].append((v, cost))
 77        graph[v].append((u, cost))
 78
 79    # BFS with state: (node, remaining_fuel)
 80    INF = float('inf')
 81    dist = [[INF] * (fuel + 1) for _ in range(n)]
 82    dist[start][fuel] = 0
 83
 84    queue = deque([(start, fuel, 0)])  # (node, remaining_fuel, distance)
 85
 86    while queue:
 87        node, remaining, d = queue.popleft()
 88
 89        if node == end:
 90            return d
 91
 92        if d > dist[node][remaining]:
 93            continue
 94
 95        for neighbor, cost in graph[node]:
 96            if remaining >= cost:
 97                new_fuel = remaining - cost
 98                if d + 1 < dist[neighbor][new_fuel]:
 99                    dist[neighbor][new_fuel] = d + 1
100                    queue.append((neighbor, new_fuel, d + 1))
101
102    return -1
103
104
105# =============================================================================
106# 3. ๊ทธ๋ฆฌ๋”” + ์šฐ์„ ์ˆœ์œ„ ํ: ์ž‘์—… ์Šค์ผ€์ค„๋ง
107# =============================================================================
108
109def max_profit_scheduling(jobs: List[Tuple[int, int, int]]) -> int:
110    """
111    ์ž‘์—… ์Šค์ผ€์ค„๋ง: ๊ฒน์น˜์ง€ ์•Š๊ฒŒ ์„ ํƒํ•˜์—ฌ ์ตœ๋Œ€ ์ด์ต
112    jobs: (์‹œ์ž‘, ์ข…๋ฃŒ, ์ด์ต)
113    ์‹œ๊ฐ„๋ณต์žก๋„: O(n log n)
114    """
115    n = len(jobs)
116    if n == 0:
117        return 0
118
119    # ์ข…๋ฃŒ ์‹œ๊ฐ„์œผ๋กœ ์ •๋ ฌ
120    jobs = sorted(jobs, key=lambda x: x[1])
121    end_times = [job[1] for job in jobs]
122
123    dp = [0] * (n + 1)
124
125    for i in range(n):
126        start, end, profit = jobs[i]
127
128        # ํ˜„์žฌ ์ž‘์—… ์‹œ์ž‘ ์ „์— ๋๋‚˜๋Š” ๋งˆ์ง€๋ง‰ ์ž‘์—…
129        j = bisect_right(end_times, start) - 1
130
131        # ์„ ํƒ vs ๋น„์„ ํƒ
132        dp[i + 1] = max(dp[i], (dp[j + 1] if j >= 0 else 0) + profit)
133
134    return dp[n]
135
136
137# =============================================================================
138# 4. ๋ฌธ์ž์—ด + DP: ํŽธ์ง‘ ๊ฑฐ๋ฆฌ ์‘์šฉ
139# =============================================================================
140
141def min_operations_to_palindrome(s: str) -> int:
142    """
143    ๋ฌธ์ž์—ด์„ ํŒฐ๋ฆฐ๋“œ๋กฌ์œผ๋กœ ๋งŒ๋“œ๋Š” ์ตœ์†Œ ์‚ฝ์ž…/์‚ญ์ œ
144    = ๊ธธ์ด - LCS(s, reverse(s))
145    """
146    n = len(s)
147    t = s[::-1]
148
149    # LCS
150    dp = [[0] * (n + 1) for _ in range(n + 1)]
151    for i in range(1, n + 1):
152        for j in range(1, n + 1):
153            if s[i - 1] == t[j - 1]:
154                dp[i][j] = dp[i - 1][j - 1] + 1
155            else:
156                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
157
158    return n - dp[n][n]
159
160
161def longest_palindromic_subsequence(s: str) -> int:
162    """
163    ๊ฐ€์žฅ ๊ธด ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„ ์ˆ˜์—ด
164    = LCS(s, reverse(s))
165    """
166    n = len(s)
167    t = s[::-1]
168
169    dp = [[0] * (n + 1) for _ in range(n + 1)]
170    for i in range(1, n + 1):
171        for j in range(1, n + 1):
172            if s[i - 1] == t[j - 1]:
173                dp[i][j] = dp[i - 1][j - 1] + 1
174            else:
175                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
176
177    return dp[n][n]
178
179
180# =============================================================================
181# 5. ๊ทธ๋ž˜ํ”„ + Union-Find: ์—ฐ๊ฒฐ ์š”์†Œ
182# =============================================================================
183
184class DSU:
185    """Disjoint Set Union"""
186    def __init__(self, n: int):
187        self.parent = list(range(n))
188        self.rank = [0] * n
189        self.size = [1] * n
190
191    def find(self, x: int) -> int:
192        if self.parent[x] != x:
193            self.parent[x] = self.find(self.parent[x])
194        return self.parent[x]
195
196    def union(self, x: int, y: int) -> bool:
197        px, py = self.find(x), self.find(y)
198        if px == py:
199            return False
200        if self.rank[px] < self.rank[py]:
201            px, py = py, px
202        self.parent[py] = px
203        self.size[px] += self.size[py]
204        if self.rank[px] == self.rank[py]:
205            self.rank[px] += 1
206        return True
207
208
209def min_cost_to_connect_all(n: int, edges: List[Tuple[int, int, int]]) -> int:
210    """
211    ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์ตœ์†Œ ๋น„์šฉ (MST)
212    edges: (u, v, cost)
213    """
214    edges = sorted(edges, key=lambda x: x[2])
215    dsu = DSU(n)
216    total_cost = 0
217    edges_used = 0
218
219    for u, v, cost in edges:
220        if dsu.union(u, v):
221            total_cost += cost
222            edges_used += 1
223            if edges_used == n - 1:
224                break
225
226    return total_cost if edges_used == n - 1 else -1
227
228
229def count_islands(grid: List[List[int]]) -> int:
230    """
231    ์„ฌ์˜ ๊ฐœ์ˆ˜ (Union-Find ๋ฒ„์ „)
232    grid[i][j] = 1: ๋•…, 0: ๋ฌผ
233    """
234    if not grid or not grid[0]:
235        return 0
236
237    rows, cols = len(grid), len(grid[0])
238    dsu = DSU(rows * cols)
239    count = 0
240
241    def idx(r, c):
242        return r * cols + c
243
244    for r in range(rows):
245        for c in range(cols):
246            if grid[r][c] == 1:
247                count += 1
248
249    directions = [(0, 1), (1, 0)]
250    for r in range(rows):
251        for c in range(cols):
252            if grid[r][c] == 0:
253                continue
254            for dr, dc in directions:
255                nr, nc = r + dr, c + dc
256                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
257                    if dsu.union(idx(r, c), idx(nr, nc)):
258                        count -= 1
259
260    return count
261
262
263# =============================================================================
264# 6. ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ + ์ขŒํ‘œ ์••์ถ•: ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ
265# =============================================================================
266
267class SegmentTree:
268    """๊ตฌ๊ฐ„ ํ•ฉ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ"""
269    def __init__(self, n: int):
270        self.n = n
271        self.tree = [0] * (4 * n)
272
273    def update(self, node: int, start: int, end: int, idx: int, delta: int):
274        if idx < start or idx > end:
275            return
276        if start == end:
277            self.tree[node] += delta
278            return
279        mid = (start + end) // 2
280        self.update(2 * node, start, mid, idx, delta)
281        self.update(2 * node + 1, mid + 1, end, idx, delta)
282        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
283
284    def query(self, node: int, start: int, end: int, l: int, r: int) -> int:
285        if r < start or end < l:
286            return 0
287        if l <= start and end <= r:
288            return self.tree[node]
289        mid = (start + end) // 2
290        return (self.query(2 * node, start, mid, l, r) +
291                self.query(2 * node + 1, mid + 1, end, l, r))
292
293
294def count_smaller_after_self(nums: List[int]) -> List[int]:
295    """
296    ๊ฐ ์›์†Œ ๋’ค์— ์žˆ๋Š” ๋” ์ž‘์€ ์›์†Œ์˜ ๊ฐœ์ˆ˜
297    ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ + ์ขŒํ‘œ ์••์ถ•
298    ์‹œ๊ฐ„๋ณต์žก๋„: O(n log n)
299    """
300    # ์ขŒํ‘œ ์••์ถ•
301    sorted_nums = sorted(set(nums))
302    rank = {v: i for i, v in enumerate(sorted_nums)}
303    n = len(sorted_nums)
304
305    result = []
306    st = SegmentTree(n)
307
308    # ์—ญ์ˆœ์œผ๋กœ ์ฒ˜๋ฆฌ
309    for num in reversed(nums):
310        r = rank[num]
311        # r๋ณด๋‹ค ์ž‘์€ ์ธ๋ฑ์Šค์˜ ํ•ฉ (= ๋” ์ž‘์€ ์›์†Œ์˜ ๊ฐœ์ˆ˜)
312        count = st.query(1, 0, n - 1, 0, r - 1) if r > 0 else 0
313        result.append(count)
314        st.update(1, 0, n - 1, r, 1)
315
316    return result[::-1]
317
318
319# =============================================================================
320# 7. ๋ฐฑํŠธ๋ž˜ํ‚น: ์กฐํ•ฉ ์ตœ์ ํ™”
321# =============================================================================
322
323def solve_sudoku(board: List[List[str]]) -> bool:
324    """
325    ์Šค๋„์ฟ  ํ•ด๊ฒฐ
326    board: 9x9, '1'-'9' ๋˜๋Š” '.'
327    """
328
329    def is_valid(row: int, col: int, num: str) -> bool:
330        # ํ–‰ ๊ฒ€์‚ฌ
331        if num in board[row]:
332            return False
333        # ์—ด ๊ฒ€์‚ฌ
334        for r in range(9):
335            if board[r][col] == num:
336                return False
337        # 3x3 ๋ฐ•์Šค ๊ฒ€์‚ฌ
338        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
339        for r in range(box_row, box_row + 3):
340            for c in range(box_col, box_col + 3):
341                if board[r][c] == num:
342                    return False
343        return True
344
345    def solve() -> bool:
346        for row in range(9):
347            for col in range(9):
348                if board[row][col] == '.':
349                    for num in '123456789':
350                        if is_valid(row, col, num):
351                            board[row][col] = num
352                            if solve():
353                                return True
354                            board[row][col] = '.'
355                    return False
356        return True
357
358    return solve()
359
360
361# =============================================================================
362# 8. ๋น„ํŠธ๋งˆ์Šคํฌ DP: ์™ธํŒ์› ๋ฌธ์ œ (TSP)
363# =============================================================================
364
365def tsp(dist: List[List[int]]) -> int:
366    """
367    ์™ธํŒ์› ๋ฌธ์ œ (TSP)
368    ๋ชจ๋“  ๋„์‹œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ณ  ์‹œ์ž‘์ ์œผ๋กœ ๋Œ์•„์˜ค๋Š” ์ตœ์†Œ ๋น„์šฉ
369    ์‹œ๊ฐ„๋ณต์žก๋„: O(nยฒ * 2^n)
370    """
371    n = len(dist)
372    INF = float('inf')
373
374    @lru_cache(maxsize=None)
375    def dp(mask: int, last: int) -> int:
376        if mask == (1 << n) - 1:  # ๋ชจ๋“  ๋„์‹œ ๋ฐฉ๋ฌธ
377            return dist[last][0] if dist[last][0] > 0 else INF
378
379        result = INF
380        for next_city in range(n):
381            if mask & (1 << next_city):
382                continue
383            if dist[last][next_city] == 0:
384                continue
385            result = min(result, dist[last][next_city] + dp(mask | (1 << next_city), next_city))
386
387        return result
388
389    return dp(1, 0)  # 0๋ฒˆ ๋„์‹œ์—์„œ ์‹œ์ž‘
390
391
392# =============================================================================
393# 9. ์ด๋ถ„ํƒ์ƒ‰ + ๊ทธ๋ฆฌ๋””: ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜
394# =============================================================================
395
396def min_max_distance(houses: List[int], k: int) -> int:
397    """
398    k๊ฐœ์˜ ์šฐ์ฒดํ†ต์„ ์„ค์น˜ํ•˜์—ฌ ๊ฐ€์žฅ ๋จผ ์ง‘๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ ์ตœ์†Œํ™”
399    ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜: "์ตœ๋Œ€ ๊ฑฐ๋ฆฌ๊ฐ€ d ์ดํ•˜๊ฐ€ ๋˜๊ฒŒ ํ•  ์ˆ˜ ์žˆ๋Š”๊ฐ€?"
400    ์‹œ๊ฐ„๋ณต์žก๋„: O(n log D)
401    """
402    houses = sorted(houses)
403    n = len(houses)
404
405    def can_cover(max_dist: int) -> bool:
406        """์ตœ๋Œ€ ๊ฑฐ๋ฆฌ max_dist๋กœ ๋ชจ๋“  ์ง‘์„ ์ปค๋ฒ„ ๊ฐ€๋Šฅํ•œ์ง€"""
407        count = 1
408        last_post = houses[0]
409
410        for house in houses:
411            if house - last_post > 2 * max_dist:
412                count += 1
413                last_post = house
414
415        return count <= k
416
417    lo, hi = 0, houses[-1] - houses[0]
418
419    while lo < hi:
420        mid = (lo + hi) // 2
421        if can_cover(mid):
422            hi = mid
423        else:
424            lo = mid + 1
425
426    return lo
427
428
429def min_pages_per_student(pages: List[int], students: int) -> int:
430    """
431    ์ฑ…์„ ํ•™์ƒ๋“ค์—๊ฒŒ ๋‚˜๋ˆ ์ค„ ๋•Œ ์ตœ๋Œ€ ํŽ˜์ด์ง€ ์ˆ˜ ์ตœ์†Œํ™”
432    (์—ฐ์†๋œ ์ฑ…๋งŒ ๊ฐ€๋Šฅ)
433    """
434    def is_feasible(max_pages: int) -> bool:
435        count = 1
436        current = 0
437        for p in pages:
438            if p > max_pages:
439                return False
440            if current + p > max_pages:
441                count += 1
442                current = p
443            else:
444                current += p
445        return count <= students
446
447    lo, hi = max(pages), sum(pages)
448
449    while lo < hi:
450        mid = (lo + hi) // 2
451        if is_feasible(mid):
452            hi = mid
453        else:
454            lo = mid + 1
455
456    return lo
457
458
459# =============================================================================
460# 10. ์ข…ํ•ฉ: LIS + ์ด๋ถ„ํƒ์ƒ‰
461# =============================================================================
462
463def longest_increasing_subsequence(nums: List[int]) -> Tuple[int, List[int]]:
464    """
465    ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด (๊ธธ์ด + ์‹ค์ œ ์ˆ˜์—ด)
466    ์‹œ๊ฐ„๋ณต์žก๋„: O(n log n)
467    """
468    n = len(nums)
469    if n == 0:
470        return 0, []
471
472    # tails[i] = ๊ธธ์ด i+1 LIS์˜ ๋งˆ์ง€๋ง‰ ์›์†Œ ์ค‘ ์ตœ์†Ÿ๊ฐ’
473    tails = []
474    # ๊ฐ ์œ„์น˜์—์„œ์˜ LIS ๊ธธ์ด
475    lengths = [0] * n
476    # ์ด์ „ ์›์†Œ ์ถ”์ 
477    prev = [-1] * n
478    # tails์˜ ์ธ๋ฑ์Šค๊ฐ€ ์–ด๋–ค ์›๋ž˜ ์ธ๋ฑ์Šค์—์„œ ์™”๋Š”์ง€
479    tail_idx = []
480
481    for i, num in enumerate(nums):
482        pos = bisect_left(tails, num)
483        if pos == len(tails):
484            tails.append(num)
485            tail_idx.append(i)
486        else:
487            tails[pos] = num
488            tail_idx[pos] = i
489
490        lengths[i] = pos + 1
491        if pos > 0:
492            # ์ด์ „ ์›์†Œ: lengths[j] == pos์ธ ๋งˆ์ง€๋ง‰ j
493            for j in range(i - 1, -1, -1):
494                if lengths[j] == pos and nums[j] < num:
495                    prev[i] = j
496                    break
497
498    # LIS ๋ณต์›
499    max_len = max(lengths)
500    result = []
501    idx = lengths.index(max_len)
502
503    # ์ตœ์  ์‹œ์ž‘์  ์ฐพ๊ธฐ
504    for i in range(n - 1, -1, -1):
505        if lengths[i] == max_len:
506            idx = i
507            break
508
509    while idx != -1:
510        result.append(nums[idx])
511        # ์ด์ „ ์›์†Œ ์ฐพ๊ธฐ
512        target_len = lengths[idx] - 1
513        if target_len == 0:
514            break
515        for j in range(idx - 1, -1, -1):
516            if lengths[j] == target_len and nums[j] < nums[idx]:
517                idx = j
518                break
519        else:
520            break
521
522    return max_len, result[::-1]
523
524
525# =============================================================================
526# ํ…Œ์ŠคํŠธ
527# =============================================================================
528
529def main():
530    print("=" * 60)
531    print("์‹ค์ „ ๋ฌธ์ œํ’€์ด (Practice Problems) ์˜ˆ์ œ")
532    print("=" * 60)
533
534    # 1. ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ
535    print("\n[1] ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ")
536    arr = [1, 2, 3, -3, 1, 2]
537    k = 3
538    count = subarray_sum_k(arr, k)
539    print(f"    ๋ฐฐ์—ด: {arr}, k={k}")
540    print(f"    ํ•ฉ์ด {k}์ธ ๋ถ€๋ถ„ ๋ฐฐ์—ด ๊ฐœ์ˆ˜: {count}")
541
542    # 2. ์ž‘์—… ์Šค์ผ€์ค„๋ง
543    print("\n[2] ์ž‘์—… ์Šค์ผ€์ค„๋ง (์ตœ๋Œ€ ์ด์ต)")
544    jobs = [(1, 3, 50), (2, 5, 20), (4, 6, 70), (6, 7, 60)]
545    profit = max_profit_scheduling(jobs)
546    print(f"    ์ž‘์—… (์‹œ์ž‘, ์ข…๋ฃŒ, ์ด์ต): {jobs}")
547    print(f"    ์ตœ๋Œ€ ์ด์ต: {profit}")
548
549    # 3. ํŒฐ๋ฆฐ๋“œ๋กฌ
550    print("\n[3] ๋ฌธ์ž์—ด โ†’ ํŒฐ๋ฆฐ๋“œ๋กฌ")
551    s = "aebcbda"
552    ops = min_operations_to_palindrome(s)
553    lps = longest_palindromic_subsequence(s)
554    print(f"    ๋ฌธ์ž์—ด: '{s}'")
555    print(f"    ํŒฐ๋ฆฐ๋“œ๋กฌ ๋งŒ๋“œ๋Š” ์ตœ์†Œ ์—ฐ์‚ฐ: {ops}")
556    print(f"    ๊ฐ€์žฅ ๊ธด ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„์ˆ˜์—ด ๊ธธ์ด: {lps}")
557
558    # 4. MST
559    print("\n[4] ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ")
560    edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4)]
561    cost = min_cost_to_connect_all(4, edges)
562    print(f"    ๊ฐ„์„ : {edges}")
563    print(f"    MST ๋น„์šฉ: {cost}")
564
565    # 5. ์„ฌ์˜ ๊ฐœ์ˆ˜
566    print("\n[5] ์„ฌ์˜ ๊ฐœ์ˆ˜")
567    grid = [
568        [1, 1, 0, 0, 0],
569        [1, 1, 0, 0, 0],
570        [0, 0, 1, 0, 0],
571        [0, 0, 0, 1, 1]
572    ]
573    islands = count_islands([row[:] for row in grid])
574    print(f"    ๊ทธ๋ฆฌ๋“œ:")
575    for row in grid:
576        print(f"      {row}")
577    print(f"    ์„ฌ์˜ ๊ฐœ์ˆ˜: {islands}")
578
579    # 6. ๋’ค์— ์žˆ๋Š” ๋” ์ž‘์€ ์›์†Œ
580    print("\n[6] ๊ฐ ์›์†Œ ๋’ค์˜ ๋” ์ž‘์€ ์›์†Œ ๊ฐœ์ˆ˜")
581    nums = [5, 2, 6, 1]
582    result = count_smaller_after_self(nums)
583    print(f"    ๋ฐฐ์—ด: {nums}")
584    print(f"    ๊ฒฐ๊ณผ: {result}")
585
586    # 7. TSP
587    print("\n[7] ์™ธํŒ์› ๋ฌธ์ œ (TSP)")
588    dist = [
589        [0, 10, 15, 20],
590        [10, 0, 35, 25],
591        [15, 35, 0, 30],
592        [20, 25, 30, 0]
593    ]
594    min_cost = tsp(dist)
595    print(f"    ๊ฑฐ๋ฆฌ ํ–‰๋ ฌ:")
596    for row in dist:
597        print(f"      {row}")
598    print(f"    ์ตœ์†Œ ๋น„์šฉ: {min_cost}")
599
600    # 8. ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜
601    print("\n[8] ์ฑ… ๋ฐฐ๋ถ„ ๋ฌธ์ œ")
602    pages = [12, 34, 67, 90]
603    students = 2
604    min_pages = min_pages_per_student(pages, students)
605    print(f"    ํŽ˜์ด์ง€: {pages}, ํ•™์ƒ: {students}")
606    print(f"    ์ตœ๋Œ€ ํŽ˜์ด์ง€ ์ตœ์†Œํ™”: {min_pages}")
607
608    # 9. LIS
609    print("\n[9] ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด (LIS)")
610    nums = [10, 9, 2, 5, 3, 7, 101, 18]
611    length, seq = longest_increasing_subsequence(nums)
612    print(f"    ๋ฐฐ์—ด: {nums}")
613    print(f"    LIS ๊ธธ์ด: {length}")
614    print(f"    LIS ์˜ˆ์‹œ: {seq}")
615
616    # 10. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ ํƒ ๊ฐ€์ด๋“œ
617    print("\n[10] ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ ํƒ ๊ฐ€์ด๋“œ")
618    print("    | ๋ฌธ์ œ ์œ ํ˜•              | ํ•ต์‹ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜              |")
619    print("    |------------------------|----------------------------|")
620    print("    | ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ           | ํ•ด์‹œ๋งต + ํ”„๋ฆฌํ”ฝ์Šค ํ•ฉ       |")
621    print("    | ๊ตฌ๊ฐ„ ์Šค์ผ€์ค„๋ง          | ์ •๋ ฌ + ๊ทธ๋ฆฌ๋””/DP           |")
622    print("    | ๋ฌธ์ž์—ด ๋ณ€ํ™˜            | DP (LCS, ํŽธ์ง‘๊ฑฐ๋ฆฌ)         |")
623    print("    | ๊ทธ๋ž˜ํ”„ ์—ฐ๊ฒฐ            | Union-Find, BFS/DFS        |")
624    print("    | ๊ตฌ๊ฐ„ ์ฟผ๋ฆฌ              | ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ, BIT         |")
625    print("    | ์กฐํ•ฉ ์ตœ์ ํ™”            | ๋ฐฑํŠธ๋ž˜ํ‚น + ๊ฐ€์ง€์น˜๊ธฐ        |")
626    print("    | ์™„์ „ ํƒ์ƒ‰ (์ž‘์€ n)     | ๋น„ํŠธ๋งˆ์Šคํฌ DP              |")
627    print("    | ์ตœ์†Ÿ๊ฐ’ ์ตœ๋Œ€ํ™”          | ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜            |")
628
629    print("\n" + "=" * 60)
630
631
632if __name__ == "__main__":
633    main()