[Gain_Study_종만북]01. 문제해결 시작하기

📌 목차

1. 문제해결과정
2. 문제해결전략

 

코딩테스트는 명시적인 시간제한과 메모리 제한이 존재하기 때문에 "적절한 알고리즘과 자료구조"를 사용하지 않으면 시간 제한 내에 동작할 수 없다.

 

따라서 오늘부터 이를 위한 적절한 알고리즘과 이를 통한 문제해결 방법에 대해 가장 유명한 "알고리즘 문제해결전략(종만북)"으로 공부를 시작하려한다. cf) 자료구조 with C++ https://chan4im.tistory.com/category/C%20%7C%20C%2B%2B/Data%20Structure%20%26%20STL

'C | C++/Data Structure & STL' 카테고리의 글 목록

 

 

 

 

 

 

 

---

1. 문제해결과정

1. 문제 이해
말 그대로 문제를 읽고 이해하는 과정.
이때, 문제를 잘못읽거나 잘못 이해하는 등의 실수가 나오지 않게 유의해야함

2. 재정의  &  추상화
익숙한 용어로 문제를 재정의 하는 과정.
(재정의). 문제를 자신의 언어로 풀어쓰고
(추상화). 현실세계의 개념 → 다루기 쉬운 수학적/전산학적 개념
즉, 최종적으로 본질만을 남겨두고 축약해 다루기 쉽게 만드는 것.

3. 계획 수립(🌟)
어떤 방식으로 해결할 것인지 계획을 세우는 과정.
사용할 알고리즘과 자료구조를 선택하는 가장 중요한 단계

4. 계획 검증
세운 계획을 검증하는 과정.
설계한 알고리즘이 요구조건 및 Cost를 만족하는지 알고리즘의 정당성을 "증명"

5. 계획 수행
프로그램으로 구현하는 과정. (https://chan4im.tistory.com/207)

6. 회고
어떻게 풀었는지 돌아보고, 개선할 점을 찾는 과정.
장기적으로 가장 큰 영향을 미치는 단계로 자신이 문제를 해결한 과정을 돌이켜보고 개선하는 과정.

효과적인 회고방법
∙ 코드와 함께 자신의 경험을 기록으로 남기는 것
∙ 어떤 방식으로 접근했는지, 가장 결정적인 깨달음은 무엇이었는지.
∙ 한번에 못맞춘 경우, 오답 원인은 무엇이었는지.

 

주의할 점
다만, 문제를 풀 때 항상 이 단계에 매몰되어 하나하나 모든 과정을 맞춰가며 생각을 전개할 필요성은 없다.
단계의 구분은 어디까지나 생각을 돕기위한 일종의 Tool의 역할을 한다.
즉, 경험이 쌓임에 따라 이 과정들을 따로 의식하지 않아도 수행할 수 있기 때문에 이 단계에 소개한 작업들을완전히 생략하지도 않는다.

 

 

 

 

 

 

 

 

 

 

 

 

 

---

2. 문제해결전략

어려운 문제일수록 다양한 방법을 시도해 보면서 답안을 찾아야한다.

이에 대해 어떤 방식으로 접근하면 좋을지에 대해 소개해보고자 한다.

 

직관  &  체계적인 접근
직관의 중요성)
∙ 직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작케 해준다.
∙ 즉, 답안의 전체적인 구조를 머릿속으로 구성하는 방법이다.
∙ 시간이 지나면서 발달하기에 경험을 쌓는 것이 중요하다.


체계적인 접근)
∙ 체계적인 접근은 문제해결의 좋은 시작점역할을 하며 막막한 문제에 접근할 수 있는 여러 방법을 제공한다.

 

 

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

아래 질문들은 많은 문제에 적용될 수 있으며,

위로 갈수록 강력한 질문들로, 아래로 갈수록 사용이 제한적인 순으로 배열되어 있다.

∙ 유사문제를 풀어본 적 있었는가?
∙ 단순한 방법에서 시작할 수 있을까?
∙ 문제를 푸는과정을 수식화할 수 있을까?
∙ 문제를 단순화할 수는 없을까?
∙ 그림으로 그려볼 수 있을까? 
∙ 수식으로 표현할 수 있을까?
∙ 문제를 분해할 수 있을까? 
∙ 뒤에서부터 생각해서 문제를 풀 수 있을까?
∙ 순서를 강제할 수 있을까?
∙ 특정형태의 답만을 고려할 수 있을까?

 

유사문제를 풀어본 적 있었는가?
형태가 비슷하거나 관련문제를 풀어본 적이 있다면, 비슷한 접근법을 사용할 것이라 예측가능하다.
예를 들어 아래 예시를 보자.

∙ 한 도시를 2번 방문하지 않으면서 가장 긴 경로를 찾는 문제
∙ 기차를 4번 이하로 갈아타면서 가장 짧은 경로를 찾는 문제
∙ 역 간 운행거리 중 가장 긴 구간이 가장 짧은 경로를 찾는 문제
∙ 역 간 운행거리 중 가장 짧은 구간이 가장 긴 경로를 찾는 문제
∙ 가장 긴 구간과 가장 짧은 구간의 길이차가 가장 적은 경로를 찾는 문제

이 예시들의 경우, 최단경로문제를 응용해 풀 수 있는 것도 있고, 없는 것도 있다.
따라서 이들을 구분하기 위해서는 알고리즘을 단순히 알고있어서는 안된다.
"알고리즘의 동작과정과 원리를 완전히 이해"하는 것이 중요하다.

꼭 형태가 비슷하지 않더라도 문제의 목표가 같은 경우도 이 사례에 속한다.
예를 들어, 어떤 사건의 발생확률이나 경우의 수를 계산하는 문제들은 십중팔구로 DP로 해결가능하다.

 

단순한 방법에서 시작할 수 있을까?
비슷한 문제를 본 적 없거나 해법이 적용되지 않는다면, 문제해결을 위해서 어떻게 시작해야할까?
이 책에서 소개되는 많은 문제풀이방법은 "무식하게 풀 수 있을까?"라는 질문에서 시작된다.
즉, Cost를 고려하지 않고 문제해결을 위한 가장단순한 알고리즘을 만드는 것을 목표로 한다.
따라서 어려운 문제를 접했을 때, 한 번쯤 시도해볼 만하다. (∵ 알고리즘 효율성의 기준선을 정하기 때문.)

보통 완전탐색(Exhaustive Search; Brute Force Search)로 모든 문제를 거의 풀 수 있지만,
조금 더 제한을 생각해 내면 DFS, BFS등의 알고리즘 점진적으로 알고리즘들을 생각하며 문제를 해결할 수 있다.

 

문제를 푸는과정을 수식화할 수 있을까?
물론, 점진적인 접근방식이 만능은 아니다.
기존과는 완전히 새로운 방향에서 접근해야 풀리는 문제들도 존재하기 때문이다.
이때, 자신이 문제를 해결한 과정을 공식화해 답을 만드는 알고리즘을 만들 수 있는 경우가 흔히 있다.

 

문제를 단순화할 수는 없을까?
아래 방법처럼 문제의 좀 더 쉬운 변형판을 만들어 단순화한 뒤, 이를 먼저 풀어보는 것이다.
∙ 변수의 수를 줄이거나
∙ 다차원을 1차원으로 줄이는 등 
이때 단순화된 문제의 해법이 기존 문제의 해법에 대한 직관이나 기존 문제에 대한 해결을 이끌어낼 수도 있다.

 

그림으로 그려볼 수 있을까?
문제의 해법에 대한 직관을 얻을 수 있는 또 다른 방법으로 기하학적 도형을 대부분 더 잘 받아들이기 때문이다.
이는 기하학을 다루는 문제에만 국한되지 않으며, 좌표로도 그려볼 수 있고, 이해를 위한 tool로써 사용될 수도 있다.
다만, 이 접근방식이 항상 통하지는 않으나 문제해결을 위한 결정적인 직관을 얻는 경우도 존재한다.

 

수식으로 표현할 수 있을까?
가능한 한 직관을 얻기 좋은 방향으로 사고를 전개하는 다른 접근 방식과는 반대로,
평문으로 적힌 문제를 수식으로 표현하는 것 또한 도움이 되는 경우가 존재한다.
수식으로 전개, 축약하는 과정은 순수 수학적 조작이 문제를 해결하는데 도움을 줄 수 있기 때문이다.

 

문제를 분해할 수 있을까?
또 다른 중요한 접근 방식은 더 다루기 쉬운 형태로 문제를 변형하는 것이다.
가장 대표적인 예시로 "문제의 제약조건을 분해"하는 방법이다.

 

뒤에서부터 생각해서 문제를 풀 수 있을까?
문제에 내재된 순서를 바꿔보는 것으로, 이 기법을 사용할 수 있는 가장 대표적 예시가 바로 사다리타기 게임이다.
예를 들어 A,B,C,D라는 사람들이 있고, 1,2,3,4위에 대해 사다리 타기를 아래와 같이 진행했다 하자.

이때, 가장 빠르게 1위인 사람을 알아내려면 당연히 거꾸로 올라가는 것이 가장 빠르다.

즉, A→B는 어렵지만, B→A로 가는 방법은 찾기 쉬운 문제들이 존재한다.

 

순서를 강제할 수 있을까?
순서가 없는 문제에 순서를 강제해 문제를 푸는 방법이다.
이 방법은 특정 순서라는 제약을 추가하지만, 답이 변하지는 않기에 제약은 단순히 우리의 사고를 도와주는 tool로써의 역할만 한다.

 

특정형태의 답만을 고려할 수 있을까?
순서를 강제하는 기법의 연장선인 정규화(canonicalization)기법은 고려해야할 답들 중 형태는 다르나 결과적으로는 똑같은 것들을 그룹으로 묶고, 각 그룹의 대표들만을 고려하는 방법이다.

정규화기법은 아주 유용하나 문제마다 사용해야되는 정규화기법이 매우 달라, 경험을 통하지 않으면 깨닫기 쉽지 않다.