[2024 동계 모각코] 7주차 계획
7주차 계획
개요
7주차(2. 12 ~ 2. 18)의 계획입니다.
- 24장 구간 트리
- 서론
- 문제: MORDOR
- 문제: FAMILYTREE
- 문제: MEASURETIME
- 25장 상호 배타적 집합
- 서론
- 문제: EDITORWARS
- 26장 트라이
- 서론
- 문제: SOLONG
- 문제: NH
24장 구간 트리
서론
부분 합은 전처리 과정 이후 어떤 구간$[a,b]$를 구하는 건 $O(1)$시간이지만
값의 업데이트가 $O(n)$이라는 점이 있습니다.
반면에 구간 트리는 값의 업데이트에 매우 강합니다. 무려 $O(\log n)$입니다.
구간 트리는 다양한 문제에서 쓸 수 있는데, 특정 구간에서 최소치를 두 개 찾을 수도 있고, 정렬된 수열의 특정 구간에서 최대 출현 빈도도 계산할 수 있습니다.
문제: MORDOR
배열 $h[0…n-1]$이 주어질 때, 어떤 구간$[a, b]$의 최댓값과 최솟값의 차이를 묻는 문제입니다.
배열의 개수는 최대 $n(1 \leq n \leq 100000)$개, 각 배열에서 구간을 묻는 횟수는 $q(1 \leq q \leq 10000)$번이기 때문에, 일반적인 반복문의 형태로는 풀 수 없습니다.
따라서 세그먼트 트리를 이용해 풀어야 하는 문제입니다.
최댓값을 구하는 세그먼트 트리, 최솟값을 구하는 세그먼트 트리로 분리해서 풀기만 하면 되는 문제입니다.
반복적으로 구현한 코드는, 세그먼트 트리를 재귀적 방식이 아닌 반복적 방식으로 구할 수 있으나, 세그먼트 트리의 노드들을 알맞게 초기화 해야 되서 결국 수행시간이 똑같은 코드입니다.
문제: FAMILYTREE
최소 공통 조상(LCA, Lowest Common Ancestor)문제를 풀어봅시다.
문제: MEASURETIME
역순 쌍(Inversion Count)의 개수를 세는 문제를 풀어봅시다.
Counting Sort방식처럼, 각 숫자의 출현 개수를 이용해서 부분 합을 구하는 문제로 변형할 수 있습니다.
트립, 세그먼트 트리, 병합 정렬 등 여러 가지 방법으로 구현 가능하지만
인덱스의 이진 표현을 이용한 펜윅 트리를 이용해 매우 쉽게 구현할 수 있습니다.
단, 펜윅 트리가 1-based 방식임에 유의합시다.
25장 상호 배타적 집합
서론
Union-find 기법과 이를 응용해서 무엇을 풀 수 있을까요?
그래프 문제에 Union-find기법을 사용할 수 있습니다.
문제: EDITORWARS
이분 그래프 판별(bipartite graph check)문제를 풀어봅시다.
bipartite union-find 방법을 이용하여 풀 수 있습니다.
26장 트라이
서론
트라이를 배우고 이를 이용한 아호 코라식도 배워봅시다.
아호 코라식을 구현하는 문제는 백준 9250 문자열 집합 판별 입니다.
문제: SOLONG
Trie를 이용해 문자열을 자동 완성(Auto complete)하는 문제를 풀어봅시다.
상당히 무식한 방법으로 풀었는데 Trie에서 가장 $frequency$가 높은 string을 노드에 쌩으로 저장해버리는 방식으로 구현했습니다.
여기다가 비트마스킹도 적용해버린 코드도 있습니다.
문제: NH
아호 코라식과 동적 계획법을 결합한 문제를 풀어봅시다.