책을 읽으며 기록합니다.
02 문제 해결 개관
2.1 도입: 문제 해결 능력은 어떻게 길러지는가?
문제 해결 능력은 프로그래밍 언어나 알고리즘처럼 명확히 정의된 실체가 없는 추상적인 개념이기 때문에 단순한 반복만으로는 연마하기 어려움.
이 능력을 기르기 위해서는 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마하는 것을 목표로 삼아야 함. 이를 위해서는 자신이 문제를 어떤 방식으로 해결하는지를 의식하고 어느 부분이 부족한지, 어떤 부분을 개선해야 할지를 파악해야함.
이를 위해서는 문제 해결 과정을 단계별로 나누어 푸는 과정이 필요함.
2.2 문제 해결 과정
파인만 알고리즘
- 칠판에 문제를 적는다.
- 문제를 골똘히 생각한다.
- 칠판에 답안을 적는다.
반쯤은 농담임. 하지만 배울 점이 있음. 첫번째로, 문제 해결 과정을 단계별로 나눔. 과정을 세분화 함으로써 어디가 부족하고 어디를 개선해야 하는지 판단할 수 있음. 두번째로, 문제를 적는 단계가 있음. 문제를 읽고 이해한 뒤 자신의 언어를 이용해 재정의한다는 뜻!
프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘
- 독해: 문제를 읽고 이해한다.
- 재정의+추상화: 문제를 익숙한 용어로 재정의한다.
- 설계: 어떻게 해결할지 계획을 세운다.
- 검증: 계획을 검증한다.
- 구현: 프로그램을 구현한다.
- 회고: 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
1. 독해: 문제를 읽고 이해한다.
이 단계의 중요성은 아무리 강조해도 지나치지 않음. 처음 참가하는 사람부터 과거의 챔피언까지 모든 프로그래밍 대회 참가자들이 공통으로 하는 실수가 있다면 바로 문제를 잘못 읽는 실수이기 때문이다.
문제 설명을 공격적으로 읽으며 문제가 원하는 바를 완전히 이해하는 과정이 반드시 필요함.
2. 재정의+추상화: 문제를 익숙한 용어로 재정의한다.
문제를 자신의 언어로 풀어 쓰는 단계. 이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요하며, 요구하는 바가 복잡한 문제일수록 그 중요성이 더해짐.
이 과정에서 문제의 추상화가 일어나는데, 이는 우리에게 익숙한 문제 해결 도구들을 문제에 적용할 수 있는 계기가 됨.
문제의 본질을 어떻게 재구성하느냐에 따라 같은 일을 하는 프로그램이더라도 전혀 다른 문제로 받아들여질 수 있음. 그러므로 실질적으로는 추상화 과정이 프로그래밍이 나아갈 방향을 결정한다고 볼 수 있음.
3. 설계: 어떻게 해결할지 계획을 세운다.
이 과정에서는 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료 구조를 선택함. (사실상 문제 해결에서 가장 중요한 단계)
2.3절에서 문제 해결 계획을 세울 때 사용할 수 있는 여러 전략들에 대해 자세히 다룸.
4. 검증: 계획을 검증한다.
우리가 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 함.
4장과 5장에서 각각 알고리즘의 효율성 분석 방법과 알고리즘의 정당성 증명에 관한 전략들을 다룸.
5. 구현: 프로그램을 구현한다.
아무리 천재적인 알고리즘을 고안했더라도 그 구현이 부정확하거나 비효율적이면 프로그램은 정확히 동작할 수 없음.
3장에서는 구현 단계에서 유의할 점들과 좋은 프로그램을 작성하기 위한 가이드라인을 소개함.
6. 회고: 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 많음. 문제 해결 기술은 외워야 할 의사 코드도, 엄밀한 증명도 없는 추상적인 기술이기 때문에, 이들을 연마하기 위해서는 끊임없이 자신이 이 기술들을 어떻게 사용하고 있는지를 돌아보고 개선해야 함.
효과적인 회고 수행 방법 1: 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것. 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지 적으면 좋음.
효과적인 회고 수행 방법 2: 반대로 한 번에 맞추지 못한 경우에는 오답 원인도 꼭 적는 것이 좋음. (오답 노트)
효과적인 회고 수행 방법 3: 같은 문제를 해결한 다름 사람의 코드를 보기
문제를 풀지 못할 때
초보 시절에는 한 문제에 너무 매달려 있는 것도 좋지 않음. 단, 다름 사람의 풀이를 참조할 때는 반드시 복기를 동반해야 함. 자신이 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이를 떠올리지 못했는지를 살펴보아야 한다는 뜻!
주의
해당 6단계를 너무 의식할 필요는 없음. 경험이 쌓임에 따라 이 과정들을 따로 의식하지 않아도 수행할 수 있기 때문.
2.3 문제 해결 전략
3단계 설계 과정에서 활용할 수 있는 접근법들을 소개함.
a. 직관
문제 해결 전략에서 먼저 강조해야 할 것은 문제와 답의 구조에 대한 직관의 중요성임. 문제를 보고 답안의 전체적인 얼개를 머릿속에 그릴 수 있으면 문제를 반쯤 해결한 것과 마찬가지이기 때문.
하지만 직관이 떠오르지 않는다면?
b. 체계적인 접근
체계적인 접근이란 백지에서부터 시작해 문제를 해결하기 위한 기반을 차근차근 쌓아올리면 점진적으로 전진하는 것을 의미함.
다음은 체계적인 접근을 위한 질문들로, 많은 문제에 적용될 수 있는 강력한 질문들부터 그 사용처가 제한되는 질문들의 순서대로 배열되어 있음.
1. 비슷한 문제를 풀어본적이 있나?
형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면 이전에 적용했던 방법과 비슷한 접근 방법을 사용할 것이라 예측할 수 있음. 허나 기존에 접했던 문제가 온전히 경험이 되려면 그 원리를 완전히 이해하고 변형할 수 있어야 함.
꼭 형태가 비슷하지 않더라도 문제의 목표가 같은 경우 또한 이런 사례에 속함.
2. 단순한 방법에서 시작할 수 있나?
이 책의 많은 연습 문제 풀이는 "무식하게 풀 수 있을까?" 라는 질문으로 시작함. 즉, 일단 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 보는 것임. 해당 전략의 일차적 목표는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 예방하는 것임.
허나 단순한 방법으로 모든 문제가 풀릴 수는 없음. 이 방법이 유용한 진짜 이유는 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문임. 이 경우 좀더 효율적인 자료 구조를 사용하거나, 계산 과정에서 같은 정보를 두 번 중복으로 계산하지 않는 등의 최적화를 적용하여 충분히 빨라질 때까지 알고리즘을 개선하는 식으로 문제를 풀 수 있음.
즉, 단순한 방법으로 시작하되 해당 방법을 개선하여 정답에 가까워지는 것!
3. 내가 문제를 푸는 과정을 수식화할 수 있나?
여기서 말하는 수식화는, 손으로 여러 간단한 입력 또는 예제 입력을 해결해보는 것을 말하는 것 같다.
손으로 여러 간단한 입력 또는 문제에 주어진 예제 입력을 직접 해결해보기. 이는 해당 과정을 공식화하여 답을 만드는 알고리즘을 만들 수 있는 경우가 흔히 있고, 그렇지 못하더라도 이 과정에서 알고리즘이 어떤 점을 고려해야 하는 지를 알게 되기 때문이다.
4. 문제를 단순화 할 수 없을까?
주어진 문제의 좀더 쉬운 변형판을 먼저 풀어보는 것!
문제를 쉽게 변형하는 방법
- 문제의 제약 조건 없애기
- 계산해야 하는 변수의 수를 줄이기
- 다차원의 문제를 1차원으로 줄여서 표현하기
이때 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수도 있고, 이것을 직접적으로 이용해 원래 문제를 풀어낼 수도 있음.
예시 문제를 풀던 중 나의 실수
직선 상의 점들이 주어질 때 이 점들까지의 거리의 합을 최소화하는 새로운 점을 찾는 상황에서, 나는 당연히 점들의 평균 위치이라고 생각했음. 하지만 이는 틀렸음.
반례
정답: 홀수 개의 점이 주어질 경우 가운데 있는 점이 최적이고, 짝수 개의 점이 주어질 경우 가운데 두 점 사이의 중간이 항상 최적이다.
5. 그림으로 그려볼 수 있나?
이것은 꼭 문제가 기하학을 다루지 않더라도 유용함.
두 개의 정수 쌍들을 다루는 문제가 있다면,
1. 이 정수 쌍을 2차원 평면 상의 좌표로 그려 볼 수도 있고,
2. 직선 상의 구간들로 그려 볼 수도 있음.
6. 수식으로 표현할 수 있나?
수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제를 해결하는 데 큰 도움을 줄 수도 있음.
7. 문제를 분해할 수 있나?
이 기술의 대표적인 예로 문제의 제약 조건을 분해하는 방법이 있음. 이 방법은 문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 여러 조건으로 분해함. 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문에 이 변형은 종종 유리함.
예시 문제를 풀던 중 나의 실수
첫 번째 조건 "선수 i는 선수 j에게 반드시 패배함"을 best[i] < worst[j]로 해석했는데, 이는 틀렸음. 왜냐하면 이 선수들은 달리기 선수들이므로 기록이 낮은게 승리하는 것임. 따라서 정답은 best[i] > worst[j]임.
또한 두 번째 조건을 첫 번째 조건과 같은 방식으로 해석하지 않았음. 이는 해당 장에서 배워가야 하는 내용과 직결됨.
8. 뒤에서부터 생각해서 문제를 풀 수 있나?
예를 들어 사다리 게임이 있음. 사다리 게임에서 정답을 아는 방법은 모든 시작점에서 사다리를 내려가는 것이 아니라, 당첨에서 시작해 거꾸로 올라가는 것임. A에서 B로 가는 것은 어렵지만, B에서 A로 가는 방법은 쉬운 경우가 있음.
9. 순서를 강제할 수 있나?
순서를 뒤집는 방법의 연장선으로, 순서를 강제하는 방법이 있다.
5x5 격자 불 켜기 예시 문항에서, 어떤 순서로 칸들을 클릭하든 상관이 없기 때문에, 특정 순서대로 칸들을 눌러야 한다는 제약을 문제에 추가하는 것임. 이 제약은 답을 변화시키지 않으며, 우리의 사고를 도와주는 역할을 한다.
10. 특정 형태의 답만을 고려할 수 있나?
순서를 강제하는 방법의 연장선으로, 정규화 기법이 있다.
정규화: 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법
정규화는 무한개의 모든 후보를 고려하는 대신에 후보의 유한한 부분 집합만을 고려할 수 있도록 해줌.
정규화 기법을 사용하기 위해서는 어떤 답이 주어지더라도 이것을 특정 형태의 답으로 바꿀 수 있는 변형 과정을 찾아야 함.
2.4 더 읽을거리
- 어떻게 문제를 풀 것인가 (How to Solve It)
