코딩 테스트를 준비하면서 알고리즘을 체계적으로 풀기위해 도서 코딩인터뷰 완전 분석, 알고리즘 문제해결전략로 공부하면서 작성합니다. 계속 추가됩니다.
문제 해결과정
- 문제를 읽고 이해한다
- 문제를 익숙한 용어로 재정의 한다.
- 어떻게 해결할지 계획을 세운다.
- 계획을 검증한다.
- 프로그램으로 구현한다.
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
1단계: 문제를 읽고 이해하기
문제를 잘못 읽는 실수를 없애야 합니다. 문제를 대강 훑어보고 쉽사리 유추하는 실수를 해서는 안됩니다. 문제를 공격적으로 읽으며 문제가 요구하는 사항을 완전히 파악해야합니다.
2단계: 재정의와 추상화
문제를 자신의 언어로 풀어씁니다.
이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 반드시 거쳐야하는 단계입니다. 문제의 본질을 어떤식으로 재구성하느냐에 따라 어려운 문제를 쉽게 만들 수도, 쉬운 문제를 어렵게 만들 수도 있습니다.
3단계: 계획세우기
문제를 어떤식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택합니다.
4단계: 계획 검증하기
계획을 세웠다고 바로 구현하지 않고, 검증하는 과정을 거쳐야 합니다. 설계한 알고리즘이 요구조건을 정확히 수행하는지, 수행에 걸리는 시간과 메모리가 제한 내에 들어오는지를 확인합니다.
5단계: 계획 수행하기
프로그램을 작성합니다.
6단계: 회고하기
자신이 푼 문제를 돌이켜보고 개선하는 과정입니다. 좋은 방법은 문제를 어떤식으로 접근했는지 결정적인 방법은 무엇이었는지 코드와 함께 작성합니다. 반대로 해결하지 못했을 경우에는 오답원인을 적습니다. 회고의 또 좋은 방법은 다른 사람이 풀었던 코드 역시 확인하는 것 입니다.
문제를 풀지 못했을 때
너무 한 문제에 매달려 있는 것도 좋지 않습니다. 해결하지 못했다면 다른사람의 풀이방법을 참조한다는 원칙을 세우고 지켜야합니다. 단, 자신이 문제를 해결할 때 사용한 방법을 되새기고 왜 이 풀이를 떠올리지 못했는지 살펴봐야 합니다.
문제 해결 전략
직관과 체계적인 접근
문제 해결 전략에서에 가장 중요한 것은 직관 입니다. 하지만 직관이 처음부터 있다면 얼마나 좋을까요... 직관은 중요하지만 그냥 생기지는 않습니다. 직관을 얻을 수 있는 방법은 얼핏 보기에 막막한 문제를 해결하며 경험을 쌓아야 합니다. 그렇다면 막막한 문제는 어떻게 해결할까요?
막막한 문제의 해결방법 => 체계적으로 접근하자!
체계적인 접근을 위한 질문들
- 비슷한 문제를 풀어본 적 있는가?
- 단순한 방법에서 시작할 수 없을까?
- 내가 푸는 과정을 수식화 할 수 있을까?
- 문제를 단순화 시킬 수 없을까?
- 그림으로 그려볼 수 있을까?
- 수식으로 표현할 수 있을까?
- 문제를 분해할 수 있을까?
- 뒤에서 부터 생각해서 문제를 풀 수 있을까?
- 순서를 강제 할 수 있을까?
- 특정 형태의 답만 고려할 수 있을까?
