Chapter 07. 고급 탐색 알고리즘

고급 탐색 알고리즘 (기초 문제 풀이)

혼자 힘으로 풀어 보기

트리 순회: https://www.acmicpc.net/problem/1991

문제 제목: 트리 순회
문제 난이도: 하(Easy)
문제 유형: 트리, 구현
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 전위 순회: 루트 -> 왼쪽자식 -> 오른쪽 자식
• 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식
• 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트
  
  
  

소스 코드

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

def pre_order(node):
    print(node.data, end='')
    if node.left_node != '.':
        pre_order(tree[node.left_node])
    print(node.data, end='')
    if node.right_node != '.':
        in_order(tree[node.right_node])

def post_order(node):
    if node.left_node != '.':
        post_order(tree[node.left_node])
    if node.right_node != '.':
        post_order(tree[node.right_node])
    print(node.data, end='')

n = int(input())
tree = {}
for i in range(n):
    data, left_node, right_node = input().split()
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

혼자 힘으로 풀어 보기

트리의 높이와 너비: https://www.acmicpc.net/problem/2250

문제 제목: 트리의 높이와 너비
문제 난이도: 중(Medium)
문제 유형: 트리, 구현
추천 풀이 시간: 50분

문제 풀이 핵심 아이디어

• 중위 순회를 이용하면 X축을 기준으로 왼쪽부터 방문한다는 특징이 있습니다.
• 이 문제는 중위 순회 알고리즘을 이용하고, 추가적으로 Level값을 저장하도록 하여 문제를 해결할 수 있습니다.
  

소스 코드

class Node:
    def __init__(self, number, left_node, right_node):
        self.parent = -1
        self.number = number
        self.left_node = left_node
        self.right_node = right_node

def in_order(node, level):
    global level_depth, x
    level_depth = max(level_depth, level)
    if node.left_node != -1:
        in_order(tree[node.left_node], level + 1)
    level_min[level] = min(level_min[level], x)
    level_max[level] = max(level_max[level], x)
    x += 1
    if node.right_node != -1:
        in_order(tree[node.right_node], level + 1)

n = int(input())
tree = {}
level_min = [n]
level_max = [0]
root = -1
x = 1
level_depth = 1

for i in range(1, n+1):
     tree[i] = Node(i, -1, -1)
    level_min.append(n)
    level_max.append(0)

for _ in range(n):
    number, left_node, right_node = map(int, input().split())
    tree[number].left_node = left_node
    tree[number].right_node = right_node
    if left _node != -1:
        tree[left_node].parent = number
    if right_node != -1:
        tree[right_node].parent = number

for i in range(1, n+1):
    if tree[i].parent == -1:
        root = i

in_order(tree[root], 1)

result_level = 1
result_width = level_max[1] - level_min[1] + 1
for i in range(2, level_depth + 1):
    width = level_max[i] - level_min[i] + 1
    if result_width < width:
        result_level = i
        result_width width

print(result_level, result_width)

고급 탐색 알고리즘 (핵심 형 문제 풀이)

혼자 힘으로 풀어보기

최소 힙: https://www.acmicpc.net/problem/1927

문제 제목: 최소 힙
문제 난이도: 하(Easy)
문제 유형: 힙, 자료구조
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 최소 힙의 기본적인 기능을 구현합니다.
• 파이썬에서 heapq 라이브러리를 이용하면 간단히 힙을 구현할 수 있습니다.
• 최소 힙의 기본적인 기능을 구현합니다.
  

소스 코드

import heapq

n = int(input())
heap = []
result = []

for _ in range(n):
    data = int(input())
    if data == 0:
        if heap:
            result.append(heapq.heappop(heap))
        else:
            result.append(0)
    else:
        heapq.heappush(heap, data)

for data in result:
    print(data)

혼자 힘으로 풀어 보기

카드 정렬하기: https://www.acmicpc.net/problem/1715

문제 제목: 카드 정렬하기
문제 난이도: 하(Easy)
문제 유형: 힙, 자료구조, 그리디
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 가장 크기가 작은 숫자 카드 묶음들을 먼저 합쳤을 때, 비교 횟수가 가장 적습니다.
  

• 가장 크기가 작은 숫자 카드 묶음들을 2개씩 합치기 위해, 힙 자료구조를 이용합니다.
  

소스 코드

import heapq

n = int(input())
heap = []

for i in range(n):
    data = int(input())
    heapq.heappush(heap, data)

result = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)

혼자 힘으로 풀어보기

문제집: https://www.acmicpc.net/problem/1766

문제 제목: 문제집
문제 난이도: 중(Medium)
문제 유형: 힙, 위상 정렬
추천 풀이 시간: 40분

문제 풀이 핵심 아이디어

• 본 문제는 전형적인 위상 정렬 문제입니다.
• 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘입니다.
• 위상 정렬의 시간 복잡도는 O(V+E)로 문제를 해결할 수 있습니다.
  

위상 정렬(Topology Sort) 알고리즘

1) 진입 차수가 0인 정점을 큐에 삽입합니다.
2) 큐에서 원소를 꺼내 해당 원소와 간선을 제거합니다.
3) 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입합니다.
4) 큐가 빌 때까지 2)-3) 과정을 반복합니다.

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것입니다.
• 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

소스 코드

import heapq

n,m = map(int, input().split())
array = [[] for i in range(n+1)]
indegree = [0] * (n+1)

heap = []
result = []

for _ in range(m):
    x, y = map(int, input().split())
    array[x].append(y)
    indegree[y] += 1

for i in range(1, n+1):
    if indegree[i] == 0:
        heapq,heappush(heap, i)

result = []

while heap:
    data = heapq.heappop(heap)
    result.append(data)
    for y in array[data]:
        indegree[y] -= 1
        if indegree[y] == 0:
            heapq.heappush(heap, y)

for i in result:
    print(i, end=' ')