파인만 알고리즘
- 칠판에 문제를 적는다.
- 골똘히 생각한다
- 칠판에 답안을 적는다
문제 해결 과정을 단계별로 나누었다.(아주 중요하다)
문제를 적어보는 단계가 있다. 문제를 읽고 이해한 뒤 자신의 언어를 이용해 재정의 해야 하기 때문에 이 단계는 매우 중요하다.
문제 해결 과정(How to Solve It에서의 문제 해결 과정)
- 문제를 이해한다.
- 어떻게 풀지 계획을 세운다.
- 계획을 수행해서 문제를 해결한다
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
결론
- 문제를 읽고 이해한다.
- 사소한 제약 조건도 놓치거나 잘못 이해하면 안된다.
- 문제를 익숙한 용어로 재정의한다.
- 문제가 요구하는 바를 직관적으로 이해하기 위해 필요하다.
- 어떤 부분을 추상화할 것인지를 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 좋은 프로그래머가 되기 위해 필수적인 과정이다.
- 어떻게 해결할지 계획을 세운다.
- 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.
- 문제 해결에서 가장 중요한 단계이다.
- 계획을 검증한다.
- 구현을 시작하기 전에 계획을 검증한다.
- 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인한다.
- 프로그램으로 구현한다.
- 프로그램을 작성한다.
- 아무리 천재적인 알고리즘을 고안했더라도 구현이 부정확하거나 비효율적이면 프로그램은 정확히 동작할 수 없다.
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
- 자신이 문제를 해결한 과정을 돌이켜 보고 개선한다.
- 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 많다.
- 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남길 것
- 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지를 기록하면 좋다.
- 한 번에 맞추지 못한 경우에는 오답 원인도 꼭 적을 것
- 같은 문제를 해결한 다른 사람의 코드를 보는 것도 좋다.
문제를 풀지 못할 때
- 초보 시절에는 한 문제에 너무 매달려 있는 것도 좋지 않다.
- 일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 소스 코드나 풀이를 참조한다는 원칙을 세우고 이를 지키는 것이 좋다.
- 단, 다른 사람의 소스 코드나 풀이를 참조할 때는 반드시 복기를 동반해야 한다.
- 자신이 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이를 떠올리지 못했는지를 살펴봐야 한다.
문제 해결 전략
직관과 체계적인 접근
- 직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 해준다.
- 체계적인 방법은 백지에서부터 시작해 문제를 해결하기 위한 기반을 차근차근 쌓아올리면서 점진적으로 전진하는 것을 의미한다.
체계적인 접근을 위한 질문들
-
비슷한 문제를 풀어본 적이 있던가?
-
단순한 방법에서 시작할 수 없을까?
- 무식하게 풀 수 있을까? 라는 질문으로 시작
- 즉, 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 보는 것이다.
- 이 전략의 일차적 목표는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 예방한다.
- 컴퓨터는 사람보다 훨씬 빠르므로, 언뜻 우리가 느끼기에는 엄청나게 오래 걸릴 것 같은 일도 시간 안에 수행할 수 있는 경우가 많다.
- 이 방법이 유용한 진짜 이유는 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문이다.
- 효율적인 자료 구조를 사용하거나, 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선하는 식으로 문제를 해결할 수 있다.
- 단순한 방법은 알고리즘 효율성의 기준선을 정해주는 효과도 있다.
-
내가 문제를 푸는 과정을 수식화할 수 있을까?
- 손으로 여러 간단한 입력, 예를 들어 문제에 주어진 예제 입력을 직접 해결해 보면 좋다.
-
문제를 단순화할 수 없을까?
- 문제의 좀 더 쉬운 변형판을 먼저 풀어 보는 것이다.
- 문제를 쉽게 변형하는 방법은 여러 가지이다.
- 문제의 제약 조건을 없앨 수도 있고, 계산해야 하는 변수의 수를 줄일 수도 있으며, 다차원의 문제를 1차원으로 줄여서 표현할 수도 있다.
- 이때 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수도 있고, 이것을 직접적으로 이용해 원래 문제를 풀어낼 수도 있다.
-
그림으로 그려볼 수 있을까?
- 많은 사람들의 사고 체계는 숫자의 나열보다 기하학적 도형을 더 직관적으로 받아들이기 때문이다.
- 예를 들어 두 개의 정수 쌍들을 다루는 문제가 있다면, 이 정수 쌍을 2차원 평면 상의 좌표로 그려 볼 수도 있고, 직선 상의 구간들로 그려 볼수도 있다.
-
수식으로 표현할 수 있을까?
- 문장으로 쓰여 있는 문제를 수식으로 표현하는 것도 도움이 되는 경우가 있다.
-
문제를 분해할 수 있을까?
- 더 다루기 쉬운 형태로 문제를 변형하는 것
- 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽다.
-
뒤에서부터 생각해서 문제를 풀 수 있을까?
-
순서를 강제할 수 있을까?
- 순서가 없는 문제에 순서를 강제해서 문제를 푸는 방법
-
특정 형태의 답만을 고려할 수 있을까?
- 정규화(canonicalization) 기법
- 정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다.
출처
- 프로그래밍 대회에서 배우는 알고리즘 문제해결전략