2장: 문제 해결 개관 (21p ~ 42p)

문제 해결 과정

1. 문제를 읽고 이해한다.
   • 문제를 노트에 다시 써보면 문제를 제대로 이해하기 좋다.
2. 문제를 익숙한 용어로 재정의한다.
   • 여러 수식어가 붙어있는 문제를 간단한 문제로 축약시키면 문제를 이해하기 좋다.
3. 어떻게 해결할지 계획을 세운다.
   • 문제에서 어떤 알고리즘과 어떤 자료 구조를 사용할지를 결정한다.
4. 계획을 검증한다.
   • 사용할 알고리즘이 문제의 상황에 맞는지, 즉 메모리와 소요 시간이 적합한지 등을 확인한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 계선할 방법이 있는지 찾아본다.
   • 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지, 문제를 풀면서 어려움을 겪었던 점은 무었이었는지를 기록하며 오답노트를 작성한다. 또 다른 사람이 쓴 코드를 보면 자신이 생각하지 못했던 통찰을 얻을 수도 있다.

 

문제를 풀지 못할 때

1. 비슷한 문제를 풀어본 적이 있던가?
2. 단순한 방법에서 시작할 수 있을까?
   • 단순한 방법으로 풀면 기준선 알고리즘으로 활용할 수 있으며 이를 통해 직관이 생기기도 한다.
   • ex) 소수 판정법에서 브루트 포스와 아리스토테네스의 체 알고리즘과 비교해본다.
3. 내가 문제를 푸는 과정을 수식화 할 수 있을까?
   • 문제를 수식으로 나타내면 명료하게 문제를 바라볼 수 있다.
   • ex) 동적 계획법
4. 문제를 단순화할 수 없을까?
   • 복잡한 문제를 단순한 문제로 바꿔서 해결한 후 복잡한 문제로 다시바꿔 해결한다.
   • ex) 2차원을 1차원으로 분해해서 생각
5. 문제를 분해할 수 있을까?
   • 분할 정복과 비슷한 의미로 큰 형태의 문제를 작은 형태의 의미로 쪼개서 해결한 후 큰 문제를 해결한다.
6. 뒤에서부터 생각해서 문제를 풀 수 있을까?
   • 문제에 내재된 순서를 반대로 뒤집어서 생각해보는 것이다. ex) 사다리 타기
7. 순서를 강제할 수 있을까?
   • 순서와 상관 없는 문제에서 순서를 생각하지 않으면 알고리즘이 복잡할 때가 많다. 이때 특정기준으로 알고리즘을 수행하는 과정에서 순서를 강제하면 편리하다.
   • ex) 2차원 행렬에서 왼쪽 위부터, 오른쪽 아래로 차례로 수행하기 등등
8. 특정 형태의 답만을 고려할 수 있을까?
   • 정규화(cononicalization) 기법이란 고려해야 할 답들 중 형태가 다르지만 결과적으로 똑같은 것들을 그룹으로 묶은 뒤 각 그룹의 대표들만 고려하는 방법이다.

 

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.