[종만북] 02. 문제 해결 전략

문제 해결 과정

• 문제를 읽고 이해한다.

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

• 어떻게 풀지 계획을 세운다.

• 계획을 검증한다.

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

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

1) 문제를 읽고 이해하기

문제를 잘못 읽는 실수를 범하지 않도록, 문제를 공격적으로 읽으면서 문제가 원하는 바를 완전히 이해하려는 노력이 필요하다. 사소한 제약 조건을 놓치게 되는 경우 풀 수 없게 되는 경우도 많으며, 대회에서는 작은 실수도 용납하지 않는 경우가 대부분이기 때문이다.

2) 재정의와 추상화

자신이 다루기 쉬운 개념을 사용하여, 문제를 자신의 언어로 풀어쓰는 것, 문제가 요구하는 바를 직관적으로 이해하기 위해서 필요한 과정이며 복잡한 과정일수록 더욱 중요하다. 문제의 본질을 어떤 방식으로 재구성하느냐에 따라서 같은 일을 하는 프로그램이라도 전혀 다르게 받아들여질 수 있다. 어려운 문제를 쉽게, 쉬운 문제를 어렵게 풀 수 있기 때문에 추상화가 프로그램이 나아갈 방향을 결정한다고 볼 수 있음

추상화: 현실세계의 개념을 우리가 다루기 쉬운 수학적 / 전산학적 개념으로 옮겨 표현하는 과정

3) 계획 세우기

문제를 어떤 식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택하는 과정. 가장 중요한 과정이라고 할 수 있으며, 문제를 보고 바로 해결 방법이 떠오르지 않는 경우, 이 과정에서 가장 많은 고민을 하게 됨.

4) 계획 검증하기

구현을 시작하기 전에 계획을 검증하는 단계를 거쳐야 함. 이 과정에서 우리가 설계한 알고리즘이 모든 경우에 대해 요구 조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다.

5) 계획 수행하기

구현에 있어서는 효율성과 정확성을 항상 챙길 것.

6) 회고하기

당장 직접적인 영향은 없지만 장기적으로 가장 큰 영향을 미치는 단계. 한 번 풀어봤던 문제를 다시 풀어보는 경우에 더 효율적인 알고리즘을 찾거나 간결한 코드의 작성이 가능해지기도 하며, 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾아낼 수도 있다. 효과적으로 회고를 수행하는 방법으로는 문제를 풀 때마다 자신의 경험을 기록으로 남기는 것이 제일 유효하다고 본다.

접근 방식, 결정적인 깨달음, 오답 원인 등을 기록하는 것으로 실수를 줄이고 패턴화에 도움을 줄 수 있기도 함. 해결한 다른 사람의 코드를 확인하는 것으로 생각치 못했던 통찰을 얻을 수도 있음

해결하지 못했을 경우에도 일정 시간이 지나면 다른 사람의 코드나 풀이를 참조하되 반드시 복기를 동반할 것

문제 해결 전략

1) 직관과 체계적인 접근

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

  • 단순하게 풀어본 경험이 아닌 원리의 이해와 변형이 가능해야 한다.

• 단순한 방법에서 시작할 수 있을까?

  • 무식하게 풀 수 있을까? 에서 시작하는 가장 단순한 알고리즘을 만들고 최적화를 통해 구현하는 방식도 존재

  • 알고리즘 효율성의 기준선을 정할 수 있음

• 내가 문제를 푸는 과정을 수식화할 수 있을까?

  • 문제에 주어진 예제 등을 해결하면서 공식화

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

  • 주어진 문제의 좀 더 쉬운 변형판을 먼저 풀어보는 것

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

  • 기하학적 도형이 더 직관적으로 받아들이기 좋음

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

  • 평문 → 수식이 문제를 해결하는 데에 도움을 줄 수 있음

• 문제를 분해할 수 있을까?

  • 더 다루기 쉬운 형태로 문제를 변형하는 방법 중에서 제약 조건을 분해하는 방식

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

  • 전형적인 예시: 사다리 게임

  • 앞에서 모든 경로를 시도하는 것보다 도착지에서부터 역으로 타고 올라가는 것으로 횟수 줄이기 가능

• 순서를 강제할 수 있을까?

  • 순서가 없는 문제에 순서를 강제하는 방식

  • 예시: 하나의 변수에 대해 변형을 하거나, 하지 않거나 2가지 경우만 존재 / 순서가 상관이 없음 → 순서대로 변형할지 말지만 결정하는 케이스

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

  • 정규화 기법

  • 여러 가지 답들 중 형태가 다르지만 결과적으로는 동일한 것들을 그룹으로 묶고, 그룹 대표들만을 고려하는 방법