코딩테스트를 위한 자료구조와 알고리즘 with c++

독서기간_22년 11월 21일 ~ 22년 11월 22일

저자_존 캐리, 세리안 도시, 피야스 라잔

 

 

---

 

 

급하게 코테를 벼락치기 해야 할 일이 있어서 급하게 읽은 책^^ 이론 위주로 읽었다. 

 

C++ STL 라이브러리, 트리, 힙, 해시 테이블, 분할 정복, 그리디, 정렬, 그래프1, 그래프2, 동적 계획법1, 동적 계획법2로 목차가 구성되어 있다. 코테에 출제되는 수준의 알고리즘을 다룬다.

 

알고리즘이 이론뿐만 아니라 실무에서 성능을 고려하는 알고리즘을 사용하는 방법을 알 수 있다. 예를 들어, 블룸필터가 거짓-부정(false-negative)이 없다는 것은 확신하지만 거짓-긍정(false-positive)이 있다는 것은 확신하지 못하는 알고리즘이라면, 수억 개의 이메일에서 중복되는 이메일이 있는지 찾는 알고리즘으로 사용된다는 것이다. 

프로젝트를 진행하며 동일 데이터가 존재하는지 확인하는 알고리즘을 많이 짜봤지만 수억 개의 데이터가 존재할 때의 성능을 고려한 적이 없었다. 

 

문제 풀이 위주의 책은 아니니 이걸로 코테를 준비해야겠어! 라는 사람에겐 비추천한다. 기본 지식을 쌓는 용도이다. 특히 그래프 유형 별로 알고리즘을 비교&제시해서 괜찮았다. MST, 프림, 크루스칼, 다익스트라, 벨만포드, 플로이드와샬 등등... 각각의 특징과 장단점, 사용하는 상황을 확실하게 알 수 있다. 하지만 다루지 않는 알고리즘도 많으니 다양한 책을 읽어야 될 것 같다. (특히 트리)

 

또 문자열 알고리즘 문제를 풀면서 트라이 알고리즘을 처음 알았는데, 트리를 이용한 풀이도 공부해야겠다. 동일한 문자열이 있는지 판별하는 방법으로 효율적인 알고리즘이다. 이 또한 단순히 string.contains를 활용하면 될 줄 알았는데 방대한 데이터에서 사용하기엔 무리가 있구나를 깨달았다. 그래서 카카오 코테에 문자열이 자주 나오는 것인가...

 

개발자에게 알고리즘은 평생의 숙명..........