세그먼트 트리 썸네일형 리스트형 백준 10070 벽 https://www.acmicpc.net/problem/10070 구간에 min, max를 적용하는 쿼리를 처리하면 된다.구간 쿼리니까 세그 박고 싶은데 먼가 잘 안 되고..무지성으로 쓰자니 쿼리 순서에 따라 답이 달라지고..세그비츠가 비슷한 연산을 지원했던 것 같기도 하고..?뇌절하지 말자 lazy propagation을 설계할 때는 한 정점에 여러 쿼리가 쌓이는 상황을 잘 생각해야 한다.같은 구간에 적용된 쿼리 중 min 쿼리는 $h$가 최대인 것만, max 쿼리는 $h$가 최소인 것만 고려하면 된다는 점은 자명하다. 고려할 min 쿼리의 $h$를 $min_h$, max 쿼리의 $h$를 $max_h$로 두자.구간에 적용된 $min_h$ $\le$ $max_h$인 경우는 문제가 되지 않고, 크기가 뒤.. 더보기 세그먼트 트리 소개 세그먼트 트리는 구간에 대한 연산을 $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 다음
