Algorithm Problem Solving

원래는 알고리즘별로 정리해서 블로그에 포스팅하려 했는데, 군대에서 PS에 쏟을 시간이 많지가 않아서 일단은 깃헙 레포에 정리해보려함. 이 레포를 방문하는 극소수의 사람들도 이해할 수 있도록 쓴다면 좋겠지만, 일단은 나만 알아보도록 쓸 것...

본인이 읽고있는 책

• [ Introduction to Algorithm(CLRS) ]
  알고리즘 분석, 트리, 그래프 그리고 정수론, 문자열의 일부분만 읽었음. 자료구조의 성질, 알고리즘의 증명 및 정리가 상세하게 나와있어서 공부하는 맛이 나긴 하지만... 머리가 나쁜 탓일까 아님 번역체가 이해하기 힘든 것일까? 그리 술술 읽히는 편은 아닌듯. 그래도 설명 중간중간 적절한 삽화가 이해하는데 매우매우 도움이됨.
• [ 알고리즘 트레이닝 : 자료 구조, 알고리즘 문제 해결 핵심 노하우 (원제: Competitive Programming: The New Lower Bound of Programming Contests) ]
  오늘 주문해서 아직 받아보지 못한 책. 위의 책이 이론, 증명에 치중한 책이라면 이 책은 원제에서 알 수 있듯이 CP(Competitive Programming) 즉 알고리즘 대회를 위해 쓰여진 책임. 모 PS 커뮤니티에서는 하얀책 이라고 알려져 있는 것 같음. 그들의 리뷰에 따르면 ICPC에서 출제되는 알고리즘 유형이 많이 수록되어있다고 함.

공부한 내용

여기서부터는 조금이라도 알고있는 알고리즘을 서술 할 것임. 필자의 미천한 지식 수준을 엿볼 수 있는 대목. 이후에 링크를 달아서 각 알고리즘과 관련 문제(BOJ)를 설명해 볼 계획임. 물론 소스코드는 없고 작성하게 된다면 의사코드로 하지 않을까?

트리

• 힙
• 이진트리 & Red-Black & AVL
• 기수트리
• 세그먼트 트리 & 느리게 전파되는 세그먼트 트리(레이지세그)
• 팬윅트리

그래프

• DFS & BFS
• 크루스칼 & 프림 & 다익스트라
• 위상정렬
• 벨만-포드

문자열

• KMP
• 트라이

수학

• 유클리드 호제법 & 확장된 유클리드 호제법
• GCD & LCM
• 페르마 소정리

공부할 내용

공부할 알고리즘이야 차고 넘치지만, 재밌어보여서 일단 먼저 하고싶은것들...

• 2-SAT
• LCP배열
• 비트마스크
• 플로이드-워샬
• 포드-풀커슨
• 라빈-카프