1. [Python] BOJ 2243 사탕상자

0. 탐색 기반 설계 및 관계 기반 설계 탐구

3월 주제가 탐색 기반 설계 및 관계 기반 설계를 탐구하고 관련 문제를 해결하는 것이었기 때문에 관련 내용을 먼저 조사했다.

 

탐색 기반 설계: 주어진 문제에서 주어진 데이터를 특성에 맞도록 구조화하고 이 자료를 적절한 방법으로 탐색해 나가면서 원하는 해를 찾는 알고리즘 설계법. 전체를 탐색하는 전체탐색법과 탐색할 영역을 적절한 방법으로 배제하여 탐색의 효율을 높은 부분 탐색법이 있다. 또한 구조에 따라 선형 구조와 비선형 구조로 나눌 수 있다.

선형 구조 탐색: 자료의 순서를 유일하게 결정할 수 있는 형태의 구조. i번째 자료를 탐색한 다음, i+1번째 자료를 탐색하는 방식이다. 순차탐색과 이분 탐색이 존재한다.

비선형 구조 탐색: i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 여러 개의 원소가 존재하는 탐색구조. 자료가 트리나 그래프로 구성되어 있을 경우 비선형 구조를 의미하고, 이를 모두 탐색하는 것을 비선형 탐색이라 한다. 스택이나 큐와 같은 자료구조를 활용하여 탐색하는 것이 일반적이다. 일반적으로 깊이우선탐색(DFS)와 너비우선탐색(BFS)로 나뉜다.

 

관계 기반 설계: 해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 방법. 문제의 정의 및 상태를 함수로 정의하고, 이 함수들 간의 관계를 점화식 혹은 이와 유사한 형태로 표현하며, 수학적 귀납법이나 점화식 등의 표현을 기반으로 작동한다.

수학적 귀납법: 자연수 n에 관한 명제 P(n)이 모든 자연수에 대해서 성립함을 증명하기 위한 수학의 증명법 중 한 방법

분할 정복: 문제 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘

재귀 함수: 정의 단계에서 자신을 재참조하는 함수. 자기 자신을 반복적으로 호출하면서 문제를 해결함.

1. 문제 링크

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

2243번: 사탕상자

2. 문제 선정 과정 및 문제 내용

3월 과제는 탐색기반설계를 탐구하고 이를 이용하여 풀 수 있는 문제를 해결하는 것이었다. 이를 위해 나는 백준 온라인 저지 사이트에서 트리를 사용한 이분 탐색 문제를 찾아보았고, 정답률이 50% 이하인 도전적인 문제 중 본 문제가 흥미로워 보여서 선정하게 되었다. 

 

문제 내용

화질이 좀 안좋은데 이해 부탁드립니다

3. 사용한 문제 풀이 전략

본 문제를 효과적으로 해결하기 위해 세그먼트 트리를 이용한 이분 탐색 알고리즘을 세웠다.

 

3 - 1. 세그먼트 트리

 

세그먼트 트리란 구간을 저장하기 위한 트리이다. 더 풀어 말하면 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다. 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. 기존 배열의 경우 특정 시작 인덱스부터 끝 인덱스까지 부분합을 구하려면 그 범위의 원소를 하나씩 다 더해야 해서 시간 복잡도는 O(N)이다. 그러나 세그먼트 트리를 사용하면 O(logN)의 시간 복잡도로 빠르게 구할 수 있다.

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

위 리스트를 이용하여 세그먼트 트리에 대해 설명하겠다. 밑의 그림은 본 리스트에 대한 세그먼트 트리의 구조이다.

세그먼트 트리의 구조

먼저 루트 노드부터 보자. 세그먼트 트리의 루트 노드에는 0번째부터 9번째 인덱스까지의 구간 합이 들어가고 루트 노드는 1번 인덱스가 된다. 루트 노드의 왼쪽 자식 노드의 번호는 2번이 되며, 0번 인덱스에서 (0+9)//2번 인덱스, 즉 0~4번 인덱스까지의 구간 합이 삽입된다. 오른쪽 자식 노드의 번호는 3번이 되며, (0+9)//2+`번 인덱스에서 끝까지, 즉 5~9번 인덱스까지의 구간 합이 삽입된다. 이러한 방식으로 시작 인덱스와 끝 인덱스가 같아질 때까지 세그먼트 트리의 원소를 채워주게 된다. 이때 보통 리스트의 인덱스는 0번부터 시작하는데, 세그먼트 트리는 왜 1번부터 시작할까? 그 이유는 세그먼트 트리를 재귀적으로 편하게 생성하기 위해서이다. 특정 노드의 인덱스가 n이라면 2*n 번째 노드는 왼쪽 자식 노드를 가리키고, 2*n+1 번째 노드는 오른쪽 자식 노드를 가리키게 되어 효과적이기 때문이다. 세그먼트 트리는 두 자식 노드 값의 합이 루트 노드가 된다는 특징이 있다. 한편 세그먼트 트리를 생성할 때는 보통 리스트의 길이에 4를 곱한 크기로 생성하는데, 엄밀히 따지면 리스트의 길이가 N일 때 N보다 큰 가장 가까운 제곱수를 구한 뒤에 그것의 2배를 하여 크기를 만들어야하나 넉넉하게 트리를 생성하는 것이다. 따라서 세그먼트 트리를 생성하고 그 값을 채워주는 코드는 다음과 같다.

tree = [0] * (len(arr) * 4)

# start : 배열의 시작 인덱스, end : 배열의 마지막 인덱스
# index : 세그먼트 트리의 인덱스 (무조건 1부터 시작)
def init(start, end, index):
    # 가장 끝에 도달했으면 arr 삽입
    if start == end:
        tree[index] = arr[start]
        return tree[index]
    mid = (start + end) // 2
    # 좌측 노드와 우측 노드를 채워주면서 부모 노드의 값도 채워준다.
    tree[index] = init(start, mid, index * 2) + init(mid + 1, end, index * 2 + 1)
    return tree[index]

 

위 세그먼트 트리에서 arr[6] 값을 수정한다고 하면 어떻게 해야 할까? 6번째 인덱스가 시작 인덱스와 끝 인덱스 사이 범위에 포함되는 노드의 값을 모두 수정해주면 된다.

붉은색으로 칠해진 노드를 모두 수정해주어야 한다.

노드의 값을 수정하는 함수는 바꾸려는 값의 인덱스가 범위 안에 있는 경우에 한하여 수정하도록 재귀적으로 작성할 수 있다.

# start : 시작 인덱스, end : 마지막 인덱스
# what : 구간 합을 수정하고자 하는 노드
# value : 수정할 값
def update(start, end, index, what, value):
    # 범위 밖에 있는 경우
    if what < start or what > end:
        return
    # 범위 안에 있으면 내려가면서 다른 원소도 갱신
    tree[index] += value
    if start == end:
        return
    mid = (start + end) // 2
    update(start, mid, index * 2, what, value)
    update(mid + 1, end, index * 2 + 1, what, value)

 

* 세그먼트 트리에 대한 설명에서 참고한 자료

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree

[자료구조] 세그먼트 트리 (Segment Tree)

 

3 - 2. 문제에 세그먼트 트리 적용

 

1. 세그먼트 트리 초기화: 사탕의 맛이 1부터 1,000,000 까지의 등급(?)으로 구분되므로, 이 범위를 전체로 하는 세그먼트 트리를 초기화한다. 각 노드는 해당 구간에 있는 사탕의 개수를 저장한다.

MAX = 1000000
tree = [0]*(MAX*4)

 

2. 특정 순위(rank)의 사탕 찾기: 세그먼트 트리를 사용하는 주된 이유가 되는 항목이다. 세그먼트 트리를 사용하였을 때 특정 순위의 사탕을 가장 빠르게 찾을 수 있기 때문이다. 특정 순위의 사탕을 찾으려면, 세그먼트 트리의 그 순위에 해당하는 리프노드(자식이 없는 가장 말단노드)까지 찾아야 찾고자 하는 순위의 사탕의 맛을 알 수 있다. 이때 루트 노드부터 시작하여 왼쪽 자식 노드에 있는 사탕의 개수가 찾으려는 순위보다 큰지 확인하는 과정이 필요하다. 만약 크다면 왼쪽 자식 노드에 그 사탕이 있다는 것이고, 작다면 오른쪽 자식 노드에 그 사탕이 있다는 것을 의미하기 때문이다. 이때 만약 왼쪽 자식 노드에 있는 사탕의 개수가 찾으려는 순위보다 작다면 찾으려는 순위에서 왼쪽 자식 노드에 있는 사탕의 개수를 뺀 후 오른쪽으로 이동한다. 왜냐하면 왼쪽 노드에 있는 사탕의 개수는 찾으려는 순위보다 높은 순위들의 사탕이기 때문이다. 예를 들어 왼쪽 노드에 2개의 사탕이 있는데 3번째로 맛있는 사탕을 찾아야 하면 오른쪽 노드에서 3-2=1번째로 맛있는 사탕을 찾으면 된다. 위 과정을 재귀적으로 구현한 코드는 다음과 같다.

def query(node, start, end, rank):
    if start == end:
        return start
    mid = (start+end)//2
    left = tree[node*2]
    if left >= rank:
        return query(node*2, start, mid, rank)
    return query(node*2+1, mid+1,end, rank-left)

 

3. 사탕 넣거나 빼기: 사탕을 넣가나 뺄 때는 해당하는 사탕의 맛에 해당하는 인덱스의 값을 갱신하는 것이므로, 특정 맛을 가진 사탕이 범위에 포함될 경우에만 노드를 모두 업데이트해주면 된다. 문제 입력에서 사탕을 n개만큼 넣을 경우 n, 뺄 경우 -n이 입력으로 들어오기 때문에 n또는 -n씩 노드를 업데이트해주면 된다. 이 n또는 -n을 diff라는 매개변수로 하여 업데이트하는 함수를 작성하면 다음과 같다.

def update(node, start, end, idx, diff):
    if end < idx or idx < start:
       return
    tree[node] += diff
    if start != end:
        mid = (start+end)//2
        update(node*2, start, mid, idx, diff)
        update(node*2+1, mid+1, end, idx, diff)

 

위 과정들을 모두 적용하여 문제 해결을 위한 전체 코드이다.

MAX = 1000000
tree = [0]*(MAX*4)

def query(node, start, end, rank):
    if start == end:
        return start
    mid = (start+end)//2
    left = tree[node*2]
    if left >= rank:
        return query(node*2, start, mid, rank)
    return query(node*2+1, mid+1,end, rank-left)

def update(node, start, end, idx, diff):
    if end < idx or idx < start:
       return
    tree[node] += diff
    if start != end:
        mid = (start+end)//2
        update(node*2, start, mid, idx, diff)
        update(node*2+1, mid+1, end, idx, diff)

n = int(input())
answer = []
for i in range(n):
    s = list(map(int, input().split()))
    if s[0] == 1:
        ans = query(1, 1, MAX, s[1])
        answer.append(ans)
        update(1, 1, MAX, ans, -1)
    elif s[0] == 2:
        update(1, 1, MAX, s[1], s[2])
for i in answer:
    print(i)

 

4. 시행착오

처음 세그먼트 트리를 적용하지 않고 풀려고 시도했을 때에는 구현 과정이 구조화되지 않아 여러 오류를 겪었고, 시간 초과가 발생하였다. 따라서 '이진 트리를 사용한 이분 탐색으로 문제 해결하기'라는 목표에 맞게 사용할만한 이진 트리에 대해 공부하였고, 그 결과로 세그먼트 트리라는 자료구조를 공부하면서 본 자료구조를 사용하면 특정 순위의 사탕을 비교적 쉽고 빠르게 찾을 수 있을 것 같다는 생각이 들어 적용시켰다. 세그먼트 트리 적용 과정에서도 왼쪽 자식 노드에 있는 사탕의 개수가 찾으려는 순위보다 큰지를 확인하는 과정을 떠올리기가 어려웠었는데, 왼쪽이 기존 노드의 앞 절반, 오른쪽이 뒤 절반을 각각 범위로 잡는다는 세그먼트 트리의 개념을 활용해서 특정 맛의 사탕이 왼쪽과 오른쪽 중 어느 자식 노드에 있을지를 알아낼 수 있었다.

 

5. 느낀점

본 문제를 풀어보면서 세그먼트 트리라는 자료구조를 처음 공부하게 되었는데, 이번 문제처럼 본 자료구조를 다양한 문제에 적용시켜 시간 복잡도를 줄일 수 있겠다라는 생각이 들었다. 또한 본 경험이 이진 트리를 사용하여 문제를 해결해보는 첫 시도이기도 했는데, 처음엔 어려워 보였지만 학습을 통해 문제를 해결하게 되어 상당히 뿌듯하고 재미있는 시간이었다. 이진 트리를 이용한 또 다른 이분 탐색 문제를 해결해보고 싶다는 생각도 들었다.