프로그래밍 문제풀이과정 분석하기

종만북의 문제해결개관 파트를 읽고 문제풀이시에 실천하기 위해 정리하였습니다.

코딩테스트 또는 프로그래밍 대회의 문제를 잘 풀기 위해 필요한 능력은 알고리즘 & 자료구조 & 사용하는 컴퓨터 언어의 문법과 특징 등에 대한 배경지식, 자신이 아는 것을 이용해 문제를 풀어내는 문제해결능력, 생각해낸 문제해결방법을 정확히 구현해내는 구현력이다.

문제해결능력을 키우기 위해서는 문제를 많이 풀어보아야 한다. 하지만 막연한 시도를 반복하는 것만으로는 부족하다. 문제를 푸는 방식을 연마하기 위해  자신이 문제를 어떻게 풀고 있는지, 어떤 방향으로 개선해야하는지 끊임없이 파악해야한다. 

아래와 같이 문제를 푸는 과정을 여러 부분으로 나눠보고 각 과정을 자신이 잘하고 있는지, 어떤 방향으로 개선해야하는지 알아보자. 

1. 문제 이해하기

문제를 읽고 이해한다. 작은 제약 조건을 잘 못 이해하면 풀 수 없는 문제들이 많다.

2. 자신의 언어로 재정의/추상화

자신이 익숙한 말, 도표 등으로 문제를 재정의/추상화 해본다. 추상화란 복잡한 현실의 개념을 본질만을 남겨두고 축약하는 것을 말한다. 특히 문제의 내용이 복잡할수록, 추상화과정을 잘해놓으면 문제해결계획을 세워야할지 실마리를 잡을 수 있기 때문에 중요하다.

3. 계획세우기

문제를 어떻게 해결할지 결정하고, 어떤 알고리즘, 자료구조을 사용할지 정한다.

- 어떤 문제가 최적화 문제인지, 경우의 수 문제인지, 검색문제인지 문제유형을 구분하는 방법을 익힌다. 이를 구분할 수 있다면 이전에 풀어본 같은 유형의 문제해결방법을 활용할 수 있을 것이다.

- 해결방법을 모르겠다면, 무식하게 풀 수 있을까?에서 부터 시작한다. 단순한 방법(brute-force)에 효율적인 자료구조와 중복 연산을 없애는 등 점진적인 개선으로 풀 수 있는 문제도 꽤 많다. 그렇게 풀 수 없는 문제더라도 알고리즘 효율성이 얼마나 개선되었는지에 대한 기준선이 될 수 있기 때문에 여전히 단순한 방법은 유용하다.

- 손으로 문제를 풀어봅니다. 평문으로 쓰인 문제를 수학적 수식으로 만들어 풀어봐도 좋고, 그게 아니더라도 손으로 문제를 풀어보는 것은 도움이 된다. 어떻게 문제를 풀어야하는지 감이 올 때라면, 코드를 작성하기 이전에 자신의 알고리즘이 간과한 점이 없는지 확인할 수 있음으로 유용하다. 그게 아니라, 영감이 필요할 때라도 손으로 문제를 먼저 풀어보고 문제해결과정을 수식화해서 알고리즘을 만들 수 있다.

- 단순화된 버전의 문제를 풀어본 후, 그 해결방법을 참고하여 본래의 문제를 푼다. 문제를 단순화하기 위해 문제 제약조건 없애거나 다차원의 문제를 1차원으로 줄이는 등의 시도를 해볼 수 있다.

- 대부분의 사람들의 경우 숫자가 나열된 것 보다 기하학적으로 표현된 쪽을 쉽게 받아들인다. 문제에 나오는 숫자들을 그래프 등을 통해 그림으로 표현해보자.

- 좀 더 다루기 쉬운 형태로 문제를 분해해본다. 복잡한 제약조건을 분해해 여러개의 단순한 제약조건으로 만드는 편이 더 문제를 쉽게 해결하게 해준다.

- 사다리 타기에서 당첨에서 부터 거슬러 올라가는게 당첨되기 위해 선택해야하는 사다리 입구를 찾는 가장 빠른 방법인 것 처럼, 문제에 내재된 순서를 바꾸면 쉽게 해결할 수 있는 문제들이 있다.

- 순서가 없는 문제에 순서를 강제해본다.

- 답이 여러개 있는 경우, 한가지 형태로 정규화canonicalization해본다.

4. 계획검증

- 모든 요구조건 정확히 수행하는지 증명하기.

- 시간, 메모리 효율성 분석.

- 특히, 제한 시간 내에 수행할 수 있는지 확인.

5. 계획수행

- 코딩 

- 코드를 빨리짜기보다는 읽기 쉽게 작성한다.

- 코드를 모듈화하기. 같은 코드가 3번 이상 등장한다면 함수가 클래스로 분리해서 사용한다.

- 기초적인 알고리즘들을 직접 작성하지말고, 표준라이브러리를 활용하라.

- 같은 기능이라면 항상 같은 형태로 프로그램을 작성하라. 

- 변수, 함수 등의 이름을 명료하게 지어라. 모호하지 않은 이름을 짓는 버릇을 들이고, 사용하는 언어의 표준 라이브러리에서 사용하는 명명 규약을 익혀라.

- 데이터를 정규화해서 저장하라. 같은 스케일 안에서 규칙을 따르도록 한다.

- 코드의 논리와 상관없는 데이터는 분리하라.

  - 디버깅

6. 회고하기

자신의 문제해결능력을 향상시키기 위해, 회고는 자신이 문제를 어떻게 풀었는지 돌아보고 개선방법을 찾는 과정이다.

1. 문제 풀때마다 코드와 자신의 경험을 기록한다.

- 답으로 작성한 코드

- 간단한 해법 

- 자신의 접근 방식

- 해법을 찾는데 결정적이었던 깨달음 

- 해결하지 못한 경우 오답원인 

2. 한번 푼 문제를 여러번 다시 푼다. 다시 풀 때는 좀 더 효율적인 알고리즘을 찾거나, 코드를 더 간결하게 만들 수도 있다.

3. 같은 문제를 푼 다른 사람의 코드를 본다. 같은 문제에 대한 다른 문제풀이방식을 보고 통찰력을 얻을 수 있다.