세그먼트 트리 썸네일형 리스트형 세그먼트 트리 소개 세그먼트 트리는 구간에 대한 연산을 $O(logN)$만에 처리할 수 있는 자료구조입니다. 난이도 높은 문제에서 다양한 방식으로 활용되는 자료구조이기도 합니다. 구조 이진 트리의 형태이며, 각 노드는 특정 구간의 값을 저장하고 있습니다. 이 값은 구간의 합, 최솟값 등 다양한 값이 될 수 있습니다. 루트 노드는 전체 구간에 대한 값을 저장하며, 루트 노드에서 멀어질수록 담당하는 구간이 작아지다 리프 노드에 도달하면 원소 하나만을 담당하게 됩니다. 연산 기본적으로 원소 하나를 변경하는 연산과 특정 구간의 값을 구하는 연산을 처리할 수 있습니다. 구간 합을 구하는 세그먼트 트리의 코드를 예시로 설명하겠습니다. 원소 변경 1 2 3 4 5 6 7 8 9 10 void change(int now, int l.. 더보기 백준 20052번 괄호 문자열? https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 풀이 유니온 파인드를 이용한 풀이와 세그먼트 트리를 이용한 풀이가 있습니다. 유니온 파인드 풀이는 제가 구상했고, 세그먼트 트리 풀이는 다른 분의 도움을 받았습니다. 풀이 1(유니온 파인드 이용) 이 풀이의 핵심은 유니온 파인드를 이용해 이어져 있는 괄호쌍을 하나로 묶어 관리하는 것입니다. 입력받은 괄호 문자열을 탐색하며 이어져 있는 괄호쌍을 묶는 작업을 마치면 아래 그림처럼 괄호 문.. 더보기 이전 1 다음
