알고리즘 문제 해결 방법

1단계. 문제를 읽고 이해하기

---

2단계. 문제를 익숙한 용어로 재정의

문제를 추상화하여 재정의한다.

현실 세계의 개념을 다루기 쉬운 수학적 개념으로 옮겨 재정의한다.

어떻게, 어떤 부분을 추상화할 것인지에 따라 프로그램이 나아갈 방향이 정해진다.

---

3단계. 문제 해결 계획 세우기

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

• 3-1. 무식한 방법으로 풀 수 있을까? → 시공간 제약이 따른다면, 자료구조 개선 및 최적화 기법 적용하는 점직전인 개선
• 3-2. 내가 문제를 푸는 과정을 수식화할 수 있을까?
  • 예제 입력을 손으로 풀어본다.
  • 위 과정을 공식화·수식화 해본다.
  • 예제  : QUANTIZE, NUMB3RS, RESTORE, MATCHORDER, POTION, TRAPCARD
• 3-3. 문제를 단순화해볼 수 없을까?
  • 예제  :  ASYMTILING, DRAGON, LUNCHBOX, CHILDRENDAY, LAN
• 3-4. 그림으로 그려볼 수 있을까?
  • 예제  : STRJOIN, NERDS, NERD2
• 3-5. 수식으로 표현할 수 있을까?
  • 예제  : WITHDRAWAL
• 3-6. 문제를 분해할 수 있을까?
• 3-7. 뒤에서부터 생각해서 문제를 풀 수 있을까?
  • 예제 : INSERTION, GALLERY, SORTGAME
• 3-8. 순서를 강제할 수 있을까?
  • 예제  : BOARDCOVER, POLY, ZIMBABWE
• 3-9. 특정 형태의 답만을 고려할 수 있을까?
  • 특정 형태의 답만을 고려하는 정규화 기법
  • 예제  : PICNIC, WORDCHAIN
• 더 알고 싶다면, [어떻게 문제를 풀 것인가(How to Solve It)]을 읽어보자.

---

4단계. 계획 검증하기

프로그램으로 구현하기 전 3단계에서 설계한 알고리즘에서 빠진 예외는 없는지,

수행에 걸리는 시간과 사용하는 메모리가 적합한지 확인한다.

---

5단계. 프로그램으로 구현하기

코드로 구현한다.

---

6단계. 복기, 개선점 찾기

 

 

출처 : 구종만 선생님의 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 1권