알고리즘 문제 해결 전략을 읽고 요약했습니다.
2.2 문제 해결 과정
1.문제를 읽고 이해하기
- 그림과 입출력 예제로 문제가 원하는 것을 유추하지 않기
2.재정의와 추상화
- 자신이 다루기 쉬운 개념을 이용해, 문제를 자신의 언어로 풀어 쓰는 것
- 문제의 추상화
3.계획 세우기
- 문제를 어떻게 해결할지 계획 세우기
- 문제를 어떻게 해결할지 결정
- 사용할 알고리즘과 자료구조 선택
4.계획 검증하기
5.계획 수정하기
6.회고하기
자신이 문제를 해결한 과정을 돌이켜 보고 개선하는 과정
코드와 함께 자신의 경험을 기록으로 남기는 것
- 문제의 간단한 해법
- 어떤 방식으로 접근했는지?
- 문제의 해법을 찾는데 결정적인 깨달음을 무엇이 있는지?
- 오답의 원인
- 오답노트를 통해 자주 틀리는 부분 확인하기
- 다른 사람의 코드 보기
- 문제를 풀지 못했을 때
- 일정 시간이 지나도록 고민해도 답을 못 찾을 때, 다른 사람의 풀이를 참조
- 다른사람의 풀이를 참고했을 대
- 자신이 문제를 해결할 때 취했던 접근들을 되새김
- 왜 이 풀이를 떠올리지 못 했는지 살펴 보기
2.3 문제 해결 전략
가장 좋은 방법
Best) 직관과 체계적인 접근
안되면? => 체계적인 접근 방법
백지에서부터 차근차근 쌓아 올리는 방법
체계적인 적근을 위한 질문들
1. 비슷한 문제를 풀어본 적이 있던가?
2. 단순한 방법에서 시작할 수 있을까? (무식하게 풀 수 있을까?)
시간과 공간의 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘
목표) 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 방지하기 위함
-> 만약 이 방법으로 안 풀린다면?
- 최적화 과정 필요
- 좀 더 효율적인 자료 구조를 사용
- 중복 계산 방지
[예제 문제]
N(N<=30)개 이하의 사탕을 세 명의 어린이에게 공평하게 나눠 주려고 한다.
이 때 사탕의 무게는 20 이하의 정수이다.
공평하다 -> 어린이들 중 가장 무거운 무게와 가장 가벼운 무게의 차이가 적을 수록 공평하다.
[문제 풀이]
문제를 푸는 가장 단순한 방법
- 어린이에게 나눠 주는 모든 방법을 하나씩 만들어 보기
- 경우의 수) $3^N$, 최대 205조 개
사탕의 총량을 상태 공간으로 하는 너비 우선 탐색
- 상태 공간: (0,0,0)
- 경우의 수) $(20*N+1)^3$, 최대 2억개
…
3. 내가 문제를 푸는 과정을 수식화 할 수 있을까?
4. 문제를 단순화 할 수 있을까?
2차원 -> 1차원
- 왼쪽에 점이 더 많으면 왼쪽으로
- 오른쪽에 점이 더 많으면 오른쪽으로
5. 그림으로 그려볼 수 있을까?
6. 수식으로 표현할 수 있을까?
7. 문제를 분해할 수 있을까?
더 다루기 쉬운 형태로 문제를 변형하는 것
문제의 제약 조건 분해
8. 뒤에서 부터 생각해 문제를 풀 수 있을까?
문제에 내재되어 있는 순서를 바꿔 보는 것
- ex) 사다리 게임에서 위로 올라가는 과정
9. 순서를 강제할 수 있을까?
[예제 문제]
- 어떤 순서로 버튼이 눌리던 상관 없다.
- 같은 칸을 2번 누를 일은 없다.
[문제 풀이]
- 5x5 -> $2^{25}$ 가지의 경우의 수
- 모든 칸을 왼쪽 위에서부터 순서대로 누르게 강제
- $2^5$ -> …
- 누를 수 있는 경우의 수를 줄여 나가기
10. 특정 형태의 답변을 고려할 수 있을까?
정규화 기법(Canonicalization)
- 우리가 고려해야할 답들 중 형태가 다르지만 결과적으로 똑같은 것들을 묶은 후 그들의 대표만 고려하는 방식