세그먼트 트리를 언제 공부해야 할까요? (학습 주제 탐색 전략에 대해)

이 글에서는 세그먼트 트리를 배울 때 어려운 점들과 세그먼트 트리를 공부하는 과정에 대한 두 가지 예시를 다룹니다.

구직 광고

저는 지금 보충역 산업기능요원 구직 중입니다.

구직에 대한 글을 참조해 주세요.

세그먼트 트리 강의 자료

아무래도 세그먼트 트리를 제목에 넣어놨는데 주제는 학습 전략에 좀 더 가깝다 보니, 세그먼트 트리에 대해 뭔가 읽으러 오신 분들에게 조금 미안하다는 생각이 들어서 이전에 강의 준비하며 만든 세그먼트 트리 자료를 올려 봤으니 읽어 보셔도 좋고 그러지 않아도 좋습니다.

세그먼트 트리

세그먼트 트리(Segment Tree)는 데이터를 이진 트리 구조로 저장해 구간 쿼리를 빠르게 처리하는 자료구조입니다. 원소의 값이 자주 바뀌는 경우에 효과적입니다.

세그먼트 트리는 강력한 도구입니다. 여러 대회에서 세그먼트 트리를 사용해 해결해야 하는 문제가 자주 출제됩니다. 세그먼트 트리보다 쉬운 알고리즘을 사용해 풀 수 있는 문제 중에도 세그먼트 트리를 적용하면 더 빠르고 간단하게 풀 수 있는 문제가 많습니다.

세그먼트 트리는 "어렵지만 활용할 수 있는 문제가 많고 템플릿을 적용하기 쉬워서 solved.ac 티어를 빨리 올릴 수 있는" 주제로 유명합니다. 이런 특성을 가진 다른 주제는 분리 집합, 빠른 푸리에 변환 등이 있지만 세그먼트 트리가 제일 유명합니다. 경험치 파밍용으로 너무 인기가 많아서 solved.ac에서 세그먼트 트리를 다루는 문제들의 난이도를 전체적으로 하향 조정한 일도 있습니다.

이미지 출처: https://twitter.com/shiftpsh/status/1319554349366874113

코딩 테스트에도 세그먼트 트리가 나오나요?

세그먼트 트리는 일반적으로 코딩 테스트에서 다루는 것들보다 훨씬 어려운 주제입니다. 그래서 일반적으로 코딩 테스트에는 세그먼트 트리로 푸는 문제가 등장하지 않는 편입니다. 등장하더라도 합격 여부와 관련이 없는 마지막 문제이거나 세그먼트 트리가 아닌 다른 방법으로도 풀 수 있는 형태로 나옵니다.

"고난도 문제를 풀기 위해 세그먼트 트리를 공부하는 건 어떤가"에 대해서 저는 회의적인 편입니다. 고난도 문제가 나오더라도 세그먼트 트리에 대해서만 나오는 것이 아니기 때문입니다. 그런 문제들을 전체적으로 공략하려면 비슷한 난이도인 다른 주제들도 공부해야 합니다. 그것들을 다 공부하려면 1년은 잡아야 합니다.

어려운 주제를 찾기보다 자주 나오는 유형인 그래프, 시뮬레이션, 문자열 같은 분야의 숙련도를 올려 안정적으로 풀 수 있게 하는 게 코딩 테스트 준비에 훨씬 큰 도움이 됩니다.

세그먼트 트리는 왜 어려울까?

세그먼트 트리는 자주 사용되는 자료 구조이면서 공부하기 어려운 점들이 많습니다. 그래서 본격적으로 알고리즘 대회에 입문하려 하는 분들의 첫 번째 벽이 될 때가 많습니다. 왜 이렇게 어려운지 살펴보겠습니다.

선수지식이 복잡해서

세그먼트 트리를 공부하기 전에 이런 내용들을 알아야 합니다.

• 분할 정복
• DP, 특히 누적 합(Prefix sum)에 대해

분할 정복과 DP에 익숙하지 않다고 생각한다면 세그먼트 트리를 공부하는 것보다 분할 정복이나 DP 문제 풀이 연습을 더 하는 것을 추천합니다.

• 완전 이진 트리를 배열에 배치하는 테크닉: 주로 힙(Heap)을 공부하면서 익히게 됩니다.
• 클래스와 구조체: 클래스나 구조체로 세그먼트 트리를 구현해 외부 인터페이스용 멤버 함수를 작성해 사용하는 경우가 많기 때문입니다.
• 기초 대수학: 집합과 연산의 정의, 항등원에 대해.

이것들을 알고 있으면 세그먼트 트리를 편하게 공부할 수 있습니다. 물론 잘 모르고 시작해도 세그먼트 트리를 공부하면서 같이 공부하면 그만인 주제들입니다.

세그먼트 트리보다 어려운 주제 중에는 선수지식이 더 복잡한 것들도 많습니다. 하지만 이 정도면 난이도가 비슷한 주제 중에는 많은 편입니다.

구현이 복잡해서

세그먼트 트리를 만들려고 하면 적어도 세 가지 기능을 구현해야 합니다.

• 초기화
• 업데이트
• 구간 쿼리

일반적으로 세 가지 기능은 형태가 조금씩 다른 재귀 함수로 구현하게 됩니다. 세그먼트 트리의 구조를 어느 정도 파악하고 있더라도 세 가지 기능을 매번 다시 구현하는 건 쉽지 않습니다. 외워서 쓰기에는 양이 너무 많고 복잡합니다. 매일같이 세그먼트 트리를 구현하는 숙련된 분들이라면 이것들을 순식간에 머릿속에서 가져올 수 있지만 다들 처음부터 그렇지는 않습니다.

그래서 미리 작성된 템플릿을 복사해 사용하는 경우가 많습니다. 세그먼트 트리를 통해 '미리 작성된 템플릿'을 처음으로 접하는 경우가 많이 있습니다.

---

여기서부터는 세그먼트 트리를 공부하게 된 두 사람의 조금 다른 이야기를 다뤄 보겠습니다.

예시 1: 묘지기 이야기

Codeforces Round #780의 스포일러를 포함하니 주의하시길 바랍니다.

코드포스는 알고리즘 경쟁 사이트입니다. 거의 매주 알고리즘 문제를 푸는 경쟁 라운드가 열립니다. 묘지기의 코드포스 레이팅은 1500점대이고, 블루(1600+)를 목표로 하고 있습니다.

묘지기는 어제 하루 종일 세그먼트 트리를 공부했습니다. 예제도 많이 풀어봤기 때문에 오늘 코드포스 라운드에 세그먼트 트리 문제가 나오면 박살 내 버리겠다고 생각하고 있습니다. 게임을 하자는 친구들의 권유를 "Game? Sorry, I have a Rated Codeforces Round."라고 말하며 거절하고 코드포스를 하기로 했습니다.

묘지기는 Codeforces Round #780(Div.3)에 참가합니다. A, B, C, F1을 해결합니다. 남은 문제인 D, E나 F2를 모두 읽어보았지만 실마리를 찾을 수 없습니다. 그렇게 1500대 퍼포먼스로 대회를 마무리합니다.

F2가 세그먼트 트리였다고요?

여기서 묘지기가 읽어 봤지만 풀지 못한 F2에 대해 조금 더 생각해 봅시다. 묘지기는 F1을 부분 합 자료구조를 사용해 해결하지만 입력 크기가 큰 F2를 풀 방법은 찾지 못했습니다.

F2는 세그먼트 트리 세 개를 사용해 3으로 나눈 나머지를 각각 관리하고 '-'에서 '+'를 뺀 수가 특정 수치 이상이고 3으로 나눈 나머지가 같은 값을 모두 조회하는 방법으로 풀 수 있습니다.

물론 이 문제는 쉽지 않고 세그먼트 트리를 사용할 수 있는 문제라는 것도 알아채기 어렵습니다. 이 문제에는 대회가 끝난 뒤 '*2100'이 매겨졌고, 이는 위에서 묘지기가 목표로 하던 블루보다 훨씬 높은 난이도입니다. 실제로 묘지기 입장에서 이 문제보다 D나 E를 고민하는 것이 고득점을 노릴 때 유리합니다.

세그먼트 트리를 사용해 F2를 푸는 코드

 

그런데 사실은 세그먼트 트리를 사용하지 않는 해도 있습니다.

1차원 배열에 '-'에서 '+'를 뺀 개수에 따라 마킹한 뒤 '현재 보고 있는 지점보다 뒤에 있으면서 3으로 나눈 나머지가 x인 곳의 합'을 x=0, 1, 2에 대해 배열 세 칸에 저장합니다. 그리고 1차원 배열의 특정 칸을 지날 때마다 세 칸 중 3으로 나눈 나머지가 같은 칸에 더하거나 뺍니다. 그렇게 매번 세 칸 중 현재 보고 있는 곳과 나머지가 같은 칸을 확인하면 됩니다.

이쪽 풀이를 떠올리는 난이도는 세그먼트 트리 풀이와 비슷했다고 생각합니다. 이 문제를 풀기 위해 반드시 세그먼트 트리를 알아야 하는 것은 아니지만, 세그먼트 트리에 대해 잘 알고 있다면 두 가지 방법 중 적어도 하나를 떠올리기 쉬워집니다.

세그먼트 트리 없이 F2를 푸는 코드

알고 있는 것과 문제를 해결할 수 있는 것

어제 묘지기는 solved.ac에서 세그먼트 트리에 대한 문제를 검색해 풀었습니다. 이때 묘지기는 그 문제들이 세그먼트 트리 문제라는 것을 알고 접근했기 때문에 문제의 해법에 더 쉽게 접근할 수 있었습니다. 새로운 알고리즘에 대해 공부할 때 관련된 문제를 검색해서 푸는 것은 분명 효과적인 연습입니다. 하지만 실제로 대회에서 해당 카테고리의 문제가 나왔을 때 연습했던 것만큼 쉽게 풀 수 있게 되지는 않습니다.

여기서 묘지기는 F2를 읽어 보았지만 세그먼트 트리 문제라는 것을 파악하지 못했습니다. 실제로 대회에서 어떤 알고리즘을 활용하려면 문제에 대한 사전 지식이 적은 상태에서 문제를 접하는 경험이 필요합니다. 묘지기는 앞으로 참가하는 대회에서 여러 문제들을 풀어 보면서 세그먼트 트리를 적용할 수 있는 문제들도 접하게 될 겁니다. 그런 문제들의 해법을 고민하면서 세그먼트 트리를 문제에 적용하는 방법을 익히게 됩니다.

출제 경향

다른 대회들도 어느 정도 그렇지만, 코드포스는 특히 '어떤 자료구조를 알기만 하면 풀 수 있고, 아니면 풀 수 없는' 유형인 문제를 피하는 경향이 있습니다. 묘지기가 세그먼트 트리를 연습하며 풀었던 BOJ 2357이나 BOJ 11505 같은 문제를 라운드 중에 보게 될 일은 거의 없다는 뜻입니다.

실제로 코드포스에 세그먼트 트리 문제가 출제될 때는 주로 레이팅이 2000점 이상인 유저가 도전할 만한 난이도로 설계됩니다. 지금 점수가 1500대인 묘지기가 출제되는 문제를 난이도 순서대로 푼다면 세그먼트 트리가 필요한 문제를 볼 일이 별로 없다는 뜻입니다.

또 다른 예시로 제가 코드포스에서 처음으로 Candidate Master(1900+)를 달성한 것은 2020년 3월입니다. 그 때까지 저는 코드포스 라운드 중에 세그먼트 트리에 대한 문제를 단 한 문제도 푼 적이 없었습니다. 실제로 세그먼트 트리를 공부한 것이 코드포스에서 효과를 보려면 묘지기의 레이팅이 지금보다 훨씬 높아야 합니다.

예시 2: 무덤털이 이야기

무덤털이는 코드포스 라운드에 도전하는 것을 좋아합니다. 무덤털이의 코드포스 레이팅은 1800이고, 퍼플(1900+)을 노리고 있습니다. 세그먼트 트리라는 자료구조가 무엇인지에 대해 들은 적은 많지만, 아직 실전에서 접한 일이 없기 때문에 따로 공부한 적은 없습니다.

무덤털이는 Codeforces Round #780(Div.3)에 참가합니다. 무덤털이는 A부터 E까지 다섯 문제를 능숙한 솜씨로 처리합니다. 다섯 문제를 모두 푸는 데 1시간 20분이 걸렸습니다. 마지막 F번을 남겨둔 무덤털이는 비둘기집의 원리와 부분 합을 적용해 F1을 해결합니다. 하지만 같은 해법을 F2에 적용하기에는 입력 크기가 너무 큽니다. 마지막까지 F2의 해법에 대해 고민하지만, 해법을 찾지 못하고 아쉽게 6문제로 대회를 마감합니다.

무덤털이는 대회가 끝난 뒤 Twitch TV의 Gravekper 채널에서 진행되는 코드포스 풀이 방송을 시청합니다. 방송에서 세그먼트 트리를 사용해 F2를 푸는 방법에 대해 듣고 세그먼트 트리를 공부해 보기로 합니다.

이쪽 이야기의 주인공인 무덤털이는 새로운 알고리즘을 접하는 것이 느린 편입니다. 앞에서 묘지기가 세그먼트 트리를 공부했을 때 레이팅이 1500점대였는데, 무덤털이는 1800점대이지만 아직 세그먼트 트리를 구현해 본 적이 없습니다.

하지만 무덤털이는 1800점 근처 문제들을 풀면서 자신이 고민한 적이 있는 문제들을 다른 사람들이 세그먼트 트리로 푼 것을 여러 번 보았습니다. 그래서 어떤 문제들이 세그먼트 트리를 적용할 수 있는지 조금 알고 있습니다. 지금 상태에서 세그먼트 트리를 공부한다면 이전에 자신이 고민했던 몇 가지 문제에 세그먼트 트리를 직접 적용해 볼 수 있고 이것은 꽤 큰 연습이 됩니다.

탐색과 숙련

어떤 사람들은 '묘지기'처럼 새로운 알고리즘을 공부하고 관련된 문제를 푸는 걸 좋아합니다. 특히 최근에 개선된 solved.ac의 태그 기능을 사용하면 새로 공부한 알고리즘에 관련된 문제를 쉽게 찾을 수 있기 때문에 새로운 알고리즘을 공부하는 게 전보다 훨씬 쉽게 되었습니다. 이렇게 여러 가지 알고리즘을 공부하며 문제들을 해결하면 solved.ac 레이팅도 빨리 오르기 때문에 동기부여가 됩니다.

반대로 '무덤털이'처럼 새로운 알고리즘을 공부하는 것을 좋아하지 않는 사람들도 있습니다. 새로운 것을 배우는 것보다 반복 연습을 통해 코드포스나 알고리즘 경쟁 사이트에서 레이팅을 올리거나 경시대회 기출문제들을 푸는 연습을 많이 하는 편입니다. 새로운 알고리즘은 내가 문제를 풀면서 정말로 필요하게 되었을 때 공부합니다.

묘지기와 무덤털이의 예시에서 레이팅의 변화를 시간의 흐름처럼 생각해 봅시다. '묘지기'가 세그먼트 트리를 먼저 공부하기 시작했기 때문에 세그먼트 트리에 숙련되는 건 묘지기가 빠를 겁니다. 하지만 나중에 공부를 시작한 '무덤털이'는 이미 대회에서 세그먼트 트리 문제에 대해 여러 번 고민해 보았습니다. 따라서 숙련되는 데에 필요한 연습량이 더 적으리라고 볼 수 있습니다.

어느 쪽이 더 좋을까요? 어느 쪽이든 충분히 시간을 들여 연습하면 되기 때문에 한쪽이 많이 유리하지는 않습니다. 여러분의 취향과 흥미에 따라 너무 빠르거나 늦지 않도록 조심하면 됩니다. 너무 빠른 경우는 특정 알고리즘을 공부하는 데 필요한 선수지식이 갖춰지지 않은 상태에서 공부하는 경우이고, 너무 느린 경우는 특정 유형에 대한 지식이 부족해서 경쟁 환경에서 여러 번 비슷한 유형 문제에 막히는 경우입니다.

시간 문제

여기서 한 번 더 강조하고 싶은 것은 어떻게 연습해도 숙련되는 데에 시간이 걸린다는 겁니다. 오늘 공부한 알고리즘을 내일 대회에 적용하기를 기대하기는 어렵습니다. 관련된 문제들을 접해 보고 어떤 문제에 이런 해법이 적용되는지 공부해야 합니다. 따라서 목표로 하는 어떤 큰 대회가 열리기 전까지 특정 알고리즘을 연습하고 싶다면 적어도 몇 달 전에 공부를 시작하고 연습하는 것이 좋습니다.

업솔빙(Upsolving)

'대회나 연습이 끝난 뒤 풀지 못했던 문제를 다시 풀어보는 일'을 업솔빙(Upsolving)이라 합니다. 알고리즘 커뮤니티에서 자주 사용하는 단어입니다.

업솔빙은 미숙한 지식을 실제 문제 풀이에 적용하는 방법을 빠르게 익힐 수 있는 방법입니다. 대회 시간 중에 고민했던 문제들을 다시 보면 앞으로 내가 어떤 분야를 연습하면 이런 문제를 풀 수 있게 될지 파악할 수 있습니다. 이미 알고 있는 지식을 적용하지 못한 경우라면 해당 지식을 적용하는 연습을 할 수 있습니다. 숙련도를 올리고 싶은 주제로 나온 문제를 대회 시간 중에 해결하지 못했다면 바로 다시 풀어 봅시다.

풀이 영상

위에서 언급한 세트인 Codeforces Round #780을 푸는 영상이 제 유튜브 채널에 올라와 있으니 관심 있는 분은 참고하시길 바랍니다.

https://www.youtube.com/watch?v=sjuNBwSYy5w