문제 해결 과정
문제를 읽고 이해한다.
가장 중요하다. 가능한 한 빠른 시간 내에 문제를 풀어야 하는 상황에서는, 조급한 마음에 문제를 대충 읽고 푸는 경우가 있다. 문제 설명을 공격적으로 읽으며, 문제가 원하는 바를 완전히 이해하는 과정이 반드시 필요하다.
재정의와 추상화
문제의 의미를 자신이 다루기 쉬운 개념으로 변환하는 작업. 문제가 어려우면 어려울수록 문제를 자기만의 방법으로 이해하는 것이 중요하다. 이 과정에서 문제를 추상화 할 수 있다. 현실 세계의 개념은 복잡하니까 이를 단순화시켜서 내가 아는 개념을 적용할 수 있는 상태로 변환하는 것이다.
계획 세우기
어떻게 해결할 지 계획을 세운다. 문제를 어떤 방식으로 해결할지 결정하고, 사용할 자료구조와 알고리즘을 선택한다.
계획 검증하기
구현을 시작하기 전에 계획 세우기에서 세웠던 계획을 검증하는 과정을 거쳐야 한다. 계획 세우기에서 세운 계획이 요구 조건을 정확히 수행하는지 검증하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 시간 내에 들어가는지 확인한다.
계획 수행하기
계획을 코드로 변환한다.
회고하기
자신이 문제를 해결한 과정을 돌이켜 보고, 개선한다. 두 번째로 문제를 풀 때는 더 효율적인 알고리즘을 찾거나 간결한 코드를 작성할 수도 있고, 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾을 수도 있다. 회고하는 가장 좋은 방법은 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것이다.
- 문제의 해법
- 어떤 방식으로 접근했는지
- 문제의 해답을 찾는 데 가장 결정적이었던 깨달음은 무엇이었는지
를 기록하는 버릇을 기르면 좋다. 한번에 답을 찾지 못한 경우에는 오답 원인도 꼭 적으면 좋다. 또한 다른 사람이 문제를 해결한 코드를 확인하는 것도 좋다. 따라서 혼자서만 문제를 풀지 않고 그룹 스터디나 인터넷을 활용하여 다른 사람과 같이 공부하는 것이 매우 중요하다.
문제 해결 전략
이 부분은 앞에 과정 중에 <계획 세우기> 에서 수행하는, 어떻게 문제를 해결할지 전략을 세우는 부분이다. 문제에 어떻게 접근하면 될지 알려주는 몇 가지 기법들이 있다.
비슷한 문제를 풀어본 적이 있는가?
비슷한 문제를 풀어봤다면 비슷한 접근 방법을 사용하면 될 것이라고 예측할 수 있다.
단순한 방법에서 시작할 수 없을까?
시간과 공간 제약을 생각하지 않고 문제를 풀어본다.
문제 : N(N<=30)개의 사탕을 세 명의 어린이에게 가능한 한 공평하게 나눠 주려고 한다.
공평함은 사탕의 총 무게가 가장 무거운 어린이 - 가장 가벼운 어린이의 차이라고 정의한다.
사탕의 문게는 모두 20 이하의 정수이다.
가장 무거운 어린이 - 가장 가벼운 어린이의 차가 최소가 되는 건 얼마일까요?
~~~ java
1. 사탕을 나눠 주는 모든 방법을 하나씩 만들어본다. 각 사탕마다 세 명 중 한명한테 준다고 가정하면 가능한 경우의 수는 3^N 가지이다.
2. 받은 사탕들이 서로 다르더라도 그 무게는 같을 수 있다. 각각의 아이마다 상태를 표시하는 공간을 둔다. (0, 0, 0)으로 시작하여, 사탕을 하나 줄 때마다 아이가 가진 사탕의 양을 늘린다. 사탕의 최대 무게는 200이므로, 각 아이가 가진 사탕의 양은 0에서 20 * N의 사이이다. 따라서 이와 같이 문제를 풀려면 대략 2억개의 배열을 잡아야 한다.
3. 사탕의 최대 무개는 20이므로, 사탕을 가장 많이 받은 애가 가장 적게 받은 애한테 하나 준다고 해도 총량이 역전되지 않는다. 즉, 차이가 20 이상인 경우에는 최적해가 될 수 없다. (한 개를 주면 차이가 줄기 때문에) 따라서 20*N / 3 + 20 넘게 사탕을 받는 경우는 무시해도 된다. 따라서 배열의 크기는 대략 천만 정도로 줄게 된다.
4. 누가 사탕을 많이 받고, 누가 사탕을 적게 받는지는 중요하지 않다. (180, 190, 200) or (200, 190, 180) 은 큰 차이가 없다. 따라서 총량이 항상 오름차순으로 정렬된 형태를 택하면 경우의 수가 대략 1/6로 줄어들게 된다.
## 문제를 푸는 과정을 수식화할 수 있을까?
손으로 여러 간단한 입력을 직접 해본다. 문제에 주어진 예제 입력을 직접 해결해 보는것은 큰 도움이 된다.
## 문제를 단순화할 수 없을까?
문제의 제약 조건을 없애거나, 계산해야 하는 변수의 수를 줄이거나, 다차원의 문제를 1차원으로 변형해서 풀어볼 수 있다.
## 그림으로 그려볼 수 있을까?
문제에 관련한 그림을 그려보는 것은 효율적일 수 있다.
## 수식으로 표현할 수 있을까?
평문으로 쓰여 있는 문제를 수식으로 표현하는 것이 도움이 되는 경우가 있다. 수식을 전개, 축약하는 과정에서 수학적 조작이 문제를 해결하는 데 큰 도움을 줄 수 있기 때문이다.
## 문제를 분해할 수 있을까?
더 다루기 쉬운 형태로 문제를 변형한다. 대표적인 방법으로는 문제의 제약 조건을 분해하는 방법이 있다. 문제의 제약 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해하는 것이다.
## 뒤에서부터 생각해서 문제를 풀 수 있을까?
문제에 내제된 순서를 바꿔서 생각해 보는 것이다. 예를 들면, 사다리 타기에서 가고 싶은 칸에서부터 거꾸로 올라가는 것이다. A->B는 어렵지만 B->A는 쉬울 수 있다.
## 순서를 강제할 수 있을까?
순서가 없는 문제에 순서를 강제하여 문제를 풀 수 있다. 경우의 수 문제를 풀 때 특히 유용하다. 특정 조건을 만족하는 답들의 수를 셀 때, 순서를 강제하여 답의 중복 셈을 막을 수 있다.
## 특정 형태의 답만을 고려할 수 있을까?
고려해야 할 답들 중 형태가 다르지만, 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤에, 각 그룹의 대표들만을 고려하는 방법이다.