알고리즘 공부 방법/순서

baactree.tistory.com/14?category=735523

** 알고리즘 공부 방법/순서에 대한 글을 쓰고자 합니다. 내용은 차차 추가해 나갈 예정입니다.

 

- 이 글은 하이퍼링크 형태로 작성 되었습니다.

 

- 이 글은 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 책을 상당 부분 참고하여 작성하였습니다.

 

- 이 글은 학부 과정에서 배우는 C언어와 기초적인 자료구조(큐, 스택, 그래프, 트리, 힙, 이진검색트리, 딕셔너리)의 이론적인 이해가 있음을 가정하고 작성하였습니다.

 

** 17.10.9) 웹상에 좋은 자료들이 많으니 대부분의 내용을 링크로 대체하겠습니다. 

 

** 18.10.3) 링크 추가 및 업데이트

 

** 18.10.17) 방법에 대한 글은 여기에 포스팅하였습니다. 이 글은 순서(커리큘럼) 에 관한 글입니다.

 

---

 

** 언어의 선택

 

접기

알고리즘 문제를 해결하는데 있어서 가장 강력한 언어는 C++ 언어이다. 

일반적으로 소프트웨어 역랑평가나 알고리즘 대회는 C, C++ Java 이 세가지 언어를 지원한다.

추가적으로 Python을 지원하기도 한다.

C++은 C와 다르게 기본적인 소팅이나 자료구조가 모두 라이브러리에 구현 되어있고, 템플릿을 이용해 범용적인 클래스를 만드는데 용이하다. 

또한 속도 또한 Java보다 월등히 빠르다. 

따라서 필자는 C++ 언어를 통해 알고리즘 문제를 해결하는걸 강력히 추천하는 바이다.

접기

 

** 참고할 만한 사이트

 

접기

* 온라인 저지

백준

알고스팟

정올

 

* 대회

코드포스

앳코더

탑코더

 

* 알고리즘 강의

스타트링크

 

* 연간 대회

코드잼

페이스북 해커컵

코드그라운드

ACM-ICPC

접기

 

---

-- 기본적인 C++ 사용

 

** 알고리즘 기초

 

접기

- 복잡도 분석

 

- 문제 해결 전략

접기

 

 

** 입출력과 STL 사용

 

접기

- C++ 입/출력 정리

 

- C++ STL정리

접기

 

 

---

-- 소프트웨어 직군 역량평가를 위한 알고리즘

 

알고리즘 기법은 아래에 열거된 것들만 공부해도 충분하다고 생각한다. 

삼성 SW 역량테스트의 경우에는 초급부문에서만 출제된다.

 

** 알고리즘 초급

 

접기

- 완전 탐색

 

- DP(Dynamic Programming) 초급 

 

- 큐, 스택

 

- DFS

 

- BFS

 

- 탐욕법

접기

 

 

** 알고리즘 중급

 

접기

- 분할 정복

- 이분 탐색

 

- DP 중급

 

- 최단거리

다익스트라, 벨만 포드, 플로이드

 

- 최소 스패닝 트리

- 구간 트리(세그먼트 트리(탑-다운), 인덱스 트리(바텀-업), 팬윅트리(BIT))

 

- LCA(Lowest Common Ancestor)

 

- 비트마스크

 

- 서로소 집합

접기

 

 

---

-- 프로그래밍 대회를 위한 알고리즘

 

** 알고리즘 고급

 

 

접기

 

- 라인 스위핑

 

- 네트워크 플로우

 

- 이분 매칭

 

- KMP(Knuth-Morris-Pratt)

 

- Suffix Array, LCP(Longest Common Prefix)

 

- 트라이, 아호 코라식

 

- 단절점, 단절선

 

- SCC(Strongly Connected Component)

 

- 2-SAT

 

- SQRT(Square Root) Decomposition

 

- Heavy-Light Decomposition

 

- Centroid Decomposition

 

- FFT(Fast Fourier Transform)

 

- 기하

 

- Splay tree

 

- Link cut tree

접기

 

 

** 알고리즘에 필요한 수학

 

접기

링크

접기

 

---

-- 그외 팁

 

** 코딩 팁

 

접기

 

접기

 

** 자주하는 실수

 

접기

링크

접기