////
Search
Duplicate
2️⃣

2. 문제 해결 개관

1. 도입

: 무작정 알고리즘을 외우고 문제를 푼다고 해서 문제 해결 실력이 쌓이는 것은 아니다. 명확히 정의된 실체가 없는 추상적인 개념이므로 단순한 반복만으로는 늘릴 수 없다.
: 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마하자. 이를 위해서는 내가 문제를 어떻게 해결하는지 의식하고 어느 부분이 부족한지 어떤 부분을 개선해야 하는지 파악해야 한다.
: 문제를 푸는 과정을 각 세분화해서 어떤 부분이 부족한지, 그리고 어떻게 개선할지 알아보자.

2. 문제 해결 과정

파인만 알고리즘
1.
칠판에 문제를 적는다.
2.
골똘히 생각한다.
3.
칠판에 답안을 적는다.
: 우스워 보이는 농담일지 몰라도 중요한 점이 하나 있다. 문제 해결 과정을 단계별로 나누었다는 것, 이를 통해 어떤 부분이 부족하고 개선해야 할지 판단할 수 있게 된다
어떻게 문제를 풀 것인가
1.
문제를 이해한다.
2.
어떻게 풀지 계획을 세운다.
3.
계획을 수행해서 문제를 해결한다.
4.
어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
: 파인만 알고리즘의 생각 단계를, 계획을 세우고 수행하는 2개의 단계로 나누었고, 문제를 푼 다음에도 개선할 방법을 찾는 회고 단계가 추가되었다.
: 이를 토대로 책에서 제시하는 여섯 단계 알고리즘은 다음과 같다.
프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘
1.
문제를 읽고 이해한다.
: 조급하게 행동하지 않고, 차분하게 문제를 이해하자. 문제가 원하는 바를 완전히 이해하는 과정이 필수적이다.
: 문제의 궁극적인 목적을 이해하더라도 사소한 제약 조건을 놓치면 풀 수 없게 되는 문제들도 많다. 꼼꼼히 잘 읽어보자.
2.
문제를 익숙한 용어로 재정의한다.
: 문제를 자신의 언어로 풀어쓰는 것이다. 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요하며 복잡할 수록 그 중요성이 더해진다.
: 또한 이 과정에서 문제의 추상화가 발생한다. 추상화란 현실의 개념을 수학, 전산학적으로 다루기 쉽게 본질들은 남겨두고 축약하여 다루기 쉽게하는 것이다.
: 추상화 과정에서 프로그래밍이 나아갈 방향을 결정한다고 볼 수 있다. 어떤 부분을 추상화할 것인지 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 좋은 프로그래머가 될 수 있게 도와준다.
3.
어떻게 해결할지 계획을 세운다.
: 문제 해결의 다음 단계는 어떻게 해결할지 계획을 세우는 것, 사용할 알고리즘과 자료구조를 선택한다.
4.
계획을 검증한다.
: 구현을 시작하기 전에 계획을 검증하는 과정을 거쳐야 한다.
: 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고 수행에 걸리는 시간과 메모리가 문제의 제한 내에 들어가는 지 확인해야 한다.
5.
프로그램으로 구현한다.
: 알고리즘을 설계했다면 구현하자. 구현이 부정확하거나 비효율적이면 프로그램은 정확히 동작할 수 없다.
6.
어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
: 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배울 수 없다.
: 두 번째로 문제를 접한다면 더 효율적인 알고리즘에 대해 고민해볼 수 있을 것이고 같은 알고리즘을 유도할 수 있는 어떠한 직관적인 흐름을 발견할 수도 있게된다.
문제를 풀지 못할 때
: 일정 시간이 지나도 문제를 해결하지 못할 때는, 다른 사람의 소스코드나 풀이를 참고하자.
: 단 다른 사람의 소스코드나 풀이를 참고할 때는 반드시 복기를 동반해야 한다. 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이를 떠올리지 못했는지 살펴봐야 한다는 것이다.