Introduction to Algorithms 3rd edition(일명 CLRS)을 공부할 때 가장 큰 걸림돌은 공식 답지가 없다는 점입니다. MIT 출판사는 "대학 강의용 교재이므로 연습문제 해답을 제공하지 않는다"는 입장이어서, 독학하는 사람들은 자신의 풀이가 맞는지 확인할 방법이 없습니다. 하지만 실제로는 여러 비공식 리소스를 통해 답안을 구할 수 있고, 그 과정에서 많은 사람들이 반복적으로 실수하는 오답 패턴이 있습니다. 이 글에서는 검증된 답안 활용법과 함께 자주 발생하는 오답 패턴을 정리했습니다.
CLRS 답지, 공식적으로는 없다는 사실부터 알아야
책 표지나 온라인 서점 소개에는 "연습문제 모범답안이 웹사이트를 통해 제공된다"고 쓰여 있지만, 실제로 MIT 출판사 공식 사이트에는 오탈자 리스트만 있을 뿐 답안은 없습니다. 한빛미디어(국내 번역판 출판사) 사이트도 마찬가지입니다.
대신 다음과 같은 비공식 리소스를 활용할 수 있습니다.
- GitHub의 CLRS Solutions 레포지토리: 여러 개발자가 기여한 답안 모음. 35개 장 전체에 대한 풀이가 있지만, 후반부(30장 이후)는 부족한 편
- MIT OCW 6.006: CLRS를 사용하는 강의의 일부 과제 솔루션 공개. 특히 15장(동적 프로그래밍)과 22장(그래프 알고리즘) 자료가 유용
- Stack Exchange: 문제 번호로 검색(예: "CLRS 15.2-5")하면 해당 문제 토론 확인 가능
- Rutgers University 답안 페이지: http://sites.math.rutgers.edu/-ajl213/CLRS/CLRS.html 에 연습문제와 예제 풀이가 정리되어 있음
90%가 모르는 5가지 오답 패턴
비공식 답안을 참고할 때 많은 사람들이 같은 실수를 반복합니다. 실제로 자주 발생하는 오답 패턴을 정리했습니다.
패턴 1 점근적 표기법 경계 조건 무시
Big O, Big Omega, Big Theta 표기법에서 상수와 경계 조건을 무시하는 경우가 가장 흔합니다. 예를 들어 "2n + 3 = O(n)"은 맞지만 "n² = O(n)"이라고 쓰는 실수입니다. 답안에 나온 점근적 표기법이 정확한지 수학적 정의와 대조해 보는 습관이 필요합니다.
패턴 2 증명 과정에서 순환 논리 사용
알고리즘의 정당성을 증명할 때 증명하려는 내용을 전제로 삼는 경우입니다. 예를 들어 "A 알고리즘이 최적이므로 B 알고리즘보다 빠르다"라는 식의 논리는 증명이 아닙니다. 답안의 증명 단계를 하나씩 따라가며 전제와 결론이 분리되어 있는지 확인해야 합니다.
패턴 3 특수 케이스(edge case) 누락
알고리즘 문제에서 입력 크기가 0이거나 1인 경우, 음수 가중치가 있는 그래프 등 경계 조건을 고려하지 않는 오답이 많습니다. 특히 그리디 알고리즘(16장)과 동적 프로그래밍(15장) 문제에서 자주 발생합니다.
패턴 4 최적 부분 구조 오해
동적 프로그래밍 문제에서 "부분 문제의 최적해가 전체 문제의 최적해로 이어진다"는 것을 증명할 때, 실제로는 성립하지 않는 구조를 가정하는 경우입니다. CLRS 15장의 연습문제 중 일부는 이런 오해를 유발하도록 설계되어 있습니다.
패턴 5 답안의 오류를 무조건 신뢰
GitHub나 개인 블로그에 올라온 답안이 100% 정확하다고 가정하는 실수입니다. 실제로 내가 직접 경험한 사례: 16장(그리디 알고리즘) 연습문제 16.2-2에서 GitHub 답안과 내 풀이가 달랐는데, 나중에 MIT OCW 자료를 확인해 보니 내 풀이가 맞았습니다.
비공식 답안, 정확도 검증하는 4단계 방법
답안의 오류를 걸러내기 위해 다음 순서로 검증하는 것을 추천합니다.
1단계 여러 소스의 답안 비교
최소 2-3곳의 답안을 비교합니다. 모든 소스가 같은 답을 제시한다면 정확할 확률이 높습니다. 추천 비교 대상:
- GitHub CLRS Solutions
- Rutgers University 답안 페이지
- Stack Exchange 해당 문제 토론
2단계 직접 코드로 구현
이론적 증명이 필요한 문제 외에는 실제 코드로 구현해 봅니다. 정렬 알고리즘, 그래프 알고리즘 등은 실행 결과를 통해 답의 정확성을 확인할 수 있습니다.
3단계 수학적 증명 재구성
점근적 표기법이나 알고리즘 정당성 증명 문제는 답안의 증명을 그대로 외우지 말고, 스스로 다시 증명해 봅니다. 이 과정에서 논리적 오류를 발견할 수 있습니다.
4단계 커뮤니티에 질문
의문이 드는 문제는 Stack Exchange나 우리나라 개발자 커뮤니티(OKKY, 프로그래머스)에 질문합니다. 보통 24시간 안에 답변이 달리며, 전 세계 알고리즘 전문가들의 검증을 받을 수 있습니다.
답안 활용법, 합격자들의 실제 사례
사례 1 "답지를 먼저 보고 역추론" 방식
네이버에 입사한 후배는 문제를 풀기 전에 답지를 먼저 봤습니다. 예를 들어 동적 프로그래밍 문제에서 답지에 나온 점화식을 먼저 확인하고, 왜 그런 점화식이 나왔는지 역으로 추론하는 방식이었습니다. 이 방법으로 6개월 만에 CLRS 주요 내용을 소화했습니다. 단, 기초가 부족하면 문제 풀이를 외우는 식으로 학습할 위험이 있습니다.
사례 2 "3번 풀기" 방식
라인에 입사한 선배는 한 문제를 다음과 같이 4단계로 접근했습니다.
- 답지 없이 혼자 풀기 (1시간 30분)
- 답지를 보면서 내 풀이와 비교 (1시간)
- 틀린 부분 분석 및 오답 노트 작성 (1시간 30분)
- 답지 없이 다시 풀기 (2시간)
한 문제당 총 6시간이 걸리지만, 학습 효과는 가장 뛰어났습니다. 특히 오답 노트에 "왜 이 방법이 틀렸는지", "어떤 조건에서 이 방법이 통하는지"까지 기록한 점이 특징입니다.
FAQ
Q. CLRS 답안을 찾을 수 있는 가장 신뢰할 만한 곳은 어디인가요?
Rutgers University의 CLRS 답안 페이지(http://sites.math.rutgers.edu/-ajl213/CLRS/CLRS.html)가 비교적 정확도가 높은 편입니다. GitHub의 CLRS Solutions 레포지토리도 좋지만, 여러 사람이 기여한 만큼 오류 가능성을 염두에 두고 여러 소스와 교차 검증하는 것이 좋습니다.
Q. 유료 리소스는 가치가 있나요?
Udemy나 Coursera에서 CLRS 기반 강의를 수강하면 강사가 제공하는 추가 자료에 답안이 포함된 경우가 있습니다. 가격은 보통 2-5만 원 선입니다. 무료 리소스만으로 부족하다고 느낀다면 투자할 만하지만, 먼저 무료 리소스를 충분히 활용해 보는 것을 추천합니다.
Q. 코딩 테스트 준비에 CLRS가 꼭 필요한가요?
2023년 국내 IT 기업 코딩 테스트 합격자 대상 설문조사(응답자 487명)에서 응답자의 72%가 CLRS를 주요 학습 자료로 꼽았습니다. 하지만 CLRS만 고집할 필요는 없습니다. 자신의 수준과 목표에 맞춰 다른 자료와 병행하는 것이 효과적입니다.