알고리즘 문제 해결 전략 02 - 문제 해결 개관

문제 해결 과정

• 문제를 단계별로 나누는 것이 중요하다.
• 여섯 단계 문제 해결 알고리즘
  1. 문제를 읽고 이해하기
  2. 문제를 익숙한 용어로 재정의 하기 → 추상화(현실 세계의 개념을 우리가 다루기 쉬운 수학적/전산학적 개념으로 옮겨 표현하는 과정)
  3. 어떻게 해결할지 계획 세우기
  4. 계획을 검증하기
  5. 프로그램으로 구현하기
  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾기
     1. 회고의 방법으로는 오답 노트 기록이 있다.

문제 해결 전략

• 어려운 문제일수록 다양한 방법을 시도해봐야 한다.

직관과 체계적인 접근

• 직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 해준다.
  • 답안의 전체적인 얼개를 머릿속에 그릴 수 있다면 문제를 반쯤 해결한 것이나 마찬가지
  • 직관은 발달시키는 것은 결국 경험을 쌓는 것
• 막막한 문제는 어떻게 해결하나?
  • 체계적인 접근
    • 백지에서부터 시작해 문제를 해결하기 위한 기반을 차근차근 쌓아올리면서 점진적으로 접근하는 것

체계적인 접근을 위한 질문

비슷한 문제를 풀어본 적이 있었나?

• 단순히 많으 문제를 푼다고해서 그것이 다 경험이 되지는 않는다.
  • 그 원리를 완전히 이해하고 변형할 수 있어야 한다.
• 어떤 문제가 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 등의 분류하는 방법 익히기
• 각 알고리즘들이 어떤 경우에 사용될 수 있는지 체계적으로 공부

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

• -> 무식하게 풀 수 있을까?
  • 1차적 목표는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 예방하는 것
• 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문

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

• 손으로 문제를 풀어보는 습관
  • 손으로 주어진 예제 입력을 직접 해결해보기
  • 문제를 해결한 과정을 공식화해서 답을 만드는 알고리즘을 만들 수 있거나 그렇지 못해도 이 과정에서 알고리즘이 어떤 점을 고려해야 하는지를 알 수 있다.

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

• 주어진 문제의 좀 더 쉬운 변형판을 먼저 풀어보는 것
  • 제약 조건을 없애기
  • 계산해야 하는 변수 줄이기
  • 다차원 문제를 1차원으로 표현
• 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수도 있다.

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

• 사람의 사고 체계는 숫자의 나열보다 기하학적 도형을 더 직관적으로 받아들이기 때문에 문제와 관련된 그림을 그려보는 것은 도움이 된다.

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

• 평문으로 쓰여진 문제 → 수식으로 표현

문제를 분해할 수 있을까?

• 다루기 쉬운 형태로 문제를 분해
  • 예로 제약 조건을 분해하는 방법, 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해

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

• 문제에 내재된 순서를 바꾸는 방법
• 사다리 게임

순서를 강제할 수 있을까?

• 순서가 없는 문제에 순서를 강제해서 풀기

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

• 순서를 강제하는 기법의 연장선으로 정규화 기법이 있다.
• 정규화: 우리가 고려해야할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만 고려하는 방법