[프로그래머스] 종이 자르기 - Python3

1. 문제 설명

🔗 종이 자르기 Lv. 0 문제 해결하러 가기

M x N 크기의 종이를 최소로 가위질 해야하는 횟수를 반환하는 문제

 

 

2. 풀이

- 나의 풀이 : 공식 활용

def solution(M, N):
    return M * N - 1

M x N 크기의 종이를 1x1 조각으로 나누는 데 필요한 최소한의 자르기 횟수를 계산한다. 

• 시간 복잡도 O(1)
• 공간 복잡도 O(1)

---

- 다른 사람의 풀이 : 분할 정복 활용

def get_cut_cnt_dfs(width, height):
    width, height = min(width, height), max(width, height)

	# 종료 조건 -> 종이가 1x1이면 더 이상 자를 필요가 없음
    if width == 1 and height == 1:
        return 0

	# 세로로 자르기 (절반으로 나눔 -> 1번 자르기 추가) + 나머지 자르기 작업 (세로로 자른 두 덩이)
    return 1 + get_cut_cnt_dfs(width, height//2) + get_cut_cnt_dfs(width, height-height//2)

def solution(M, N):
    return get_cut_cnt_dfs(M, N)

재귀적으로 종이를 반으로 나누어 자르기 횟수를 계산한다.

• 시간 복잡도 O(log(max(M, N))
• 공간 복잡도 O(log(max(M, N))

 

 

3. 코딩테스트 대비 포인트

- 분할 정복 (Divide and Conquer)

문제를 작은 부분 문제로 나누어 해결한 후, 이를 합쳐서 전체 문제를 해결하는 알고리즘 설계 기법 (재귀 사용)

(1) 분할 : 문제를 작은 부분 문제로 나눔

(2) 정복 : 각 부분 문제를 독립적으로 해결

(3) 결합 : 부분 문제의 결과를 합쳐 전체 문제의 결과를 만듦

 

ex) merge sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

---

- BFS(Breadth-First Search, 너비 우선 탐색)

그래프나 트리에서 가까운 노드부터 탐색하는 방식 (큐 사용)

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])

    return visited

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [],
    4: [6],
    5: [],
    6: []
}

print(bfs(graph, 1))  # [1, 2, 3, 4, 5, 6]

 

 

- DFS(Depth-First Search, 너비 우선 탐색)

그래프나 트리에서 최대한 깊게 탐색한 뒤, 다음 분기로 이동하는 방식 (스택이나 재귀 사용)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = []

    visited.append(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

    return visited

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [],
    4: [6],
    5: [],
    6: []
}

print(dfs(graph, 1))  # [1, 2, 5, 3, 4, 6]