2021년 1월 25일 PS일지

1. BOJ 5 Solve

(1) 13553 수쿼 8
Mo's Algorithm + Fenwick. Add와 Del 함수를 어설프게 합치는 것보다 제대로 분리한게 낫다.
-포인터를 옮기는 순서를 항상 구간 확대를 축소보다 먼저 하자.
1 2 -> 3 5 이렇게 옮기는 상황에서는 2를 먼저 5으로 옮기고 1을 3으로 옮기자. 1을 먼저 옮기는 방식으로 하면 꼬이는 경우도 있는 듯. ex) 1 2 -> 2 2 -> 3 2 -> 3 3 -> 3 4 ->3 5
위 처럼 이상한 경우가 생긴다.

(2) 서로 다른 수와 쿼리 2
1시간 정도 고민했는데 안 나와서 스톤준님 풀이 보고 했다. PST는 연습만이 답인듯. 잘 안 보이고 구현도 어렵다.
Cgiosy 비재귀 퍼시스턴트 트리는 정말 미친 듯 => 소스 cgiosy는 전부터 리차오 / 퍼시스턴트 / 다이내믹 세그 다 비재귀로하던데 구현도 간단해보여서 언젠가 배울거다.

(3) 제비
얘도 2시간 정도 식 유도했는데 도저히 식 안 나와서 에디토리얼 봄.
역시 수학의 강력함을 깨달았다. 3문제 중에 2개 답 보는 건 조금 심하다. 요즘 다시 에디토리얼 중독이 심해지는데 스스로 풀 동기를 만들어보자.

(4) XOR
스스로 풀려고 골드 문제 하나 잡았다.
L,R이 주어질 때(L<=R<=1e9) L부터 R까지 수들을 모두 XOR한 값을 묻는 것.
이런 종류의 문제는 웬지 모르게 빡신데 막상 하면 잘된다.
0부터 X까지 모두 XOR한 것을 생각해보면 X가 짝수/홀수냐에 따라 모든 것이 결정된다.

(5) Daunting Devices
평방분할 연습.
순수하게 5000byte 짰다 -> 디버깅에만 3시간 걸렸다.
메모리 1024kb 제한이길래 사용할 수 있는 메모리를 다 썼는데 오히려 악수가 된 느낌. 대부분 1000 byte가량이길래 뇌절님께 풀이를 여쭈어봤다. jthis: "간단한 루트질" 아... 네. 그 뒤 설명을 듣기 위해 기다리는 중

2. STL Vector의 내부 구현

github.com/baactree/Algorithm/blob/master/Stl/vector.cpp

평소에 정말 궁금했던 거다.
STL을 사용 못하게 되었을 때 가장 불편할 것 중 하나는 vector의 사용이기 때문이다.
vector은 그래프 알고리즘을 구현할 때 거의 필수적이다. 
박트리님의 깃헙을 통해 vector의 내부 구현을 배웠다.

평소에 가변 배열의 원리가 궁금했는데 Size를 2의 거듭제곱 꼴로 잡고 필요할 때마다 늘리는 것이 그 원리였다.
N개의 원소를 삽입할 때 최대 lg N 번 크기의 확장이 일어나고
전체 시간복잡도는 2*(1+2+4+ ... + N 이하 최대 2의 거듭제곱) = O(N)이기 때문에 삽입의 시간복잡도는 항상 amortized O(1)이다. 원소 조회는 배열이니 당연히 O(1). 동적할당만 할 수 있다면 쉽게 구현할 수 있다. 

3. 구사과님의 단호박

xiaowuc1 이분이 버추얼 돌리는 그룹이 있길래 가봤다.
한국인들 많길래 바로 신청했더니 칼 거절.
젠장. 내가 더 실력을 키워야지