OI는 KOI, IOI, JOI, POI 등 고딩을 위한 PS이다.

범위따위 알바아닌 ICPC와 다르게 IOI는 시험범위도 정해져있고, 다른 OI들도 보통 그 안에 들어간다. (대표적인 예외로 기하가 있다)

또 서브태스크가 있고, 그레이더와 소통하는 interactive 문제도 나온다.


념글에서 돚거해온 글 좀 변경함


1. 자료구조 초급 + STL


자료구조는 Stack, Queue, Deque, Set, Map, Heap, List 정도

STL은 vector, queue, priority_queue, deque, set, map (+unordered) 정도만 알면 잘 써먹는다.

queue, deque, stack은 vector>라는 PS에서 써먹기에는 구데기같은 구현을 쓰고, 배열로 쉽게 바꿀 수 있어서, TLE가 날때 2순위 척결 대상이다.

set과 map은 1순위 척결 대상이니 priority_queue로 대체할 수 있다면 무조건 대체하자. pq에서 원소 제거를 처리하는 트릭도 있다.

가끔 unordered_map이 크기 순서대로 있다고 생각하는 사람이 있는데, unordered_map은 해시맵이라 그런거 안된다. for (auto i : m)이런거 써놓고 왜 크기순 아니냐고 화내지 말자.

unordered 코포에서 쓰면 핵에 뚝배기가 깨질 가능성이 높다.


2. 알고리즘 초급 + STL


정렬과 이분탐색은 맨날 나옴

버블소트는 증명할때 많이 쓴다.

머지소트는 정렬 외에도 다른 문제를 풀 때 꽤 쓰인다. 다른건 몰라도 머지소트는 구현하는 법을 알아두자.

이분탐색은 무한루프와 int 범위 초과를 조심하자.


가끔 옥톡기 급으로 구데기인 문제가 있어서, 카운팅 소트나 기수 정렬를 사용해야 하는 문제가 있으니 알아두자.


STL에서 쓸만한 함수는 sort, lower_bound, unique, reverse, swap, merge, max, min 정도 있다.

next_permutation 쓰는 문제는 구데기다.


3. 백트래킹


백트래킹으로 어려운 문제는 안나올듯

백트래킹으로 N<=5 답 전부 늘어놓고 규칙찾는 빌런도 있다.


4. DP 초급 + 메모이제이션


DP는 많이 풀어보는게 답인듯;;; DP 싫어


5. 그래프 초급 (인접행렬과 인접리스트, DFS, BFS)


나중가면 인접리스트만 계속 쓰게 되지만, 인접행렬이 좋은 문제들이 있으니 가끔은 인접행렬도 생각해주자.

DFS는 그래프의 기본중 하나다. 그래프 문제가 나오면 1/3은 DFS 해야 한다.

나중가면 BFS 두고 다익스트라 쓰는 사람들이 있는데, BFS를 아껴주자.


6. 그리디 초급


그리-디는 머리가 좋아야 풀수 있다. ㄹㅇ

기초 그리디에서 배우는 문제중에 회의실 배정 문제가 있는데, 그리디로 쉽게 풀리지만 다양한 바리에이션이 갑툭튀해서 어려운 문제로 탈바꿈하기도 한다. 회의실배정==그리디라는 사고방식에 갇혀있지는 말자.


7. 분할 정복


분할정복은 수많은 log 들어가는 알고리즘에 들어간다.

어려운건 머리가 좋아야 풀수 있다. 머리가 안좋으면 많이 나오는 유형을 외우는 수밖에...


8. 수론 초급(mod, pow, 역원, phi 함수, 소인수분해, 약배수, 유클리드 호제법 등)


사실 OI에 많이 나오는것 같지는 않고 코포 앳코더같은데 많이 나오니 알아서 거르던 공부하던 하자.


뜬금없지만 뭔가 수학 관련되어 복잡도를 줄여주는 성질들은 이런 것들이 있다.

a%b는 a/2 이하다.

n이하의 정수를 2 이상 정수 곱으로 표현한다면 logn개 이하밖에 안된다.

10^9 이하 정수의 소인수는 9개 이하다.

조화급수는 O(logn)으로 증가한다.


9. 최단거리 (다익스트라, 벨만-포드, 플로이드)


다익스트라는 최단거리 문제의 메인으로 최단거리면 거의 다익스트라다.


다익스트라 주의할 점


잘못 구현해서 TLE가 나야 하는데 맞는 경우가 있다.

음수 간선이 있으면 O(ElogV)가 보장이 안된다.

std::priority_queue는 max heap이다.


플로이드는 가끔 나온다. 반복문 순서가 경유점이 가장 먼저인 것에 유의.


벨만 포드를 쓰는 문제 == 벨만 포드 연습문제 + MCMF 이다. OI에 이게 나온적이 있나?

이거 쓰느니 SPFA 씀


SPFA는 데이터 뚫기 용도로 사용된다. 근데 최악의 데이터가 너무 유명해서 뚫기 힘들다.


10. DP 중급 (확률, 다차원 DP, 행렬 거듭제곱)


N이 50~500쯤 되면 보통 다차원 DP가 등장하니 N 범위를 보고 잘 추측해보자.

다차원 DP에 오면 메모리 제한이 걸리는 경우가 생긴다. (long long 500^3개면 1GB다) DP 배열을 토글링하는 방법도 익혀두자.


11. Union find (Disjoint set)


윾파는 정말 다양하게 쓰이고 변형되기 때문에, 돌아가는 방식을 완벽히 이해하자.

유니온 파인드의 시간복잡도를 줄여주는 방법에는 Union by rank/size와 Path compression이 있는데, 나중가면 Union by rank는 느리고 길어서 잘 안 쓰고, Path compression만 쓰게 된다. 그치만 Path compression은 amortized 복잡도를 가지다보니 쓸 수 없는 경우가 생기니까 Union by rank/size도 확실히 알아두자.


12. minimum spanning tree (프림, 크루스칼)


MST의 그리디 접근은 굉장히 특이한 성질이기 때문에, 온갖 신기한 문제들이 나온다. MST의 그리디 접근이 가능한 이유에 대해서 확실히 알아두자.

MST를 구현할 때 프림을 쓸 일은 없을 것 같다. 하지만 프림의 이론적인 부분은 증명에 쓰일 수 있으니 알아두는 것이 좋다.


13. bitmasking


비트마스킹이 나오면 보통 N이 ~20쯤 나오고, 복잡도가 2^(N/3)같은게 나오는 저세상 문제는 N이 50이 나올 수도 있다. N이 작으면 의심해보자.


14. 구간 쿼리 초급 (세그먼트 트리, 펜윅 트리)


OI에서 세그먼트 트리는 지겹게 나온다. 나중에는 세그트리에 별 이상한 걸 다 넣기 때문에, 구조를 잘 이해할 필요가 있다.

펜윅 트리는 세그먼트 트리보다 많이 빠르고 짧다. 대신 연산에 역원이 존재해야 한다. 역원이 없으면 1~x 쿼리밖에 못한다.

세그트리 펜윅트리 모두 초기화 O(n), 업데이트, 쿼리 O(logn)에 된다. 근데 귀찮아서 초기화를 보통 O(nlogn)에 한다.


15. 파라메트릭 서치


파라메트릭 서치는 최대, 최소 문제를 결정문제로 바꾸고 logx를 붙이는 강력한 방법이다. 파라메트릭이 가능해 보이면 일단 파라메트릭을 붙이고 생각하는 것도 나쁘지는 않다.

파라메트릭 서치를 실수에서 돌릴 때는, while (s + eps


16. 트리 초급 (euler tour, lca, 지름)


OI 레벨에서 트리 있고 쿼리 있으면 euler tour를 많이 쓴다.

lca는 euler tour와 RMQ를 쓰는 방법, sparse table을 쓰는 방법이 있는데, RMQ쪽이 성능상 좋지만 sparse table이 더 편한듯

트리의 지름은 보통 가장 먼 점에서 가장 먼 점 방법을 쓰는데, 음수 가중치 있으면 망하니 DP 방법도 알아두자.


17. 문자열 초급 (KMP, trie, 라빈-카프 해싱)


문자열은 라빈-카프 해싱의 막강한 위력때문에 OI에 내기가 힘들다.

KMP는 구데기. +꼭 문자열이 아닌 수열에도 적용되는 경우가 있으니 주의.

OI 수준에서 trie를 다루는 방법이 딱히 없다보니 OI에 나온다면 보통 문자열을 가장한 트리 문제가 된다.


18. 기하 초급 (플레인 스위핑, CCW, 컨벡스 헐)


플레인 스위핑은 오프라인 문제를 한 차원 낮추고 온라인으로 만든다는 의미를 가진다. 2D 이상이 나오면 자주 쓰인다.

CCW는 선분 교차나 컨벡스 헐 등에 사용된다. 헷갈리지 말자.

컨벡스 헐과 로테이팅 캘리퍼스는 외워서 쓰는게 편하다. 보통 CCW가 nlogn번 사용되는 graham scan을 쓰는데, CCW를 2n번 쓰는 andrew's monotone이 더 좋은 것 같다. 무려 andrew's monotone은 x좌표가 s~e인 점들의 컨벡스 헐 쿼리같은거도 쿼리당 O(n)에 할수있다?


19. 구간 쿼리 중급 (좌표 압축, lazy propagation, 2d structure, sparse table)


좌표 압축 없으면 dynamic segment tree 써야된다. 좌표압축은 쓸데가 많음

lazy propagation은 구간 업데이트에 쓰이는데, 은근히 못 쓰는 경우가 많고 잘 쓸 일이 없다.

참고로 펜윅 트리를 두개 쓰면 합 연산 등은 구간 업데이트 구간 쿼리가 가능하다. 세그트리 lazy propagation보다 훨씬 빠르다

2d structure는 2d 펜윅, 2d 세그트리 등이 있는데, 본질은 세그트리의 각 노드에 1d 세그트리를 넣은 거라는걸 명심하자. 세그트리의 각 노드에 펜윅을 넣을 수도 있고 펜윅의 각 노드에 세그트리를 넣을 수도 있고 세그트리의 각 노드에 map을 넣을 수도 있는거다.

sparse table은 lca 구할 때도 쓰고 구간 쿼리 할때도 쓸 수 있는데 구간 쿼리에는 잘 안쓴다. 구간 쿼리에 쓰기에는 메모리가 O(nlogn)이고 초기화가 O(nlogn)이고 업데이트가 불가능한 등 무수한 단점들이 있다.

근데 구간 최대, 최소같은 쿼리처럼 한 원소가 두번 세져도 관계없는 쿼리에서는 쿼리당 O(1)이라는 엄청난 장점이 있다. 그래도 안씀


20. sqrt decomposition과 mo's algortihm


sqrt decomposition? 구데기

mo's algorithm은 백준 수열과 쿼리 시리즈에 연습문제가 많이 있다. 트리에서도 쓸수 있다 카더라.

복잡도가 O(nsqrtnlogn)인 경우 1초 안에 들어오려면 N을 10000쯤 줘야 하는데 그러면 n^2이 뚫린다. 그래서 출제자들이 피눈물을 흘리며 N 100000에 5초 8초 이런식으로 시간을 길게 주는 경우가 많으니 시간 제한이 길면 의심해보자.


21. 이분매칭


플로우증에서 OI에 나올만한건 이분매칭정도. Hopcroft-Karp를 알면 유리한 고지를 점할수 있으나 굳이?


22. 그래프 중급 (SCC, BCC, 2-sat)


SCC나 2-sat을 쓰는 문제는 뻔하거나 개어렵거나인것 같다. 자주 나오는 유형은 아니다.

단절선이나 단절점도 뻔하거나 개어렵다. 마찬가지로 자주 나오지도 않는다. 최근 APIO에 나와서 구데기성을 인증한적 있다.


23. DP 고급 (CHT, DnC opt, Knuth opt)


CHT는 DP 식을 잘 세우고 나면 바로 보인다. 문제는 DP 식 세우기가 어려운 경우다.

CHT에는 다양한 바리에이션이 있어서, set을 쓴다거나, 세그트리에 CHT를 넣는다거나, 리차오 트리라던가 별 이상한게 다 있다 카더라. 이런거나 보고있는 뉴비들은 스택 CHT나 쓰자.

DnC opt나 Knuth opt는 보통 사각부등식으로 증명하는데 꼭 그렇지만도 않다. 증명이 어렵기 때문에 그냥 Knuth feel이 오면 Knuth를 짜고 WA를 받으면 된다.


24. 트리 중급 (Centroid decomposition, 트리 압축, 이진 트리 변환)


Centroid decomposition은 사기 스킬이다. Centroid tree까지 쓸줄 알면 이론은 끝일듯

트리 압축은 안 중요한 정점들을 버리는 스킬이다. 뜬금없지만 dynamic segment tree에서 트리 압축을 하면 메모리가 O(n)이 된다.

이진 트리 변환은 더미노드를 N개쯤 더 넣어서 기존 트리의 거리 관계를 유지하되 이진 트리가 되도록 만드는 방법이다. 구데기다.


25. 자료구조 중급 (Persistent segment tree, HLD)


Persistence라는 성질은 '과거의 상태에 접근가능'하다는 의미이다. 2D query에 PST를 쓰는건 y좌표를 시간처럼 생각하는 거라고 볼 수 있다.

HLD는 OI에서 잘 나오지는 않는데, 서브태스크 긁기에는 쓸수 있을지도?


26. 문자열 중급 (Suffix array, manacher, z)


Suffix Array는 문자열 비교의 사기 스킬중 하나다. KMP가 헷갈릴때 쓸수도 있다.

manacher algorithm은 팰린드롬을 구하는 알고리즘이지만, 비슷한 상황에 사용되기도 한다. NYPC 예선 종이접기를 n^2logn에 풀수 있다 카더라. 난 몰라


27. offline dynamic graph


JOIOC 2018 collapse에서 30점 섭태로 dynamic connectivity를 던졌길래 그냥 넣었다.

여담1. 일본 대회에서 한 대회인데 스코어보드가 외국인들에게 점령당해있다.

여담2. 이 대회는 HLD도 냈다.


28. 구간 쿼리 고급 (BBST, dynamic segment tree)


set과 map으로 할수 없는 일을 하기 위해서 BBST를 구현하고 싶을 때가 있을 수 있다. splay tree나 treap 등을 사용할 수 있다. red black tree같은 걸 구현하는 사람은 없겠지?

PS에서 BBST를 사용할 때는 보통 정렬 기준이 정수이다. 그럴 때 dynamic segment tree를 써서 구현을 좀더 단순하게 할 수 있다.


------------------------------------------

이 이하는 진짜로 OI에서 아무 짝에 쓸모가 없다


29. 문자열 고급 (아호코라식)


아호코라식 != OI


30. 수학 중급 (FFT, 게임(Nim game, Grundy number), 뫼비우스 함수, 카탈란 수)


FFT 팀노트 없이 구현 가능? 전 못함


31. 플로우 초급 (Ford-Fulkerson, Edmond-Karp, MCMF)

32. 플로우 중급 (Dinic, Hopcroft-Karp, LR-maxflow)


플로우를 배우는 것의 큰 단점은, N=1000000인데 플로우 풀이가 생각난다는것.

디닉이 아무리 빨라도 O(V^2E)인데 될리가 없다.

디닉에 LCT를 섞으면 O(VElogV)라고 한다. 저세상 알고리즘인듯


33. 자료구조 고급 (Link/Cut Tree 등)


고등학생 대회에 이딴걸 왜냄


34. 기하 고급


ㅗ


고칠거 있으면 제보바람

질문하면 아는건 답해줌