알면 도움되는 코딩 테스트 유형: 1) #Segtree

• 이번에는 '세그먼트 트리(Segment Tree)'에 대해 알아보겠습니다. 세그먼트 트리는 코딩 테스트에서 자주 활용되는 자료 구조 중 하나이며, 세그먼트 트리의 개념과 문제 해결 방법을 이해하는 것은 코딩 테스트에서 도움이 됩니다.

 

세그먼트 트리의 개념

 

• 세그먼트 트리는 배열 형태의 데이터를 분할하여 구간 합, 최소값, 최대값 등을 빠르게 계산하기 위한 자료 구조입니다. 주로 배열의 구간에 대한 질의(Query)를 처리하는 데 사용됩니다.
• 세그먼트 트리는 완전 이진 트리 형태를 가지며, 각 노드가 해당 구간의 정보(합, 최소값 등)를 가지고 있습니다. 이러한 성질을 활용하여 원래 배열의 범위를 분할하고 각 구간에 대한 정보를 저장하므로써 질의 연산을 빠르게 수행할 수 있습니다.

 

세그먼트 트리 문제 접근 방법

 

• 코딩 테스트에서 세그먼트 트리 문제를 해결하기 위해서는 아래와 같은 접근 방법을 활용할 수 있습니다.

 

1. 문제 이해와 제약 사항 파악: 주어진 문제를 정확하게 이해하고, 입력 조건과 제약 사항을 파악합니다.
2. 세그먼트 트리 설계: 주어진 조건과 목표에 맞추어 필요한 세그먼트 트리를 설계합니다. 각 노드가 어느 범위의 값을 나타내며 어떤 정보(합, 최소값 등)가 저장되어야 하는지 정확히 파악해야 합니다.
3. 구간 합 / 최소값 / 최대값 계산: 주어진 질의(Query)에 따라 세그먼트 트리 내에서 필요한 연산(구간 합 계산, 최소값 찾기 등)을 수행합니다.
4. 업데이트 작성: 배열의 값이 변경되는 경우에는 세그먼트 트리를 업데이트해야 합니다. 업데이트 작업은 해당하는 구간의 노드들을 갱신하고 필요한 정보를 업데이트하는 과정입니다.
5. 구간 쿼리 처리: 주어진 구간에 대한 질의(Query)를 처리해야 할 경우, 세그먼트 트리에서 해당 구간을 찾아 필요한 연산을 수행합니다. 이를 위해 재귀적인 방식이나 반복문을 사용하여 구간을 탐색하고 연산을 수행합니다.
6. 시간 복잡도 분석과 최적화: 세그먼트 트리의 시간 복잡도를 분석하고 최적화할 수 있는 부분을 찾아 개선합니다. 예를 들어, Lazy Propagation 등의 기법을 활용하여 연산 속도를 개선할 수 있습니다.
7. 테스트 케이스 작성: 구현한 코드가 정확하게 동작하는지 확인하기 위해 다양한 테스트 케이스를 작성하여 검증합니다. 주어진 예제 뿐만 아니라 경계값, 잘못된 입력 등 다양한 상황에 대해 테스트해보는 것이 좋습니다.

 

10868번: 최솟값

  문제  
 

• N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.
• 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

 
  해결 방법  
 

• 이 문제는 세그먼트 트리를 활용하여 주어진 구간의 최소값을 찾는 문제입니다. 세그먼트 트리를 구성하고, 주어진 쿼리에 따라 해당 구간의 최소값을 찾아 출력하면 됩니다.

import sys; input=sys.stdin.readline

INF = int(1e9)

def init(node, start, end):
    if start == end:
        tree[node] = arr[start]
        return tree[node]
    mid = (start + end) // 2
    tree[node] = min(init(node * 2, start, mid), init(node*2+1, mid+1, end))
    return tree[node]

def query(node, start, end, left, right):
     if left > end or right < start: return INF
     if left <= start and right >= end: return tree[node]
     mid = (start+end) // 2 
     return min(query(node*2, start, mid, left, right),query(node*2+1, mid+1, end, left, right))

n, m = map(int,input().split())
arr = [0] + [int(input()) for _ in range(n)]
tree = [0] * ((n*4)+10)

init(1, 1, n)

for _ in range(m):
   a, b = map(int,input().split())
   print(query(1, 1, n, a, b))

• 위 코드에서 init 함수는 세그먼트 트리를 초기화하는 역할을 합니다. 각 노드가 해당 구간의 최소값을 가지게 합니다. query 함수는 주어진 구간에 대한 최소값을 찾아 반환합니다.
• 세그먼트 트리를 이용해 이런 식으로 배열에서 특정 범위에 대한 연산을 빠르게 처리할 수 있습니다. 이런 방식은 배열이 변경되더라도 그 변경사항이 반영된 상태에서 계속해서 연산할 수 있기 때문에 동적인 문제 상황에서 매우 유용합니다.

 

1275번: 커피숍2

  문제  
 

• 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)
• 어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.
• 그 게임은 다음과 같은 규칙을 갖는다.
• N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.
• 당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.
• 당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

 
  해결 방법  
 

• 이 문제는 세그먼트 트리를 활용하여 주어진 구간의 합을 찾고, 특정 위치의 값을 변경하는 문제입니다. 주어진 질의(Query)에 따라 세그먼트 트리 내에서 필요한 연산(구간 합 찾기, 값 업데이트)을 수행하면 됩니다.

import sys; input=sys.stdin.readline

def init(node, start, end):
    if start == end:
        tree[node] = arr[start]
        return tree[node]
    mid = (start + end) // 2
    tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end)
    return tree[node]

def sum_range(node, start, end, left, right):
     if left > end or right < start: return 0
     if left <= start and right >= end: return tree[node]
     mid = (start + end) // 2 
     return sum_range(node*2, start, mid, left, right) + sum_range(node*2+1, mid+1, end, left, right)

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

n, q = map(int,input().split())
arr = list(map(int,input().split()))
tree = [0] * (n*4)

init(1, 0, n-1)

for _ in range(q):
   x, y, a, b = map(int,input().split())
   if x > y: x, y = y, x
   
   print(sum_range(1, 0, n-1, x-1, y-1))
   diff = b - arr[a-1]
   arr[a-1] = b

   update(1, 0, n-1, a-1, diff)

 

• 세그먼트 트리 문제 해결 전략 중 '문제 이해와 제약 사항 파악', '세그먼트 트리 설계', '구간 쿼리 처리' 등의 요소들이 위 두 문제 해결 과정에서 활용되었습니다. 앞으로도 비슷한 유형의 문제가 출제된다면 이러한 접근 방법과 코드를 참고하여 해결해 나가시길 바랍니다.