[알고리즘] 문제 풀이 주제별 관련 우선순위

알고리즘 문제 풀이대회가 많다.

특히 삼성 쪽에서 많은 관심을 보이고 있다.

알고리즘 문제 풀이 면접이나 대회도 개최하고 있으며,

입사하고 나서도 문제 풀이(상대 평가)를 통해 등급을 나눈다. (익스퍼트, 프로페셔널... 등등 익스퍼트에 도달해야만 상대평가에서 면제라고 들었다. )

여튼 입사 면접 시험을 위해,

스펙을 위해

재미를 위해 

그냥 해보고 싶어서 등등 여러 이유를 가지고 알고리즘 관련된 공부를 시작하는 사람들에게

알고리즘 문제풀이를 위해 준비(공부)해야할 주제별 우선순위를 생각해보았다.

먼저 책은 종만북 추천드립니다.

이유는 내용은 어려워도 설명이 잘 되어 있기 때문.

주제별 우선순위는 알고리즘 문제 풀이를 제 주변에서 제일 잘하는 친구가 쓴 글을 허락없이 그냥 들고왔다.

추후에 걔가 이 글을 보고 태클을 건다면 글을 내리던가 정확히 출처를 밝히던가 하겠다.

---

상(필수)

기초 자료구조 활용(스택, 큐, 트리 등등)

DFS, BFS

Dynamic Programming(여러가지 유형의 문제 모두 접해보기. 매우 중요.)

부분합 (1차원, 2차원 부분 합-> 종만북에 아주 잘 설명되어 있음.)

최단경로(다익스트라, 플로이드 알고리즘 중요)

최소 스패닝 트리

정수론(유클리드 호제법, 에라토스테네스의 체)

파라매틱 서치(이분법)

그리디(대표적인 그리디 유형들은 알아두어야 함)

백트랙킹

최소한 상은 어떤 교수님의 표현을 빌리자면 뚝딱뚝딱, 촥촥촥 바로바로 만들어낼 수 있을 정도로 숙달해야 한다고 한다.

(물론 대회 입상을 목표로 한다면)

---

중(이 유형의 문제를 풀면 삼성 문제풀이대회 기준으로 본선 진출 확률이 높음)

세그먼트 트리

펜윅 트리

상호 배타 집합

KMP

트라이

네트워크 플로우(최대플로우, MCMF, 이분 매칭 등등)

2-SAT

SCC

단절점, 단절선

LCA

Repeated Squaring

페르마의 소정리

기하 기초(점과 점사이 거리, 점과 선사이 거리, 선과 선사이 거리, CCW 등등)

CLosest Pair

Convex hull

---

하( 출제 빈도가 낮음)

문자열 (Aho-Corasick, 접미사 배열)

Manacher's algorithm

가우스 소거법

다니아믹 프로그래밍 최적화 기법(Convex hull, Devide and Conquer, Knuth ...)

MO's algorithm

Fast Fourier Transform

Heavy-Light Decomposition

계산 기하(Delaunay Triangulation, Rotating Calipers ...)

Lazy Propagation

각종 고급 자료구조(Persistent Segment Tree, Splay Tree, Euler Tour Tree...)

---

뿐만 아니라 유명한 문제들은 알아 두어야함.

(배낭객 문제 같은.. -> 실제로 2017년 삼성 면접시험에 이것과 똑같은 모델링 문제가 나옴)

각종 온라인 콘테스트(코드포스, 탑코더)에 참가하는게 좋다고함.