Q1) BOJ 1715 G4

• 문제: https://www.acmicpc.net/problem/1715

1.1 개념

우선순위 큐(Priority Queue)

• 정의:
  - 요소들이 우선순위(priority)에 따라 정렬되어 가장 높은 우선순위(or 낮은 값)을 가진 요소가 먼저 나오는 자료구조
• 비교

자료구조	데이터 추출 방식	예시
스택(Stack)	후입선출: 최근에 삽입된 데이터부터 추출	박스 쌓기
큐(Queue)	선입선출: 가장 먼저 삽입된 데이터부터 추출	줄 서기
우선순위 큐(Priority Queue)	우선순위가 가장 높은 데이터부터 추출	저렴한/비싼 가격 순으로 데이터 추출

-> 즉, 큐는 순서 기반, 우선순위 큐는 값 기반

파이썬에서는 우선순위 큐 기능을 지원하는 라이브러리인 Priority Queue, heapq가 존재

• Priority Queue => Thread-Safe
• heapq => Non-Safe
  => 따라서 코테에선 Thread-Safe를 요구하지 않기 때문에 heapq를 씀(절차가 없기 때문에 시간적으로 효율적)

힙(Heap)

• 우선순위 큐 자체가 내부적으로 힙(Heap)을 사용해 구현
• 힙은 완전 이진 트리 구조
• 삽입/삭제 연산에도 전체 정렬을 하지 않고 O(logN) 시간에 우선 순위 유지 가능
  - 최소 힙(Min Heap): 루트에 가장 작은 값이 위치
  • 최대 힙(Max Heap): 루트에 가장 큰 값이 위치

파이썬에서는 heapq 모듈을 사용해 최소 힙(min-heap) 구현

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)

print(heapq.heappop(heap))  # 2 (가장 작은 값부터 꺼냄)
print(heapq.heappop(heap))  # 5

최대 힙 구현(우선순위 반전)

• 파이썬은 기본적으로 최소 힙이기 때문에 -값을 넣어 최대 힙처럼 동작시킴

heapq.heappush(heap, -5)  # push
max_val = -heapq.heappop(heap)  # pop and reverse sign

튜플로 우선순위 조절

• 우선순위 + 데이터 같이 저장 가능

heapq.heappush(heap, (1, "data1"))  # 우선순위 1
heapq.heappush(heap, (3, "data2"))  # 우선순위 3

1.2 풀이

아이디어

• 예시를 가지고 비교를 해 보니 작은 숫자부터 합치는 게 정답이 나오는 패턴이었음
• heapq가 애초에 최소 힙 형태
• 수를 최소 힙에 저장해서 작은 수 두 개를 더하고
• 더한 값을 다시 최소 힙에 넣어서 정렬하고
• 그 행위를 반복해서 누적 합을 더하면 될 것이라 생각

1차 코드

import heapq

N = int(input())  # 카드 묶음 수
heap_card = []

# 카드 묶음을 min-heap에 삽입
for _ in range(N):
    heapq.heappush(heap_card, int(input()))

# 합친 비용을 누적하지 않은 버전 (오답)
while len(heap_card) > 1:
    sum = heapq.heappop(heap_card)
    sum = sum + heapq.heappop(heap_card)
    heapq.heappush(heap_card, sum)

print(heap_card[0])  # ❌ 총합 아님

틀린 이유

• sum = pop1 + pop2 구하고, 이걸 다시 heap에 넣는 건 괜찮음
• 근데 매번 합치는 횟수를 따로 누적해서 더해야 하는데 그걸 빠뜨림
• heap_card[0]은 마지막으로 합쳐진 묶음의 크기이지, 이게 누적합은 아님

수정

• total = 0으로 따로 누적 합 저장
• 매 반복마다 first + second를 total +=

최종 코드

import heapq

N = int(input()) #N개의 숫자 카드 묶음

heap_card = [] #카드 묶음 담을 min heap

total = 0 #누적 합

for i in range(N):
  heapq.heappush(heap_card, int(input()))

#이러면 n개의 묶음이 min-heap으로 정리될 것

while len(heap_card) >  1:
  #작은 값 두 개 꺼내고 삭제 및 더한 값 다시 넣기
  sum = heapq.heappop(heap_card)
  sum = sum + heapq.heappop(heap_card)
  total = total + sum
  
  heapq.heappush(heap_card, sum)

print(total)

Q2) BOJ 1717 G5

• 문제: https://www.acmicpc.net/problem/1717

2.1 개념

유니온 파인드(Disjoint Set/Union-Find)

• 그래프 알고리즘 중 하나
• 보통 두 개의 노드를 선택했을 때 이 노드들이 같은 집합인지 찾아내는 알고리즘으로 '합집합 찾기'라고도 부름
• 유니온(Union): 두 개의 노드를 하나로 합치는 것
• 파인드(Find): 선택한 노드가 어느 집합에 있는지 확인하는 것

핵심 연산

연산 이름	설명
find(x)	원소 x가 속한 집합의 대표(root)를 찾음
union(x, y)	x와 y가 속한 두 집합을 합침
same(x, y)	x와 y가 같은 집합에 속해 있는지 확인

내부 동작 방식

유니온 파인드 사용을 위해서는 parent 배열 + find/union 함수 조합으로 직접 구현해야 함

1) 데이터 표현

• 보통 parent[i] = i로 초기화
  -> 처음에는 각 원소가 자기 자신이 대표(root)인 집합

2) find(x) 연산

• 원소 x가 속합 집합의 대표(루트)를 재귀적으로 찾음

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축 (Path Compression)
    return parent[x]

3) union(x, y) 연산

• 두 원소 x, y의 루트를 찾아서 한쪽 루트를 다른 쪽으로 연결

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

• root_y의 parent를 root_x로 하겠다 <= 밑으로 붙이겠다

직접 구현 총 예시

# 초기화
parent = [i for i in range(n + 1)]  # 노드 번호가 1부터 n까지일 경우

# find 함수 (경로 압축 포함)
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

# union 함수
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x  # 또는 parent[root_x] = root_y

2.2 풀이

아이디어

• 문제 자체가 유니온 파인드를 직접 구현하라는 문제

1차 코드

n, m = map(int, input().split())
lst = []  # 연산 리스트

parent = [i for i in range(n+1)]  # 초기화

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

for i in range(m):
    lst[i] = map(int, input().split())  # ❌ 런타임 에러 발생

    if lst[0] == 0:
        union(lst[1], lst[2])
    else:
        if find(lst[1]) == find(lst[2]):
            print("YES")
        else:
            print("NO")

틀린 부분

문제	설명
lst[i] = ...	인덱스를 할당하려 했지만 lst는 빈 리스트라 인덱스 없음 → 런타임 에러
lst[0], lst[1]	리스트에 값을 넣지 못했기 때문에 접근 불가
find는 잘 작성됐지만	입력 처리 로직 때문에 전체 코드가 망가짐

수정

• 입력을 리스트에 넣지 않고 op, a, b 변수로 직접 받기
• sys.setrecursionlimit()으로 재귀 깊이 제한 해제

최종 코드

import sys
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

for _ in range(m):
    op, a, b = map(int, input().split())
    if op == 0:
        union(a, b)
    else:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")