2022년 11월 2일 일기

10월 30일에 2022 SKKU 프로그래밍 대회 in 소프트의 밤 Open Contest에 참가하였다.

신나게 털려서 부족한 부분을 채우고 있는데 너무 정신 없어서 블로그에 접속할 수가 없었다.

앞으로 며칠간 다음과 같은 주제를 포스팅하려고 한다.

시간 여유가 그리 많지는 않아서 간단히 쓰거나 생략할 수도 있다.

 

1. 2022 SKKU 프로그래밍 대회 in 소프트의 밤 Open Contest

아직 모든 문제를 업솔빙하지 못하였다.

업솔빙이 끝나는 대로 올리려고 한다.

 

2. Fenwick Tree

이미 Fenwick Tree에 대하여 쓴 적이 있어서 개념은 생략하고 연습 문제 풀이만 간단히 올리려고 한다.

 

3. Segment Tree

Fenwick Tree처럼 구간을 관리하는 자료 구조이다.

Fenwick Tree보다 느리지만 대부분의 연산을 모두 수행할 수 있다.

bottom-up 구현을 배웠는데 너무 편리하다.

 

4. Segment Tree with Lazy Propagation

Segment Tree는 PURQ만 지원한다.

Segment Tree에 Lazy Propagation을 적용하면 RURQ를 수행할 수 있다.

마찬가지로 bottom-up 구현을 배웠는데 너무 복잡하다.

성능 차이도 미미하다고 하여 그냥 top-down으로만 구현하려고 한다.

 

5. Merge Sort Tree

Segment Tree에서 각 노드가 해당 구간의 모든 원소를 정렬된 상태로 저장하도록 만든 것이다.

구현이 복잡할 것 같았는데 굉장히 간단하다.

 

6. Euler Tour Technique

트리에서 특정 노드의 모든 자손 노드에 대하여 처리하고 싶을 때 사용한다.

DFS로 각 노드에 새로운 번호를 적절히 부여해주면 된다.

 

7. Square Root Decomposition

크기 N의 구간을 sqrt(N)개로 분할하여 관리한다.

 

8. Mo's algorithm

Square Root Decomposition과 유사한 아이디어로 오프라인 쿼리를 효율적으로 처리한다.

 

9. Articulation Point and Bridge

DFS로 O(N + M)에 모든 절단점과 절단선을 구할 수 있다.

 

10. Sprague-Grundy theorem

이론은 집어치우고 신나게 XOR이나 하자.

 

끝