EDOC 2023-W 6회차 과제 (이진 트리 / 세그먼트 트리)

09-3. 이진 트리

 

070. 트리 순회 (백준 1991번)

 

https://www.acmicpc.net/problem/1991

 

from sys import stdin

n = int(stdin.readline())
tree = {}

for _ in range(n):
    self, left, right = stdin.readline().split()
    tree[self] = [left, right]

def preOrder(now):
    if now != '.':
        print(now, end='')
        preOrder(tree[now][0])
        preOrder(tree[now][1])

def inOrder(now):
    if now != '.':
        inOrder(tree[now][0])
        print(now, end='')
        inOrder(tree[now][1])

def postOrder(now):
    if now != '.':
        postOrder(tree[now][0])
        postOrder(tree[now][1])
        print(now, end='')

preOrder('A')
print()
inOrder('A')
print()
postOrder('A')

전위 순회, 중위 순회, 후위 순회의 개념만 알면 재귀로 쉽게 풀 수 있었던 문제. 함수의 기본틀은 그대로 두고 순서만 조금씩 바꾸면 된다. (정답)

 

---

09-4. 세그먼트 트리

 

071. 구간 합 구하기 (백준 2042번)

 

https://www.acmicpc.net/problem/2042

 

from sys import stdin
import math

n, m, k = map(int, stdin.readline().split())
treeHeight = math.ceil(math.log2(n)) + 1
treeSize = pow(2, treeHeight)
leafIndex = treeSize // 2
tree = [0] * (treeSize)

def change(b, c):
    index = leafIndex + b - 1
    diff = c - tree[index]
    while index != 0:
        tree[index] += diff
        index //= 2

def sum(b, c):
    s = leafIndex + b - 1
    e = leafIndex + c - 1
    res = 0
    while s <= e:
        if s % 2 == 1:
            res += tree[s]
            s += 1
        if e % 2 == 0:
            res += tree[e]
            e -= 1
        s //= 2
        e //= 2
    return res

for i in range(leafIndex, leafIndex + n):
    tree[i] = int(stdin.readline())

i = treeSize - 1
while i != 1:
    tree[i // 2] += tree[i]
    i -= 1

for _ in range(m + k):
    a, b, c = map(int, stdin.readline().split())
    if a == 1:
        change(b, c)
    elif a == 2:
        print(sum(b, c))

처음에 세그먼트 트리 이론 부분을 읽기만 하니 이해가 잘 안 되었는데, 직접 처음부터 코드를 짜보니 이해가 잘 되었다. 굳이 교재 인덱스 또는 변수로 한다기 보다는 살짝 달라도 자기가 편한 대로 잡아두는 게 더 편한 것 같다. 핵심은 트리 사이즈를 잘 계산하고 트리를 만들어 둬서 이론에서 배운대로 업데이트 시키고 부분합을 구하는 것이었다. (정답)

 

---

 

072. 최솟값 (백준 10868번)

 

https://www.acmicpc.net/problem/10868

 

from sys import stdin
import math
import sys
sys.setrecursionlimit(10 ** 8)

n, m = map(int, stdin.readline().split())
treeHeight = math.ceil(math.log2(n)) + 1
treeSize = pow(2, treeHeight)
leafIndex = treeSize // 2
tree = [sys.maxsize] * (treeSize)

def min(a, b):
    s = leafIndex + a - 1
    e = leafIndex + b - 1
    res = sys.maxsize
    while s <= e:
        if s % 2 == 1:
            res = min(res, tree[s])
            s += 1
        if e % 2 == 0:
            res = min(res, tree[e])
            e -= 1
        s //= 2
        e //= 2
    return res

for i in range(leafIndex, leafIndex + n):
    tree[i] = int(stdin.readline())

# 트리 초기화
i = treeSize - 1
while i != 1:
    if tree[i] < tree[i // 2]:
        tree[i // 2] = tree[i]
    i -= 1

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    print(min(a, b))

 

우선 앞의 구간합 구하는 문제와 틀은 매우 비슷하고 합을 구하는 것에서 최솟값을 구하는 것으로 일부만 조금 수정해주면 되는 문제였다. 그런데 계속 답이 이상하게 나오길래 디버깅을 해봤는데, 내가 의도한 대로 움직이지 않는 것을 확인했다. 왜 그럴까 몇시간을 고민하다가 다음날이 되어서야 발견했다. 원래 내장 함수 min과 내가 만든 함수 min이 이름이 같아서 그런 것 같다. 

 

from sys import stdin
import math
import sys
sys.setrecursionlimit(10 ** 8)

n, m = map(int, stdin.readline().split())
treeHeight = math.ceil(math.log2(n)) + 1
treeSize = pow(2, treeHeight)
leafIndex = treeSize // 2
tree = [sys.maxsize] * (treeSize)

def getMin(a, b):
    s = leafIndex + a - 1
    e = leafIndex + b - 1
    res = sys.maxsize
    while s <= e:
        if s % 2 == 1:
            res = min(res, tree[s])
            s += 1
        if e % 2 == 0:
            res = min(res, tree[e])
            e -= 1
        s //= 2
        e //= 2
    return res

for i in range(leafIndex, leafIndex + n):
    tree[i] = int(stdin.readline())

# 트리 초기화
i = treeSize - 1
while i != 1:
    if tree[i] < tree[i // 2]:
        tree[i // 2] = tree[i]
    i -= 1

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    print(getMin(a, b))

특정 구간에서 최솟값 구하는 함수의 이름을 min에서 getMin으로 바꾸어주니 정삭적으로 작동하는 것을 확인할 수 있었다. (정답)

 

---

 

073. 구간 곱 구하기 (백준 11505번)

 

https://www.acmicpc.net/problem/11505

 

import sys
import math
input = sys.stdin.readline

div = 1000000007
n, m, k = map(int, input().split())
treeHeight = math.ceil(math.log2(n)) + 1
treeSize = pow(2, treeHeight)
leafIndex = treeSize // 2
tree = [1] * treeSize

def change(b, c):
    index = leafIndex + b - 1
    tree[index] = c
    if index % 2 == 0:
        nxt = index + 1
    else:
        nxt = index - 1
    while index != 1:
        tree[index // 2] = tree[index] * tree[nxt]
        tree[index // 2] %= div
        index //= 2
        if index % 2 == 0:
            nxt = index + 1
        else:
            nxt = index - 1

def getAns(b, c):
    s = leafIndex + b - 1
    e = leafIndex + c - 1
    res = 1
    while s <= e:
        if s % 2 == 1:
            res *= tree[s]
            res %= div
            s += 1
        if e % 2 == 0:
            res *= tree[e]
            res %= div
            e -= 1
        s //= 2
        e //= 2
    return res

for i in range(leafIndex, leafIndex + n):
    tree[i] = int(input())

i = treeSize - 1
while i != 1:
    tree[i // 2] *= tree[i]
    tree[i // 2] %= div
    i -= 1

for _ in range(m + k):
    a, b, c = map(int, input().split())
    if a == 1:
        change(b, c)
    elif a == 2:
        print(getAns(b, c))

처음에는 tree[index] //= pre, tree[index] *= c 이런식으로 이전 값으로 나누고 새로운 값을 곱하는 형태로 코드를 짰다. 그런데 예제2를 입력으로 넣으니 오류가 나는 것을 확인할 수 있었다. ZeroDivisionError: integer division or modulo by zero 즉, 0으로 나누는 상황이 발생하기 때문이었다. 그래서 아예 곱을 다시 구하는 것으로 수정해주었다. 그리고 값이 1000000007이 넘지 않도록 중간중간 계속 나눠주는 연산을 해주어야 한다는 것을 주의해야 한다. (그렇지 않으면 출력초과가 난다...) (정답)