[Algorithmic Problem Solving Strategies] 문제 해결 독후감

Algorithmic Problem Solving Strategies

해당 책을 읽고 쓰는 독후감 또는 요약 정리본입니다.
주관적인 내용이 아주 많이 들어가 있습니다.

-
(독후감)

  사실 알고리즘이라는 분야 자체를 코딩테스트용으로만 생각하고, 무작정 많은 문제들을 풀어야한다. 라는 인식이 너무 강해서, 제대로 생각해본 적없이 매번 sv.ac에서 분류별로 나뉘어있는 카테고리를 몸으로 부딪혀가면서 풀어왔는데요.

  이 책을 읽으면서 알고리즘에 대한 개념적인 문제나 문제 해결에 대한 제 생각을 조금 고쳐 먹으려고 합니다.
생각과 행동이 좀 더 단단한 프로그래머가 될 수 있도록 노력하려고 합니다.

  사실 종만북 읽기를 몇 번이나 도전했었는데, 읽을 때마다 항상 필요한 부분만 읽고 너무 어렵다 하면서 내려놓기 일쑤였습니다.
해서 이번에는 책의 도입 부분부터 책의 좋은 부분을 정리해 가며 읽을 예정입니다. 

이번엔 끝까지 다 읽겠습니다.

아래는 지극히 주관적인 정리 내용본 입니다.

 

---

  알고리즘을 보는 관점에서 좋은 문제 해결자가 되기 위해서는 좀 더 높은 차원의 수련이 필요합니다. 이 수련의 목표는 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마하는 것입니다. 이를 위해서는 자신이 문제를 어떤 방식으로 해결하는지를 의식하고 어느 부분이 부족한지, 어떤 부분을 개선해야 할지 파악해야 합니다. 실력을 늘리기 위해서는 문제 풀이 과정을 여러 부분으로 나눠보고 각 과정을 자신이 잘하고 있는지, 그리고 잘하지 못하고 있다면 어떤 방향으로 개선해야 하는지 끊임없이 파악해야 합니다.

---

문제 해결 연구의 고전인 [How to Solve It]에서는 문제 해결 과정을 다음과 같이 네 단계로 나눌 수 있다.

1. 문제를 이해한다.
2. 어떻게 풀지 계획을 세운다.
3. 계획을 수행해서 문제를 해결한다.
4. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

이 책에서는 여섯 단계로 문제해결 알고리즘을 만든다.

1. Read and understand the problem.
2. Redefine the proble in familiar terms. (Redefine and abstract)
3. Make a plan for how to solve it.
4. Validate the plan.
5. Implement it in a program.
6. Reflect on how you solved the problem and look for ways to improve.

---

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

문제를 제대로 읽어라. 조급해서 입출력만 유추하면서 풀지 말고. 어제도 오픈콘테스트에서 제대로 안 읽어서 한 문제 틀렸다. 명심해라.

---

2단계: 재정의와 추상화

  자신이 다루기 쉬운 개념을 이용해서, 문제를 자신의 언어로 풀어쓰는 것. 이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요하며, 요구하는 바가 복잡한 문제일수록 그 중요성이 더해진다.

  이 과정에서 문제의 추상화라는 중요한 일이 일어난다. 추상화란 현실 세계의 개념을 우리가 다루기 쉬운 수학적 / 전산학적 개념으로 옮겨 표현하는 과정. 현실 세계의 개념들은 너무 복잡해서 현실세계를 다루기 위해서는 어느 정도 본질만 남겨두고 축약하여 다루기 쉽게 표현해야 한다. 이 과정을 추상화라고 부르며, 우리에게 익숙한 문제 해결 도구들을 문제에 적용할 수 있는 계기가 된다.

  문제의 본질을 어떤 방식으로 재구성하느냐에 따라 같은 일을 하는 프로그램이라도 전혀 다른 문제로 받아들여질 수 있다. 어려운 문제를 쉽게 만들 수도 있고, 쉽게 해결할 수 있는 문제를 오히려 어렵게 풀 수도 있다. 그러므로 실질적으로 추상화 과정이 프로그래밍이 나아갈 방향을 결정한다고 볼 수 있다. 어떤 부분을 추상화할 것인지를 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 좋은 프로그래머가 되기 위한 필수적인 과정이다.

---

3단계: 계획 세우기

문제를 어떻게 해결할지 계획을 세우는 것, 사용할 알고리즘과 자료구조를 선택하는 단계. 가장 중요한 단계이다. *2.3절에서 자세히 다룬다.

---

4단계: 계획 검증하기

  구현을 시작하기 전에 계획을 검증하는 과정을 거쳐야 한다. 우리가 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다. *4장, 5장에서 각각 알고리즘의 효율 분석 방법과 알고리즘의 정당성 증명에 관한 전략을 다룬다.

---

5단계: 계획 수행하기

  구현이 부정확하거나 비효율적이면 프로그램은 정확히 동작할 수 없다. *3장에서 유의할 점과 좋은 프로그램을 작성하기 위한 가이드라인을 다룬다.

---

6단계: 회고하기

  자신이 문제를 해결한 과정을 돌이켜 보고 개선하는 과정을 거쳐야 한다. 문제 해결 기술은 외워야 할 의사 코드도, 증명도 없는 추상적인 기술이기 때문에, 이들을 연마하기 위해서는 끊임없이 자신이 이 기술들을 어떻게 사용하고 있는지를 돌아보고 개선해야 한다. 

  효과적으로 회고를 수행하는 가장 좋은 방법은 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것. 이때 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음이 무엇이었는지를 기록. 또한 한 번에 맞추지 못한 경우에는 오답원인을 꼭 적는 것이 좋다. 

  회고를 위한 또 다른 좋은 방법은 같은 문제를 해결한 다른 사람의 코드를 보는 것. 

→ 블로그에 문제 풀고 나면 게시하기로 했는데 안 함. 앞으로 꾸준히 해야 한다. 템플릿을 정하고 맞춰서 작성하기. 요즘 시간 없다고 계속 쉬운 문제 알던 문제들만 계속해서 푸는데, 회고도 못하고 있고.. 독이 되는 것 같다.

---

문제가 풀리지 않을 때.

  문제를 직접 풀기 전에는 절대 답안을 참조하지 말라는 말도 있지만, 너무 한 문제에 매달려 있는 것도 좋지 않다. 일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 소스 코드나 풀이를 참조한다는 원칙을 세우고 이를 지킨다.

단! 다른 사람의 소스 코드나 풀이를 참조할 때는 반드시 복기를 동반해야 한다. 자신이 문제를 해결할 때 취했던 접근들을 되새겨보고 자신이 왜 이 풀이를 떠올리지 못했는지를 살펴봐야 한다는 뜻. 처음 보는 기술이나 접근을 한 번만에 자신의 것으로 하기란 힘들지만 두 번, 세 번 해당 기법을 이용한 문제를 풀다 보면 비슷한 문제를 봤을 때 해당 기법이 떠오르는 때가 올 것이다.

---

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

• 비슷한 문제를 풀어본 적이 있던가 ?
  • 형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면 이전에 적용했던 방법과 비슷한 방법을 사용할 거라고 예측 가능
  • 풀어 본 문제와 완전히 같은 문제가 있을 확률이 거의 없기 때문
  • 기존에 접했던 문제가 온전히 경험이 되려면 그 원리를 완전히 이해하고 변형할 수 있어야 한다.

 

• 단순한 방법에서 시작할 수 있을까?
  • 비슷한 문제를 본 적 없거나, 비슷한 문제의 해법이 곧장 적용되지 않는다면 무식하게 풀 수 있을까? 라는 질문으로 시작
  • 일단 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어보는 것.
  • 일단 단순하게 시작하고 그 이후 좀 더 효율적인 자료구조를 사용하거나, 최적화하여 알고리즘을 개선하는 식으로 문제 풀이가능.
  • 점진적 개선을 통해 문제를 풀 수 없더라도 단순한 방법을 생각해 보는 데는 나름의 의미가 있다.
  • 알고리즘 효율의 기준이 정해져서, 새로운 알고리즘이 그에 비해 얼마나 개선되었는지 재는 용도로 유용하게 쓰이기도 한다.

 

• 내가 문제를 푸는 과정을 수식화할 수 있을까 ?
  • 손으로 문제를 풀어봐라. 그러면 어떻게 문제를 풀어야 할지 감이 올 때도 있다.
  • 자신이 문제를 해결한 과정을 공식화해서 답을 만드는 알고리즘을 만들 수 있는 경우가 흔히 있다.
  • 그렇지 못한 과정에서도 알고리즘이 어떤 점을 고려해야 하는지를 알게 되기 때문

 

• 문제를 단순화할 수 없을까 ?
  • 주어진 문제의 좀 더 쉬운 변형판을 먼저 풀어보는 것. 
  • 문제를 쉽게 변형하는 방법. 이때, 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수 있다.
    1. 문제의 제약조건을 없앤다.
    2. 계산해야 하는 변수의 수를 줄인다.
    3. 다차원의 문제를 1차원으로 줄여서 표현해 본다.
  • 직관을 직접적으로 이용해 원래 문제를 풀어낼 수도 있다.

 

• 문제를 분해할 수 있을까 ?
  • 더 다루기 쉬운 형태로 문제를 변형하는 것.
    • 문제의 제약 조건을 분해하는 방법
    • 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해
    • 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문

 

• 뒤에서부터 생각해서 문제를 풀 수 있을까 ?
  • 출발지에서 목적지까지의 길이 여러 개라면 출발지를 모두 선택해서 목적지로 가는 것보다는 목적지에서 거꾸로 생각해서 출발지를 찾는 것이 더 쉬운 방법이다.
  • A에서 B로가는 방법을 찾긴 어렵지만 B에서 A로 가는 방법을 찾기는 쉽다. 

 

• 순서를 강제할 수 있을까 ?
  • 순서가 없는 문제에 순서를 강제해 문제를 푸는 방법도 있다.
  • 순서 강제 기법은 경우의 수를 셀 때도 유용하다. 특정 조건을 만족하는 답들의 수를 세는 문제를 흔히 볼 수 있는데, 이때 까다로운 것은 한 가지 답을 두 가지 이상의 방법으로 만들 수 있을 때 이 답들을 중복하여 세는 경우.
  • 대부분의 경우 답을 만들기 위해 할 수 있는 일들의 순서를 강제하는 것이 좋은 해법이 된다.

 

• 특정 형태의 답만을 고려할 수 있을까 ?
  • 순서 강제 기법의 연장선으로 정규화(canonicalization) 기법이 있다.
  • 정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 것.
  • 정규화 기법은 아주 유용하지만 사용해야 할 정규화 기법이 문제마다 매우 달라 많이 경험하지 않으면 깨닫기 쉽지 않다.

 

---

 

알고리즘 문제 해결 전략