알고리즘 공부 회고

 알고리즘에 몰입했던 한 달

프로그래머스

solved.ac

코딩 테스트를 준비하기 위해서 알고리즘 공부를 꾸준히 해왔지만, 이번 방학 한 달간에 알고리즘에 푹 빠져서 다양한 문제들을 많이 풀어봤다. 기존에 풀었던 문제들도 있어서 모든 문제를 이번 방학에 풀었던 것은 아니고 대충 한 달 동안 100문제 정도 풀었다.

https://github.com/WAQESD/Algorithm

GitHub - WAQESD/Algorithm

특히 백준에서 풀었던 문제들은 문제를 푼 날짜별로 문제정보와 함께 정리해놨다. 

방학이 끝나고 시간이 지나고 나니 내가 풀었던 문제들을 다시 풀 수 있을지, 공부했던 알고리즘들을 다시 구현할 수 있을지 의문이 들었고 정리해둔 정보를 확용해서 복습하기로 마음을 먹었다.

회고를 쓰게 된 이유는 원래 복습 할 내용의 목차를 작성하려고 했는데 겸사겸사 회고로 작성하면서 점수를 쌓아 올리던 때의 성취감을 되새김질 하고 싶었다.

 

새로 공부했던 알고리즘들

DP, DFS, BFS와 같이 워낙 유명한 알고리즘들은 당연히 기억하고 있기 때문에 지금 상태에서 찾아보지 않고는 구현하기 힘들 것 같은 알고리즘들을 정리해봤다.

- 외판원 순회(비트필드를 이용한 다이나믹 프로그래밍)

- 위상 정렬

- 최소 스패닝 트리(MST)

- 분리 집합, Union-Find

- 투포인터, 중간에서 만나기

- 세그먼트 트리

- 2-sat

- 스위핑

- 강한 연결 요소(SCC)

- 최소 공통 조상(LCA)

- 데이크스트라(Dijkstra)

- 트라이(Trie)

- 단절점과 단절선

- 배낭 문제(knapsack problem)

- 0 - 1 BFS

- KMP

- 오프라인 쿼리, mo's

- 스프라그 그런디 정리

- 최대 유량

정리를 하면서도 개념이 생각나지 않는 알고리즘들이 꽤나 있는걸로 봐선 복습이 반드시 필요했던 상황인것 같다.

 

알고리즘 공부를 잠시 중단했던 이유

백준에서 문제에 적용된 알고리즘 자체가 어려운 경우에 응용 없이 풀 수 있는 문제에도 높은 등급을 주기 때문에 새로운 알고리즘을 공부하면 높은 등급의 문제들을 쉽게 풀 수 있다.

그리고 나는 점수를 올리고 싶어 높은 등급 문제를 푸는 것에 신경 쓰기 시작했고, 그런 내 모습에 회의감이 들어 한달 동안 몰입하고 있었던 알고리즘 공부를 잠시 중단하기로 했다.내가 푼 문제들을 보면 플레티넘 난이도의 문제들도 많이 푼 것을 볼 수 있지만, 정작 골드 난이도의 어려운 DP 문제나 구현 문제를 풀려고 하면 두세 시간씩 걸리거나 못 푸는 경우도 허다했다.

 

앞으로의 공부 계획

위에 정리해 놓은 알고리즘들을 하나씩 블로그에 정리하면서 문제를 풀어 볼 예정이다.대부분은 코딩테스트에서 만나보기 힘든 알고리즘이지만 개발자라면 저 정도의 알고리즘은 알고 있어야 한다고 생각하기 때문에 시간을 두고 천천히 복습해 나가야겠다.