PS 토픽 모음

2019. 4. 21. 02:43알고리즘 문제풀기/기타 주제

PS 판이 참 좁습니다. 좁은 판이 점점 넓어지고 있는 요즘, 어떤 것을 배워야 하는지 몰라 헤매는 사람도 많습니다.

이런 일들이 있습니다. 어떤 문제를 한참 고민하다 포기하고 질문을 했는데, 알고 보니 내가 전혀 모르는 개념이 필요한 문제네요. 아, 역시 못 푸는 문제였구나. 새 개념을 공부합니다. 나중에 이걸 쓰는 문제를 만나면 그 때는 풀어야지.

너무 좋죠. 누구나 그렇게 발전합니다.
그런데 아무리 배워도 매번 이런 일뿐이라면 어떨까요?
매번 문제를 풀 때마다 몰랐던 새로운 개념이 나오는데, 물어보면 다들 하는 말이
"이건 중요하니까 알고 계셔야(알고 계셨어야) 해요"라면?

 

좋은 커뮤니티 속에서 실력이 비슷한 이들과 꾸준히 교류할 수 있는 사람은
그렇지 않은 사람에 비해 새로운 내용을 훨씬 빨리, 쉽게, 많이 접합니다. 무럭무럭 자라날 수 있지요.

저는 그런 접점이 없는 사람들도 PS를 하면서 즐거웠으면 좋겠고,
나아가 훌륭한 실력을 가지게 되었으면 합니다.

 

이 글에는 제가 PS를 하면서 중요하다고 생각하는 내용, 그리고 그냥 나만 알고 있기 아까운 내용을 모았습니다.
앞으로도 꾸준히 내용을 추가하고, 굵은 글씨는 이 블로그의 다른 글로 이어지게 하려고 합니다.

 

 

도입

왜 PS를 하는가?가 있습니다. PS가 현업에서 어떤 도움을 주는지에 관한 실용적 이야기, 그리고 하는 입장에서 어떤 점이 재미있는지에 관한 이야기.

PS 계열 커뮤니티와 웹 사이트(링크)가 정말 많이 있습니다. 정기적으로 대회를 열어주는 고마운 사이트들도 있고, 커뮤니티에서 전세계 사람들과 얘기하고 정보를 나눌 수도 있습니다. 또한 알고리즘 공부에 도움이 되는 도구 역할의 사이트도 있습니다.

PS 용어 정리(링크)도 있으면 좋을 것 같았습니다.

 

기초

PS에서 가장 많이, 또 당연하다는 듯이 쓰이는 게 C 및 C++입니다. 반복문과 배열 선언, 함수 선언과 구조체 선언을 기초로 하며, C++의 STL을 사용한다면 구조체 정렬과 각종 컨테이너의 사용법, 템플릿의 개념 또한 알아야 하겠습니다. C++ 표준 라이브러리에도 알려지지 않은 다양한 기능이 있습니다.

반복문을 쓸 수 있게 되었다면 시간복잡도에 대해서도 알아야 하겠죠. 여기까지는 기초 중의 기초입니다.

 

초급

이 블로그 조회수의 대부분을 차지하는 std::sort를 이용한 정렬(링크)이 있습니다.

DFS와 스택, BFS와 큐의 개념이 있습니다. 보통 이들을 한꺼번에 무작정 배우는데 저는 좋지 않다고 생각해요. 스택과 큐의 개념 자체는 직관적이지만, 둘이 어떻게 DFS와 BFS에 적용되는지 그리고 DFS와 BFS는 대체 왜 하는지(이 질문은 DFS와 BFS가 애초에 무엇인가 하는, 본질에 대한 질문에 닿습니다)는 바로 와닿지 않거든요. 그래프와 탐색이라는 개념을 먼저 이해한 후, DFS 그리고 BFS를 따로 이해하는 것이 낫다고 생각해요. 그리고 위상 정렬(링크).

어쩌면 가장 먼저, 그리고 가장 많이 접하는 그래프인 트리가 있습니다. 트리도 그 자체만 보는 것보다, 그래프 탐색을 이해한 후에 트리를 보고, 트리를 어떻게 분석해 저장할 것인지를 이해함이 좋을 것 같습니다.

DP의 개념은 일찍 할 수록 좋구요.

최단경로 문제와 다익스트라 알고리즘을 먼저 함께 배우는 게 낫다고 생각해요. 이후에 플로이드-워셜 알고리즘, 벨만-포드 알고리즘을 배우기.

이분탐색과 삼분탐색. 선형 시간을 로그 시간으로 줄여야 한다는 것과, 어떻게 줄이는지, 어떻게 줄었다고 확신할 수 있는지를 이해해야 합니다.

분할정복으로 쉽게 풀리는 문제들이 있음을 일찍 아는 것도 좋습니다.

그리디 알고리즘도 어렵죠.

유니온-파인드 알고리즘.

 

중급

세그먼트 트리. 인덱스드 트리. 세그먼트 트리에서 노드에 추가적인 정보를 저장하는 경우도 있는데, 세그먼트 트리의 활용 이라고 묶어서 글을 쓸 수 있을 것 같습니다. 세그먼트 트리를 사용한 스위핑.

그래프로서의 트리에 관한 문제가 많습니다. 트리의 지름. 트리 DP. LCA (최저 공통 조상) 알고리즘.

스파스 테이블.

convex hull과 알고리즘. CCW(counterclockwise) 함수는 덤이구요.

minimum spanning tree (MST)는 정말 꾸준하게 나타나 괴롭힙니다.

문자열을 볼까요. Manacher 알고리즘. suffix array와 longest common prefix. failure function과 KMP 알고리즘.
그리고 문자열 해싱. 트라이. 아호-코라식 알고리즘.

랜덤으로 문제풀기로 풀리는 문제는 '모르면 풀지 마시오' 같은 문제가 많습니다. 꼭 알아둡시다.

기초 정수론도 많이 쓰입니다. 빠른 거듭제곱, 유클리드 최대공약수 알고리즘, 모듈러 역원 구하기, 순열과 조합 구하기, 에라토스테네스의 체 정도는 알아두기.

빠른 거듭제곱을 사용하면 행렬 계산도 가능합니다. 행렬로 점화식 계산하기.

게임 문제와 그런디 넘버 역시 빼놓을 수 없는 개념입니다. 랜덤과 마찬가지로 '모르면 풀지 마시오' 수준이지요.

sqrt decomposition (Mo's algorithm)도 필요할 때가 있습니다.

작은 것, 큰 것 트릭.

좌표 압축도 알아두어야 합니다.

 

 

 

고급

여기서부터는 어려운 내용이 이어집니다.

네트워크 플로우로 모델링하는 이유와 중요성, 방법에 대해 배웁니다. 모델링을 하고 나면 최대 유량 알고리즘을 적용할 수 있습니다. 최대 이분 매칭도 몰라서는 안 됩니다. 최소 비용 유량 알고리즘.

persistent segment tree (PST)는 정말 강력한 도구입니다. 학술적으로는 일찍이 알려져 있었겠지만, PS 대회에서는 상당히 최근에 와서야 쓰이기 시작했습니다. 대략 2015년 즈음 같네요. PST와 연관짓자면 merge sort tree도 있습니다. 이 둘 중 하나는 쉽게 짜야 하는 세상이 되었습니다.

convex hull trick 역시 최근에 유명해진 테크닉 같네요.

heavy-light decomposition (HLD)도 그렇구요. centroid decomposition도 그런가?

set 개조하기는 comparator를 지정하는 방법에 관한 내용인데, 특별히 어려운 내용은 아니지만 이를 알아야 하는 문제는 보통 어려울 것 같아서 여기에 넣습니다.

발전한 정수론으로는 Miller-Rabin 소수 판별 알고리즘(링크), Pollard's rho 인수분해 알고리즘이 있습니다.

FFT 및 정수 체의 FFT(링크) 역시 고급에 오면 빼놓을 수 없는 주제입니다. XOR transform은 있다는 것만 기억하는둥 마는둥 해도 될 것 같네요.

카라츠바 알고리즘, 키타마사법.

Divide-and-Conquer optimization을 포함한 다양한 DP optimization이 있습니다.

Aliens 트릭으로 알려진 접근법이 있습니다.

SPFA라는 최단경로 알고리즘이 있습니다.

트리 압축 기법이 있습니다.

'알고리즘 문제풀기 > 기타 주제' 카테고리의 다른 글

PS 용어 정리  (0) 2019.05.25
PS 계열 커뮤니티와 웹 사이트  (4) 2019.04.23
CMS 세팅 (워커 등 분리)  (1) 2018.08.02
Code::Blocks에서의 편한 설정  (0) 2016.01.13
CMS Green  (0) 2015.08.20