코딩 테스트 중상위 문제와 실무에서 종종 만나는 알고리즘 42편을 모았습니다. 그래프에서는 다익스트라·위상 정렬·최소 신장 트리·사이클 검출·이분 그래프 판정을 다뤄요. 동적 계획법 쪽은 최장 공통 부분 수열과 편집 거리 같은 2차원 DP, 최장 증가 부분 수열, 트리 DP·구간 DP·자릿수 DP가 맡습니다. 세그먼트 트리·펜윅 트리·트라이·힙·단조 스택·단조 덱을 쓰는 문제와 문자열 검색·퀵셀렉트·비트 연산·빠른 거듭제곱·유클리드 호제법·에라토스테네스의 체도 들어 있어요.

모든 장은 같은 순서로 읽힙니다. 먼저 무엇을 푸는 문제인지, 왜 단순한 방법으로는 모자란지를 그림과 수로 봐요. 그다음 누구나 떠올리는 단순한 방법에서 출발해 이 알고리즘까지 한 걸음씩 걸어갑니다. 입력 하나를 골라 단계마다 값을 적으며 끝까지 실행하면 마지막 단계에서 전체 코드가 완성돼요. 뒤 파트는 따지는 자리입니다. 어떤 문제에 쓰는지, 실행 내내 참으로 남는 불변식이 왜 정답을 보장하는지, 시간과 공간이 얼마나 드는지를 봅니다.

「그렇게 해도 되지 않나」 싶은 방법은 반례로 왜 틀리는지 짚고 넘어가요. 장 끝에는 스스로 답해 볼 물음과 그 답, 직접 풀어 볼 문제가 있습니다. 코드는 TypeScript로 썼어요.

기본 알고리즘을 익힌 뒤 한 단계 위의 문제로 넘어가려는 분께 맞는 책이에요. 시리즈는 중요도에 따라 세권으로 나뉘고, 이 책은 시리즈의 2권입니다.

본문 초고는 생성형 AI(Claude)가 쓰고, 저자가 검토하고 고쳤습니다.