문제 해결 개관

책을 읽으면서 제가 이해한 방식으로 정리해봤습니다.

1. 도입

문제 해결 능력은 프로그래밍 언어나 알고리즘처럼 명확히 정의된 실체가 없는 추상적인 개념이기 때문에 단순한 반복만으로는 연마하기 어렵습니다.

좋은 문제 해결자가 되기 위해서는 좀더 높은 차원의 수련이 필요합니다. 이 수련의 목표는 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마하는 것입니다.

(21페이지 인용)

대부분의 사람이 알고있는 상식일 수도 있는 위의 글쓴이의 조언은 앞으로 6장부터 문제를 풀어나감에 있어서도 명심해야 할 것 같습니다.

저는 앞으로 스터디를 하면서 위의 내용을 잊지 않도록 이 게시물에 자주 방문할 것입니다.

2. 문제 해결 과정

이 책에서는 문제해결과정을 크게 6단계로 나누었습니다.

1. 문제를 읽고 이해하기

문제의 궁극적인 목적을 옳게 이해하는 것 부터, 사소한 제약 조건과 특수한 부분까지 놓치지 않는 능력이 필요하다고 합니다.

2. 재정의와 추상화하기

문제를 읽고 난 후, 스스로만의 혹은 팀원들만의 이해하기 쉬운 언어로 풀어 쓰는 것을 재정의라고합니다. 요구하는 바가 복잡한 문제일 수록 재정의를 하면 문제를 보다 직관적으로 이해할 수 있습니다.

재정의와 함께 문제를 추상화하는 것 또한 중요합니다. 추상화란 큰 덩치의 문제를 핵심부분만 남겨두고 축약하는 것입니다. 그렇게 하면, 우리가 풀어봤던 익숙한 문제들을 풀 때의 방법을 추상화된 문제에 적용할 수 있는 가능성이 생깁니다. 따라서 추상화를 어떤 방향으로 할지에 따라서 문제를 어떻게 풀지에 대한 방향을 정할 수 있습니다.

3. 계획 세우기

문제를 이해하고 재정의와 추상화를 완료했다면, 문제를 어떤 방식으로 해결할지 결정하고 어떤 알고리즘과 자료구조를 사용할지 결정해야합니다. 이 글의 3절 '문제 해결 전략'에서 계획을 세울 때 사용할 수 있는 여러 전략들을 다룰 것 입니다.

4. 계획 검증하기

계획을 세웠다면 그 계획을 검증하는 과정이 필요합니다. 사용하는 알고리즘과 자료구조가 문제가 요구하는 시간복잡도, 공간복잡도의 제한 내에 들어가는지 확인해야합니다. 문제를 힘들게 다 풀었으나 제한내에 걸려 처음단계로 돌아가는 일이 없도록 해야합니다.

5. 계획 수행하기

검증까지 완료했다면 코딩을 할 시간입니다 ! 계획한 알고리즘이나 자료구조가 코딩과정에서 구현을 하는 것 또한 중요합니다. 선택한 언어가 고안한 방법의 구현이 불가능하거나 굉장히 비효율적일 수도 있는 상황을 유의해야합니다.

6. 회고하기

문제 해결에 당장 직접적인 영향은 없지만 장기적으로 가장 큰 영향을 미치는 단계가 바로 회고입니다. (25페이지 인용)

일반적으로 같은 문제임에도 푸는 방법은 다양한 경우가 많습니다. 그래서 회고는 큰 의의를 가집니다. 처음에 해결한 방법보다 더 효율적인 알고리즘을 찾을 수도 있고, 좀 더 간결하고 이해하기 쉬운 코드를 작성할 수도 있습니다.

효과적으로 회고를 수행하는 가장 좋은 방법은 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것입니다.(26페이지 인용)

기록을 남길 때 특히 문제의 간단한 해법과 해법을 찾는데에 결정적 이였던 깨달음은 무엇 이였는지 기록하는 것이 포인트입니다.

또한 한번에 맞추지 못한 문제는 오답의 원인부터 답을 찾아가는 과정을 기록하는 것이 좋습니다.

회고를 위해서 같은 문제를 해결한 다른 사람의 코드를 보는 것도 좋습니다. 모든 사람의 코드는 조금씩 다 다를 수 밖에없습니다. 따라서 그 사람의 코드를 보며 또 다른 접근법과 풀이방법을 배울 수 있습니다.

회고를 통해 기록한 자료는 나중에도 틈틈이 볼 수 있기 때문에 최대한 직관적으로 기록하는 것이 좋습니다.

문제를 풀지 못할 때

일정한 시간이 지나도록 고민했음 에도 문제를 풀지 못했을 때는 다른 사람의 소스 코드나 풀이를 참조하는 것이 방법이 될 수 있습니다. 다른 사람의 소스 코드나 풀이를 참조할 때는 반드시 복기를 동반해야 합니다.

위의 단계의 구분을 하나하나 맞추어 따라갈 필요는 없습니다. 단계의 구분은 어디까지나 생각을 돕기 위한 도구입니다.

3. 문제 해결 전략

문제 해결 전략에 소개되어 있는 문제를 위에서 소개한 문제 해결 과정을 거쳐서 풀어보기

• 6.5 문제: 소풍 (155페이지)

  • step 1 문제를 읽고 이해하기 : 학생 이름과 학생들이 서로 친구인지에 대한 관계가 주어지면 학생들을 짝지을 수 있는 경우의 수를 계산해야한다.

  • step 2 문제를 재정의하고 추상화하기: 문제가 복잡하지 않아 패스하였다.

  • step 3 계획 세우기 : 조건에 의해 학생수가 많은 편이 아니여서 1초라는 시간은 촉박하지는 않다고 판단하였다. 따라서 비교적 느린 언어인 python으로도 가능할 것이라고 생각했다. input의 조건에 따르면 학생은 총 0~9 까지만 존재할 수 있다. 따라서 크기가 10인 1차원 배열을 만들 것이다. 그리고 학생들의 관계를 저장하기 위해 2차원 배열을 활용할 것이다. 경우에 수를 셀 때 재귀함수를 이용하여 점진적으로 세어 나갈 계획이다.

  • step 4 계획 검증하기 : 시간복잡도와 공간복잡도가 제한되어있지만 계획한 대로라면 충분 할 것 같다.

  • step 5 계획 수행하기 : problems repository에 추후 업로드 예정

  • step 6 회고하기 : 계획 수행하기 후 회고예정