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