구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 도입 2. 재귀 호출과 완전 탐색 3. 소풍 (문제 ID: PICNIC, 난이도: 하) 4. 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하) 5. 최적화 문제(Optimization problem) 6. 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) 7. 많이 등장하는 완전 탐색 유형 1. 도입 공부를 할 수록 우아한 답안을 만들고 싶은 욕구가 커지고, 그로 인해 쉽고 간단하며 틀릴 가능성이 낮은 답안을 놓치는 경우가 있다. 문제를 가장 처음 봤을 때는 "무식하게 풀 수 있을까?"라고 스스로에게 먼저 물어봐야 한다. 무식하게 푸는(brute-force) 알고리즘을 완..

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 수학적 귀납법과 반복문 불변식 2. 귀류법 3. 다른 기술들 1. 수학적 귀납법과 반복문 불변식 • 수학적 귀납법(mathematical induction) • 반복문 불변식(loop invariant) • 이진 탐색과 반복문 불변식 • 삽입 정렬과 반복문 불변식 • 단정문을 이용해 반복문 불변식 강제하기 📌 수학적 귀납법(mathematical induction) 반복적인 구조를 갖는 명제들을 증명하는데 유용하다. 귀납법 증명은 크게 3단계로 나눈다. 단계 나누기 증명하고 싶은 사실을 여러 단계로 나눈다. ex1. 100개의 도미노가 순서대로 있다. ex2. 텅 빈 N개의 세로줄에서 가로 줄을..

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. Overall 2. 선형 시간 알고리즘 3. 선형 이하 시간 알고리즘 4. 지수 시간 알고리즘 5. 시간 복잡도 6. 수행 시간 어림짐작하기 7. 계산 복잡도 클래스: P, NP, NP-완비 1. Overall • 알고리즘 평가 기준 • 프로그램 실행 시간 != 알고리즘 속도 • 반복문이 지배한다 📌 알고리즘 평가 기준 시간 알고리즘 수행 시간이 작을 수록 더 빠르게 동작하는 것을 의미 시간 안에 실행되지 않는다면 답안의 정확도와 상관없이 오답 알고리즘 수행 속도와 특성을 분석하는 능력 필요 공간 적은 용량의 메모리를 사용 알고리즘이 아무리 빨라도, 너무 많은 메모리 공간을 요구한다면 오답 📌 ..

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 코딩의 중요성 2. 좋은 코드를 짜기 위한 원칙 3. 자주 하는 실수 4. 디버깅과 테스팅 5. 변수 범위의 이해 6. 실수 자료형의 이해 1. 코딩의 중요성 사람들을 가르치다보면, 본인이 코테를 못하는 이유가 알고리즘과 자료 구조에 대한 지식이 부족해서라고 잘못 생각하는 사람들이 많다. 물론, 많이 안다는 것은 유용하고 때론 중요하고 강력한 알고리즘이 존재하긴 하지만, 과연 그게 가장 큰 문제라고 묻느냐면 난 아니라고 생각한다. 제 아무리 로직을 머리에 꿰고 있다고 해도 그것을 구현하는 "구현력"은 별개다. 그리고 구현 과정에 있어서, 어떤 식으로 코드를 작성하는지도 천차만별이고 같은 로직을 ..