스택, 큐, 덱, 힙, 해시, 집합 등 기본 자료구조를 사용하는 문제를 풀고 자료구조에 대해 이해한다.

개요

이번 미션은 LOJ(Leet Online Judge) 자료구조 입문 문제집을 풀면서 자료구조의 기본 개념을 익히고,

실제 문제 풀이에서 어떻게 활용되는지 경험해보는 것을 목표로 진행했다.

관련 링크:
https://loj.kr/workbooks/6

알고리즘 문제를 풀다 보면 단순히 프로그래밍 문법만 아는 것으로는 해결할 수 없는 경우가 많다.
같은 문제라도 어떤 자료구조를 선택하느냐에 따라 코드 길이, 실행 시간, 구현 난이도가 완전히 달라진다.

예를 들어 단순히 데이터를 저장하는 문제라면 리스트 하나로도 해결할 수 있다.

하지만 문제의 요구사항이 바뀌면 이야기가 달라진다.

  • 가장 최근 값을 빠르게 꺼내야 한다 → 스택(Stack)
  • 먼저 들어온 값을 순서대로 처리해야 한다 → 큐(Queue)
  • 양쪽 끝에서 자유롭게 넣고 빼야 한다 → 덱(Deque)
  • 우선순위가 높은 데이터를 먼저 처리해야 한다 → 힙(Heap)
  • 특정 데이터를 빠르게 찾거나 중복 여부를 확인해야 한다 → 해시(Hash), 집합(Set)

이처럼 자료구조는 단순한 이론 개념이 아니라 문제 해결을 위한 핵심 도구라고 볼 수 있다.

이번 미션에서는 이러한 자료구조들을 직접 사용하면서 개념을 정리하고, 실제 문제 풀이를 통해 익숙해지는 것을 목표로 하였다.

왜 이 미션을 선택했는가

보안 분야를 공부하다 보면 프로그래밍 능력도 중요하지만,

그 기반이 되는 알고리즘과 자료구조에 대한 이해 역시 매우 중요하다고 느꼈다.

웹 보안

웹 보안 실습에서는 요청과 응답 흐름을 분석하거나 세션 데이터를 다루게 된다.
이 과정에서 큐, 해시, 문자열 처리 개념들이 많이 나온다.

포렌식

포렌식에서는 대량의 로그를 처리하거나 특정 데이터를 빠르게 검색해야 한다.
이때 해시 기반 탐색이나 효율적인 자료 관리가 중요하다.

CTF

CTF 문제를 풀다 보면 다음과 같은 작업이 자주 나온다.

  • 문자열 처리
  • BFS / DFS 탐색
  • 우선순위 큐
  • 중복 체크
  • 빠른 탐색
  • 상태 관리

결국 자료구조에 대한 이해가 부족하면 비효율적인 방식으로 문제를 풀게 된다.
반대로 개념에 대한 이해가 많을수록 좀 더 빠르게 풀어나갈수있다고 생각한다.
실제로 이전에는 Python 리스트 하나만으로 대부분 해결하려고 했는데,
입력 크기가 커지면 시간 초과가 발생하거나 코드가 불필요하게 복잡해지는 경우가 많았다.

그래서 자료구조를 단순히 이론으로만 보는 것이 아니라,
실제 문제를 통해 몸으로 익혀보자는 생각으로 이 미션을 선택하게 되었다.

자료구조 학습 정리

1. 스택 (Stack)

개념

스택은 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조이다.

이를 LIFO (Last In, First Out) 구조라고 한다.

쉽게 생각하면 책을 쌓아두는 구조와 비슷하다.

  • 새로운 책은 맨 위에 올린다.
  • 책을 꺼낼 때도 맨 위 책부터 꺼낸다.

즉 가장 나중에 들어온 데이터가 가장 먼저 처리된다.

주요 연산

데이터 삽입:

1

stack.append(x)

데이터 제거:

1

stack.pop()

맨 위 데이터 확인:

1

stack[-1]

시간 복잡도:

1
2
3

삽입 O(1)
삭제 O(1)
조회 O(1)

Python 구현

1
2
3
4
5
6
7
8

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

print(stack.pop())   # 30
print(stack[-1])     # 20

사용되는 경우

  • 괄호 문자열 검사
  • 문자열 뒤집기
  • Undo / Redo
  • 함수 호출 스택
  • DFS 탐색
  • 브라우저 뒤로 가기

2. 큐 (Queue)

개념

큐는 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조이다.

이를 FIFO (First In, First Out) 구조라고 한다.

은행 번호표 대기 시스템과 비슷하다.

  • 먼저 온 사람이 먼저 처리된다.
  • 뒤에 온 사람은 기다려야 한다.

주요 연산

삽입:

1

queue.append(x)

삭제:

1

queue.popleft()

맨 앞 확인:

1

queue[0]

Python 구현

1
2
3
4
5
6
7
8
9

from collections import deque

queue = deque()

queue.append(10)
queue.append(20)
queue.append(30)

print(queue.popleft())  # 10

왜 deque를 써야 하는가?

리스트:

1

arr.pop(0)

시간 복잡도:

1

O(n)

이유는 맨 앞 원소를 제거하면 뒤 원소들을 모두 한 칸씩 앞으로 당겨야 하기 때문이다.

하지만 deque:

1

queue.popleft()

시간 복잡도:

1

O(1)

입력이 커질수록 이 차이는 매우 크다.

사용되는 경우

  • BFS
  • 작업 대기열
  • 프로세스 스케줄링
  • 요청 처리
  • 네트워크 패킷 처리

3. 덱 (Deque)

개념

Deque는:

1

Double Ended Queue

양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조다.

즉:

  • 스택처럼 사용 가능
  • 큐처럼 사용 가능

둘의 장점을 모두 가진 구조다.

Python 구현

1
2
3
4
5
6
7
8
9

from collections import deque

dq = deque()

dq.append(10)
dq.appendleft(5)

print(dq.pop())
print(dq.popleft())

사용되는 경우

  • 회전 큐
  • 슬라이딩 윈도우
  • 양방향 탐색
  • 양쪽 삽입 삭제 문제

4. 힙 (Heap)

개념

힙은 우선순위가 높은 데이터를 빠르게 꺼내기 위한 자료구조이다.

Python은 기본적으로 최소 힙(Min Heap)을 제공한다.

즉 가장 작은 값이 먼저 나온다.

Python 구현

1
2
3
4
5
6
7
8
9

import heapq

heap = []

heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heapq.heappop(heap))

출력:

1

1

시간 복잡도

1
2
3

삽입 O(log n)
삭제 O(log n)
최솟값 조회 O(1)

사용되는 경우

  • 우선순위 큐
  • 다익스트라
  • 작업 스케줄링
  • 실시간 최소값 관리

5. 해시 (Hash)

개념

해시는 빠른 탐색을 위한 자료구조다.

Python에서는:

1
2

dict
set

이 대표적인 해시 기반 구조다.

평균 탐색 시간:

1

O(1)

Python 예시

1
2
3
4
5
6

count = {}

count["apple"] = 3
count["banana"] = 2

print(count["apple"])

사용되는 경우

  • 빈도수 계산
  • 빠른 검색
  • 중복 체크
  • 키-값 저장
  • 캐싱

6. 집합 (Set)

개념

중복 없는 데이터 집합.

Python:

1

set()

특징

  • 중복 제거
  • 빠른 탐색
  • 집합 연산 가능

예시

1
2
3
4
5
6

a = {1, 2, 3}
b = {3, 4, 5}

print(a & b)
print(a | b)
print(a - b)

문제 LIST

#57. 원형 전시대 정리

이 문제는 원형 전시대에서 원하는 인형을 창문 앞으로 최소 회전으로 가져오는 문제이다.
먼저 문제 규칙대로 초기 인형 배치를 만들어야 한다.

  • 홀수는 작은 순서
  • 짝수는 큰 순서

예를 들어 N=8이면:

1

1 3 5 7 8 6 4 2

원형 구조에서 시계/반시계 방향 회전이 필요하므로 deque를 사용했다.
각 목표 인형마다 현재 위치를 찾고,

  • 앞으로 돌리는 횟수 = 인덱스
  • 뒤로 돌리는 횟수 = 전체 길이 - 인덱스

를 계산해서 더 작은 쪽으로 회전한다.
인형이 맨 앞(창문 앞)에 오면 제거하고, 이 과정을 반복하면서 회전 횟수를 누적하면 된다.
즉, deque로 원형 구조 구현 + 양방향 회전 중 최소값 선택이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

from collections import deque

N = int(input())
targets = list(map(int, input().split(',')))

arr = []

for i in range(1, N + 1, 2):
    arr.append(i)

start_even = N if N % 2 == 0 else N - 1

for i in range(start_even, 0, -2):
    arr.append(i)

dq = deque(arr)

answer = 0

for target in targets:
    idx = dq.index(target)

    left_rotate = idx
    right_rotate = len(dq) - idx

    if left_rotate <= right_rotate:
        for _ in range(left_rotate):
            dq.append(dq.popleft())
        answer += left_rotate
    else:
        for _ in range(right_rotate):
            dq.appendleft(dq.pop())
        answer += right_rotate

    dq.popleft()

print(answer)

#100. 은박 카드 보정

이 문제는 각 카드를 비트마스크로 표현하면 쉽게 풀 수 있다.
각 층의 보이는 상태를 1, 가려진 상태를 0으로 두고 카드 상태를 저장한다.
기준 카드와 어떤 카드가 같아지려면 필요한 조작은:

1

현재 카드 상태 XOR 기준 카드 상태

같은 조작을 했을 때 여러 카드가 기준 카드와 같아질 수 있으므로, 필요한 조작 상태를 Counter로 세어준다.
단, 보정기는 정확히 K번 작동해야 한다.

가능 조건:

  • 필요한 뒤집기 수 <= K
  • (K - 필요한 뒤집기 수)가 짝수

남은 조작은 같은 층을 두 번 뒤집으면 원래대로 돌아오기 때문이다.
결국 가능한 조작 상태 중에서 가장 많이 등장한 개수를 출력하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import sys
from collections import Counter

data = list(map(int, sys.stdin.read().split()))
idx = 0

N = data[idx]
M = data[idx + 1]
K = data[idx + 2]
idx += 3

R = data[idx]
idx += 1

target = 0
for _ in range(R):
    side = data[idx]
    idx += 1
    target |= 1 << (side - 1)

cards = [0] * N

for side in range(1, M + 1):
    C = data[idx]
    idx += 1

    for _ in range(C):
        card_num = data[idx]
        idx += 1
        cards[card_num - 1] |= 1 << (side - 1)

cnt = Counter()

for state in cards:
    need = state ^ target
    cnt[need] += 1

answer = 0

for need, count in cnt.items():
    flip_count = need.bit_count()

    if flip_count <= K and (K - flip_count) % 2 == 0:
        answer = max(answer, count)

print(answer)

#31. 무한 선박의 인기 없는 칸

이미 상품이 있는 칸은 피자를 붙일 수 없으므로 c(x) = 0이다.
빈칸 x가 두 상품 사이에 있을 때, 왼쪽 상품을 prev, 오른쪽 상품을 p라고 하면:

  • c(x) = (x - prev) * (p - x)

이다.

중요한 점은 칸 번호가 최대 10억이라서 모든 빈칸을 후보로 만들면 메모리 초과가 난다.
하지만 출력해야 하는 개수는 최대 N = 100개뿐이다.

그래서 각 빈 구간에서 우선순위가 높은 칸을 최대 N개만 후보로 만든다.
빈 구간에서는 양쪽 끝에 가까운 칸일수록 c(x)가 작다.

예를 들어 구간이 있다면:

  • 상품 … 빈칸 … 상품

양쪽 끝부터 안쪽으로 들어가면서 후보를 만들면 된다.

정렬 기준은:

  1. c(x)가 작은 순서
  2. c(x)가 같으면 칸 번호가 작은 순서

후보를 정렬한 뒤 앞에서부터 N개를 출력하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import sys

input = sys.stdin.readline

L, N = map(int, input().split())
d = list(map(int, input().split()))

pos = []
cur = 0

for x in d:
    cur += x
    pos.append(cur)

candidates = []

for p in pos:
    candidates.append((0, p))

prev = 0

for p in pos:
    length = p - prev
    gap = length - 1

    limit = min(gap, N)

    made = 0
    k = 1

    while made < limit:
        left = prev + k
        right = p - k

        c = k * (length - k)

        candidates.append((c, left))
        made += 1

        if made >= limit:
            break

        if left != right:
            candidates.append((c, right))
            made += 1

        k += 1

    prev = p

candidates.sort()

answer = []

for _, x in candidates:
    if len(answer) == N:
        break
    answer.append(x)

x = pos[-1] + 1

while len(answer) < N:
    answer.append(x)
    x += 1

print('\n'.join(map(str, answer)))

#90. 단일 템플릿

같은 팀에 배정된 전광판들은 최종적으로 모두 같은 문자를 가져야 한다.
그래서 같은 팀에 있는 전광판 번호들을 하나의 그룹으로 묶으면 된다.

이때 사용하는 자료구조가 Union-Find이다.
이미 공식 화면으로 고정된 전광판은 반드시 Y여야 한다.

따라서 각 그룹에 대해:

  • 그룹 안에 고정된 Y가 있다 → 전체를 Y로 설정
  • 그룹 안에 고정된 Y가 없다 → 전체를 N으로 설정

하면 된다.

N의 개수를 최대화해야 하므로, 강제로 Y가 되어야 하는 그룹만 Y로 만들고 나머지는 전부 N으로 만든다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline

B, W = map(int, input().split())
S = input().strip()

c = list(map(int, input().split()))
arr = list(map(int, input().split()))

parent = list(range(B + 1))

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

def union(a, b):
    ra = find(a)
    rb = find(b)

    if ra != rb:
        parent[rb] = ra

#167. 돌림통 속 번호 스티커

이 문제는 deque로 풀면 된다.

반복 과정은 다음과 같다.

  1. 맨 앞 스티커를 K번 꺼내서 맨 뒤로 보낸다.
  2. 그 다음 맨 앞 스티커를 제거한다.
  3. 통이 빌 때까지 반복한다.

예제에서 K = 2이면:

  • 10 20 30 40 50

2번 뒤로 보내면:

  • 30 40 50 10 20

그 다음 제거되는 값은 30이다.

그래서 출력이:

  • 30 10 50 20 40

가 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from collections import deque

N = int(input())
stickers = deque(map(int, input().split()))
K = int(input())

answer = []

while stickers:
    for _ in range(K):
        stickers.append(stickers.popleft())

    answer.append(stickers.popleft())

print(*answer)

#91. 해와 달 전시

이 문제는 패널 자체를 직접 뒤집는 것이 아니라, 현재 M의 개수만 상태로 보면 된다.
한 턴에서 정확히 K개를 뒤집을 때,

  • 뒤집는 M 개수 = a
  • 뒤집는 S 개수 = K - a

라고 하면 다음 M 개수는

  • 다음 M 개수 = 현재 M 개수 - a + (K - a)

이다.

즉 가능한 M 개수들을 BFS로 탐색하면서, 점수가 T 이상이 되는 가장 빠른 턴을 찾으면 된다.

  • 패널 문자열 전체를 상태로 보지 말고,
  • M의 개수만 상태로 본다.
그래서 상태 수는 최대 W + 1개라서 충분히 탐색 가능하다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

from collections import deque
import sys

input = sys.stdin.readline

K, T = map(int, input().split())
W = input().strip()

n = len(W)
start_m = W.count('M')

# 점수 = 2*(n-m) - m = 2n - 3m
# 2n - 3m >= T 를 만족해야 함
if T > 2 * n:
    print(-1)
    exit()

target_m = (2 * n - T) // 3

if start_m <= target_m:
    print(0)
    exit()

parent = list(range(n + 3))

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

def remove(x):
    parent[x] = find(x + 2)

q = deque()
q.append((start_m, 0))
remove(start_m)

while q:
    m, dist = q.popleft()

    # 현재 M개수 m에서 정확히 K개를 뒤집는다.
    # a = 뒤집는 M의 개수
    # K-a = 뒤집는 S의 개수

    a_min = max(0, K - (n - m))
    a_max = min(K, m)

    low = m + K - 2 * a_max
    high = m + K - 2 * a_min

    parity = (m + K) % 2

    if low % 2 != parity:
        low += 1

    x = find(low)

    while x <= high:
        next_m = x

        if next_m <= target_m:
            print(dist + 1)
            exit()

        q.append((next_m, dist + 1))
        remove(next_m)

        x = find(x)

print(-1)

#61. 보강끈 점검표

이 문제는 MST가 아니라 정확히 M개의 다리를 선택해야 하는 완전탐색 문제다.

다리를 우선순위대로 정렬한 뒤:

  • 길이 짧은 순
  • 같으면 시작 번호 작은 순

정확히 M개를 고르는 모든 조합을 확인한다.

각 조합마다:

  • 모든 기둥이 연결되는지 확인
  • 연결되면 길이별 개수 출력

첫 번째로 나오는 조합이 가장 좋은 답이다.

정확히 M개 선택 + 연결 여부 체크

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

from itertools import combinations

N, M = map(int, input().split())

bridges = []

for d in range(1, N):
    s = input().strip()

    for i, ch in enumerate(s):
        if ch == '1':
            bridges.append((d, i, i + d))

bridges.sort()

def connected(selected):
    parent = list(range(N))

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

    def union(a, b):
        ra = find(a)
        rb = find(b)
        if ra != rb:
            parent[rb] = ra

    cnt = [0] * N

    for d, a, b in selected:
        union(a, b)
        cnt[d] += 1

    root = find(0)

    for i in range(1, N):
        if find(i) != root:
            return None

    return cnt

for comb in combinations(bridges, M):
    result = connected(comb)

    if result:
        print(*result[1:])
        break

else:
    print(-1)

#155. 부스 사이 길바꾸기

BFS로 각 연결 요소를 찾으면서:

  • 정점 수
  • 간선 수

를 같이 센다.

간선 수는 각 정점의 연결 개수를 모두 더한 뒤 2로 나누면 된다.

  • edge_count = degree_sum // 2

각 연결 요소의 사이클 개수는:

  • 간선 수 - 정점 수 + 1

전체를 하나로 만들려면 연결 요소가 C개일 때 최소 C - 1번 필요하다.

가능 조건은:

  • 고립된 부스가 없어야 함
  • 전체 사이클 수 >= C - 1

가능하면 C - 1, 아니면 -1 출력.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

from collections import deque
import sys

input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]

for i in range(N):
    arr = list(map(int, input().split()))
    cnt = arr[0]

    for x in arr[1:]:
        graph[i].append(x - 1)

visited = [False] * N

components = 0
isolated = False
total_cycle = 0

for i in range(N):
    if not visited[i]:
        components += 1

        q = deque([i])
        visited[i] = True

        vertex_count = 0
        degree_sum = 0

        while q:
            cur = q.popleft()
            vertex_count += 1
            degree_sum += len(graph[cur])

            for nxt in graph[cur]:
                if not visited[nxt]:
                    visited[nxt] = True
                    q.append(nxt)

        edge_count = degree_sum // 2

        if edge_count == 0:
            isolated = True

        total_cycle += edge_count - vertex_count + 1

if components == 1:
    print(0)
elif isolated:
    print(-1)
elif total_cycle >= components - 1:
    print(components - 1)
else:
    print(-1)

#103. 닫히는 순서의 상자

이 문제는 괄호 구조를 상자 트리로 보면 된다.

중요한 점은 상자 번호가:

  • 여는 순서 X
  • 닫히는 순서 O

라는 것이다.

빈 상자는 자식 상자가 없는 상자이다.
K번 상자를 버리면:

  • K번 상자 + 그 안의 모든 상자

가 사라진다.

그래서:

  • 전체 빈 상자 수 - K번 상자 내부의 빈 상자 수

를 계산한다.

추가로 K번 상자를 지웠을 때, 부모 상자가 자식을 모두 잃으면 새로 빈 상자가 되므로 +1 해준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import sys

input = sys.stdin.readline

N = int(input())
S = input().strip()
K = int(input())

parent_temp = [0] * (N + 1)
child_count_temp = [0] * (N + 1)
leaf_sum_temp = [0] * (N + 1)

id_of_temp = [0] * (N + 1)
temp_of_id = [0] * (N + 1)

child_count = [0] * (N + 1)
subtree_leaf = [0] * (N + 1)

stack = [0]
temp_num = 0
box_id = 0

for ch in S:
    if ch == '(':
        temp_num += 1
        cur = temp_num
        parent = stack[-1]

        parent_temp[cur] = parent
        child_count_temp[parent] += 1

        stack.append(cur)

    else:
        cur = stack.pop()

        box_id += 1
        id_of_temp[cur] = box_id
        temp_of_id[box_id] = cur

        child_count[box_id] = child_count_temp[cur]

        if child_count_temp[cur] == 0:
            subtree_leaf[box_id] = 1
        else:
            subtree_leaf[box_id] = leaf_sum_temp[cur]

        parent = parent_temp[cur]
        leaf_sum_temp[parent] += subtree_leaf[box_id]

parent_id = [0] * (N + 1)

for i in range(1, N + 1):
    temp = temp_of_id[i]
    ptemp = parent_temp[temp]

    if ptemp != 0:
        parent_id[i] = id_of_temp[ptemp]

total_leaf = 0

for i in range(1, N + 1):
    if child_count[i] == 0:
        total_leaf += 1

answer = total_leaf - subtree_leaf[K]

p = parent_id[K]

if p != 0 and child_count[p] == 1:
    answer += 1

print(answer)

#160. 테이블 사이 충전선

이 문제는 MST 문제다.

생각해보면:

  • 충전기 설치 = 가상 정점 0과 연결
  • 케이블 연결 = 테이블끼리 연결

그래프가 된다.

  • 0 ↔ i : 충전기 비용
  • i ↔ j : 케이블 비용

이 그래프의 MST를 구하면 최소 유지 비용.

초기 비용:

  • sum(A)

절약 금액:

  • sum(A) - MST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

edges = []

# 가상 정점(충전기 설치)
for i in range(N):
    edges.append((A[i], 0, i + 1))

# 삼각형 입력
for i in range(1, N):
    arr = list(map(int, input().split()))

    for j, cost in enumerate(arr):
        edges.append((cost, i, i + j + 1))

edges.sort()

parent = list(range(N + 1))

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

def union(a, b):
    ra = find(a)
    rb = find(b)

    if ra == rb:
        return False

    parent[rb] = ra
    return True

mst = 0

for cost, a, b in edges:
    if union(a, b):
        mst += cost

print(sum(A) - mst)

#156. 서랍 앞 큰 이름표

이름표 하나가 필요한 너비:

  • 3*A - 1

너비 W인 사람만 그 이름표 사용 가능.

각 이름표는:

  • 최대 1번 사용

각 사람은:

  • 최대 1개 사용

그러므로 조건을 만족하는 사람에게 점수가 가장 큰 이름표를 우선 배정하는 게 최적.

방법:

  1. 이름표를 필요한 너비 기준 정렬
  2. 사람 그룹을 너비 기준 정렬
  3. 현재 사람 너비로 붙일 수 있는 이름표들을 heap에 넣기
  4. 점수 가장 큰 이름표부터 배정

그리디 + 우선순위 큐(heap)

시간복잡도:

  • O((N + D) log N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import sys
import heapq

input = sys.stdin.readline

N, D = map(int, input().split())

A = list(map(int, input().split()))
P = list(map(int, input().split()))

tags = []

for i in range(N):
    need = 3 * A[i] - 1
    tags.append((need, P[i]))

people = []

for _ in range(D):
    w, c = map(int, input().split())
    people.append((w, c))

tags.sort()
people.sort()

heap = []
idx = 0
answer = 0

for w, c in people:
    while idx < N and tags[idx][0] <= w:
        heapq.heappush(heap, -tags[idx][1])
        idx += 1

    while c > 0 and heap:
        answer += -heapq.heappop(heap)
        c -= 1

print(answer)

#118. 중앙 주문 출고 스트림

이 문제는 중앙값을 계속 꺼내는 문제다.

조건:

  • 개수가 홀수 → 정확한 중앙값
  • 개수가 짝수 → 중앙값 중 작은 값

이걸 빠르게 처리하려면 힙 2개 사용.

left (최대힙)

작은 절반 저장

  • 중앙값 포함

right (최소힙)

큰 절반 저장

항상:

1
2
3

len(left) == len(right)
또는
len(left) == len(right)+1

상태 유지.
그러면 중앙값은 항상:

  • -left[0]

이 된다.

’#’ 나오면:

  • 중앙값 출력
  • 제거
  • 균형 다시 맞춤

투 힙(two heaps)으로 동적 중앙값 관리

시간복잡도:

  • 각 연산 O(log N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import sys
import heapq

input = sys.stdin.readline

left = []   # 작은 절반 (최대힙처럼 사용)
right = []  # 큰 절반 (최소힙)

answer = []

for line in sys.stdin:
    line = line.strip()

    if line == '#':
        # 중앙값 출력
        median = -heapq.heappop(left)
        answer.append(str(median))

        # 균형 맞추기
        if len(right) > len(left):
            heapq.heappush(left, -heapq.heappop(right))

    else:
        x = int(line)

        if not left or x <= -left[0]:
            heapq.heappush(left, -x)
        else:
            heapq.heappush(right, x)

        # 균형 유지
        if len(left) < len(right):
            heapq.heappush(left, -heapq.heappop(right))
        elif len(left) > len(right) + 1:
            heapq.heappush(right, -heapq.heappop(left))

print('\n'.join(answer))

#138. 운동회 조끼 나눔

#116. 관측 구간 혼잡도

각 장치의 관측 구간은 자기보다 감도가 큰 가장 가까운 장치에 의해 결정된다.

그래서 먼저 단조 스택으로 각 장치의 구간 [L, R]을 구한다.
그 다음 기준값 B가 주어지면 감도 S_i <= B인 장치들이 활성화된다.
활성화된 장치들의 구간을 세그먼트 트리에 +1로 추가하고, 전체 구간 중 최댓값을 구하면 된다.

  • 단조 스택으로 관측 구간 계산
  • 쿼리를 B 기준 오름차순 정렬
  • 세그먼트 트리로 구간 추가 + 최댓값 관리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = list(map(int, input().split()))

# 왼쪽에서 나보다 감도가 큰 가장 가까운 장치
L = [0] * N
stack = []

for i in range(N):
    while stack and S[stack[-1]] <= S[i]:
        stack.pop()

    if stack:
        L[i] = stack[-1] + 1
    else:
        L[i] = 0

    stack.append(i)

# 오른쪽에서 나보다 감도가 큰 가장 가까운 장치
R = [0] * N
stack = []

for i in range(N - 1, -1, -1):
    while stack and S[stack[-1]] <= S[i]:
        stack.pop()

    if stack:
        R[i] = stack[-1] - 1
    else:
        R[i] = N - 1

    stack.append(i)

devices = []

for i in range(N):
    devices.append((S[i], L[i], R[i]))

devices.sort()

queries = []
for idx in range(Q):
    b = int(input())
    queries.append((b, idx))

queries.sort()

size = 1
while size < N:
    size *= 2

tree = [0] * (size * 2)
lazy = [0] * (size * 2)

def push(node):
    if lazy[node]:
        for child in (node * 2, node * 2 + 1):
            tree[child] += lazy[node]
            lazy[child] += lazy[node]
        lazy[node] = 0

def update(node, start, end, left, right):
    if right < start or end < left:
        return

    if left <= start and end <= right:
        tree[node] += 1
        lazy[node] += 1
        return

    push(node)

    mid = (start + end) // 2
    update(node * 2, start, mid, left, right)
    update(node * 2 + 1, mid + 1, end, left, right)

    tree[node] = max(tree[node * 2], tree[node * 2 + 1])

answer = [0] * Q
idx = 0

for b, qidx in queries:
    while idx < N and devices[idx][0] <= b:
        _, l, r = devices[idx]
        update(1, 0, size - 1, l, r)
        idx += 1

    answer[qidx] = tree[1]

print('\n'.join(map(str, answer)))

문제 CLEAR

이번 미션을 통해 배운 점

가장 크게 느낀 점은 자료구조는 암기 과목이 아니라는 것이다.
단순히 정의를 외우는 것이 아니라 문제 상황에서 어떤 도구를 선택해야 하는지 판단하는 능력
이 중요하다는 걸 느꼈다.

예전에는 그냥 리스트 하나로 다 해결하려고 했지만, 이제는 왜 특정 자료구조를 써야 하는지 조금씩 보이기 시작했다.

특히 시간 복잡도 개념이 훨씬 와닿았다.

예:

1
2

리스트 앞 삭제 → O(n)
deque 앞 삭제 → O(1)

이 차이가 실제 정답 여부를 가른다.

마무리

LOJ 자료구조 입문 문제집을 풀며 단순히 문제를 푸는 것에서 끝나는 것이 아니라:

  • 개념 이해
  • 시간 복잡도 이해
  • 실제 적용 경험

까지 얻을 수 있었다.

앞으로 더 어려운 알고리즘 문제를 풀기 전에 이런 기본기를 확실히 다지는 것이 중요하다고 느꼈다.
이번 미션을 통해 자료구조에 대한 막연한 두려움이 줄었고,
문제를 볼 때 어떤 자료구조를 활용해야할지 조금은 생각할수있을거같다.