Computer Science/Algorithm

[Algorithm] Algorithm 문제에 접근하는 방법

ooeunz 2019. 10. 19. 18:56
반응형

문제 해결 능력이란?

알고리즘 문제란 대개 '어떤 값을 읽어 들여 어떤 값을 계산하는 프로그램을 작성하시오.'와 같은 형태를 갖는다. 이러한 문제를 풀기 위해서는 프로그램이 사용할 수 있는 최대 메모리와 시간제한 등 다양한 제약 조건이 있다. 이러한 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력을 문제 해결 능력이라고 한다. 문제 해결 능력은 프로그래밍 언어나 알고리즘처럼 실체가 없는 추상적인 개념이다. 그래서 단순한 반복만으로는 능력을 향상시키는데에 어려움이 있다. 좋은 문제 해결자가 되기 위해서는 좀 더 높은 차원의 수련이 필요하다. 이를 위해서는 자신이 문제를 어떤 방식으로 해결하는지를 의식하고 어느 부분이 부족한지, 어떤 부분을 개선해야 할지 파악해야 한다.

 


문제 해결 과정

1. 문제를 읽고 이해한다.

2. 문제를 익숙한 용어로 재정의한다.

3. 어떻게 해결할지 계획을 세운다.

4. 계획을 검증한다.

5. 프로그램으로 구현한다.

6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

 

이러한 문제 해결 과정은 별 것 아닌 것 같지만 무엇하나 빼놓은 것 없이 중요한 것들이다.

 

1단계 : 문제를 읽고 이해하기

알고리즘을 처음 푸는 사람부터 노련한 프로그래머까지 모두가 공통으로 하는 실수가 있다면 바로 문제를 잘못 읽는 실수이다. 가능한 빠른 시간안에 문제를 풀어야 하는 상황에서 조급한 마음에 문제를 곁눈질한 뒤 딸려오는 그림과 입출력 예제를 보고 문제가 원하는 것을 유추하는 습관은 언젠가 큰 대가를 치르게 된다. 문제 설명을 공격적으로 읽고 문제가 원하는 바를 완전히 이해하는 과정이 반드시 필요하다. 궁극적으로 문제를 제대로 이해하더라도 사소한 제약 조건을 잘못 이해한다면 문제에서 틀릴 수도 있기 때문이다.

 

2단계 : 재정의와 추상화

문제를 이해했다면 두 번째로 문제가 요구하는 바를 직관적으로 이해하기 위해 문제를 자신의 언어로 풀어쓰는 단계가 필요하다. 

 

3단계 : 계획 세우기

문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.

 

4단계 : 계획 검증하기

계획을 세웠다고 해서 곧장 구현을 시작하는 것이 아니라 계획을 검증하는 과정이 필요하다. 이 과정에서 우리가 설계한 알고리즘이 모든 요구 조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간과 메모리가 문제의 제약 조건 안에 들어가는지 확인해야 한다.

 

5단계 : 계획 수행하기

계획이 검증되었다면 이제 프로그램을 작성한다.

 

6단계 : 회고하기

문제 해결에 장기적으로 가장 큰 영향을 미치는 단계가 바로 회고이다. 한번 푼 문제를 다시 본다고 해서 배우는게 있을까 생각할 수도 있지만, 오히려 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 더 많다. 효과적으로 회고를 수행하는 가장 좋은 방법은 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것이다. 문제의 간단한 해법과 어떤 방식으로 접근했는지, 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지를 함께 기록한다. 반대로 한번에 맞추지 못한 경우에는 오답 원인도 꼭 적는 것이 좋다.

 


문제 해결 전략

문제를 처음 보았을 때 대략적으로 어떤 형태를 가질지 가늠할 수 있다면 좋겠지만, 만약 막막한 문제를 만나게 된다면 어떡해야 할가? 이런 때에는 좀 더 체계적인 접근 방법이 필요하다. 아래에는 이러한 체계적인 접근을 위한 질문들의 나열이다.

 

비슷한 문제를 풀어본 적이 있던가?

무식하게 풀 수 있을까?

손으로 여러 간단한 입력들을 직접 해결해 볼까?

문제를 단순화할 수 없을까?

그림으로 그려볼 수 있을까?

수식으로 표현할 수 있을까?

문제를 분해할 수 있을까?

뒤에서부터 생각해서 문제를 풀 수 있을까?

순서가 없는 문제에 순서를 강제해서 문제를 풀 수 있을까?

특정 형태의 답만을 고려할 수 있을까?

 

반응형