[알고리즘 문제 해결 전략 #1] 2장 문제해결 개관

2.1 도입

2.2 문제 해결과정

    1. 문제를 읽고 이해하기

조급한 마음으로 문제를 곁눈질하고 그림과 입출력으로 유추하려는 행동은 최악의 결과를 초래한다.

문제를 옳게 이해하더라도 사소한 제약조건을 놓쳐 풀 수 없는 문제가 흔하고, 대회에서는 작은 실수도 용서하지않는다.

내가 부족한 부분이 문제를 차근히 읽고 이해하는 부분

    2. 재정의와 추상화

문제를 이해했다면 문제를 자신의 언어로 요약, 풀어쓰는 것이다. 추상화 과정을 통해 문제의 본질을 재구성하는 것은 문제를 쉽게 혹은 더욱 어렵게 만들기도한다. 따라서 어느부분을 추상화 할 것인지의 선택과 문제를 재정의 하는법을 고찰하는 것은 좋은 프로그래머의 필수 덕목이다.

    3. 계획 세우기

    4. 계획 검증하기

문제를 해결하기 위해서 계획과 검증을 하는부분.

2.3 에서 여러 전략을 소개한다.

    5. 계획 수행하기

구현하기

    6. 회고하기

한번만 문제를 풀어서 그 문제를 통해 배울 수 있는것을 다 배우지 못하는 경우가 많다. 여러번 문제를 풀 때는 효율적인 알고리즘 혹은 간결한 코드를 작성할 수 있고, 알고리즘 유도의 직관적인 방법을 찾을 수도 있다.

매번 문제를 풀때 어떠한 흐름으로 문제를 풀었는지 경험을 기록하는 것 방법이다. 이를 통해 문제들간의 공통적인 통찰과 배운내용을 되새기는데 유용하다.

못푼 문제의 오답 원인과, 다른 사람의 코드를 보는 것도 큰 도움이 된다.

    *. 문제를 풀지 못할 때

초반에 한 문제에 너무 매달리기 보다는, 다른 사람의 풀이를 참조해 문제를 복기하는 것도 방법이다.

    *. 주의

이 단계에 생각을 전개하라는 말이 아니고, 생각을 돕기위한 도구로 여겨야 한다. 경험이 많은 대회 참가자들은 이 과정을 생략하지도, 엄밀히 따라가지도 않는다. 경험을 통해 의식하지않고 수행하는 것이 중요하다.

 

2.3 문제 해결 전략

 

* 직관 : 경험을 통해 축적됨

* 체계적인 접근을 위한 질문들

    1. 비슷한 문제를 풀어본적 있는가?

비슷한 문제를 풀어본적 있다면 비슷한 접근 방법을 사용할 것이라는 예측으로 충분하다. 반드시 변형을 동반하기 때문에.

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

무식하게 풀 수 있을지 비용을 생각해 보면서 시도해볼만 하다. 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문임.

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

좀더 쉬운 변형판을 먼저 풀어보는 것, 문제의 제약조건을 제거하거나, 변수의 수를 줄인다거나 하는 쉬운 변형판은 전체 문제에 접근하기 쉽게 만들어준다.

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

기하학적으로 접근하는것이 숫자의 나열보다 더 직관적으로 받아들일 수 있다.

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

수식을 전개하거나 축약하는 순수한 수학적 조작이 문제를 해결하는데 큰 도움을 줄 수 있다.

   6. 문제를 분해할 수 있을까?

문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해하여 해석한다.

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

문제에 내재된 순서를 바꿔보는 것. 예를 들어 사다리 게임과 같이 목적지에서 부터 출발지로의 경로를 찾음으로 효율적인 접근이 가능하다.

    8. 순서를 강제할 수 있을까?

7번 접근의 연장선으로, 순서가 없는 문제에 순서를 강제하여 문제를 푸는 방법이다.

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

8번 접근의 연장선으로, 정규화 기법을 통해 접근한다. 여러개의 고려해야 할 정답들 중 형태는 다르지만 결과적으로 똑같은 것들을 그룹으로 묶은 뒤 각 그룹의 대표들만 고려하는 방법.

 

추상적으로 해결과정이나 접근 방법을 읽는 것만으로는 느낌이 오질않는다. 하지만 문제해결이 막힐때 참고할만은 할듯하다.