종만북 2단원 문제 해결 개관 내용 정리 2

안녕하세요 개발자 도도 입니다

종만북 1회독 해보기 두 번째 시간입니다 ㅎㅎ

 

2단원 내용 중 마무리 못 지은 나머지 부분을 정리해볼까 합니다 

시작해보겠습니다!

 

문제 해결 전략

---

직관과 체계적인 접근

 

사실 직관적으로 풀고자 하는 문제에 대한 해결 방법이 바로 떠오르는 직관이 있다면 따로 공부를 할 필요가 없겠지만,

대다수 그렇지 않은 경우에는 차근 차근 하나씩 공부를 해나가는 방법 밖에 없다고 합니다

그렇다면 풀 수 없는 문제들을 해결하기 위한 방법론을 하나 하나 살펴 보도록 하시죠

 

 

 

 

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

 

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

일반적으로 알고리즘 대회나, 코딩테스트 등에서 완전히 똑같은 문제가 나오는 경우는 거의 없다고 봐도 될 것 입니다

그래도 우리가 여러 종류의 알고리즘 문제를 풀어 보는 이유는 단지 그 문제를 푸는 것에서 그치는 것이 아닌, 그 문제를 풀기 위해 사용된 원리가 다른 문제에서도 동일하게 혹은 응용해서 사용될 수 있기 때문에 배우는 것이겠죠?

 

마찬가지로 종만북에서도 최단 거리 알고리즘에 대한 예시를 들며 이 문제가 최단 거리 알고리즘 문제인지, 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 분류 하는 방법과 각 알고리즘이 어느 경우에 사용해야 하는지 익혀야 한다는 게 필수라고 말씀 하시네요 

 

 

 

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

비슷한 문제를 풀어 본 적이 없는 문제라면 일단 단순한 방법에서 부터 시작을 해보는 방법을 택하는 것이 좋습니다

종만북에서는 우리의 생각보다 복잡하다고 생각되는 많은 알고리즘들이 단순한 방법에서 부터 점진적인 과정을 통해 나온 것들도 많다고 하네요

즉 시간복잡도나 공간복잡도를 고려 하지 않고 문제를 풀 수 있는 방법을 생각해본 후 거기서부터 점진적으로 최적화를 통해서 알고리즘 개선이 가능하다는 의미로  이해가 됩니다 (종만북에서의 예시는 사탕을 나눠주는 방법에 대해서 예시를 들었네요)

 

 

 

3) 문제 푸는 과정을 수식화 할 수 있을까?

점진적인 방법으로 풀 수 없는 경우는 주어진 문제의 답을 내는 과정을 손으로 일단 몇 가지 해보고 그것을 수식화 시켜서 하는 방법도 고려해볼 수 있습니다

 

 

 

4) 문제를 단순화 할 수 있을까?

문제를 단순화 하는 과정으로는 예를 들어, 제약조건을 없앨 수 도 있고, 계산해야하는 변수의 수를 줄이는 방법도 있을 수 있고, 다차원의 문제를 1차원의 문제로 해결하는 방법도 있을 수도 있습니다

(종만북에서 제시하는 예시는 x,y 격자 위에서 점들의 최소 거리가 되는 점의 위치 구하기 였습니다)

 

 

 

5) 그림으로 그려서 생각 할 수 있을까?

문제를 숫자의 나열 등으로 고려 해 볼 수 없는 상황이라면 오히려 도형의 연장선으로 생각하는 방법도 좋은 방법이라고 합니다

(종만북에서 제시하는 예시는 두 정수 쌍의 상황을 2차원 평면 상의 좌표로 고려할 수 도 있다는 것입니다)

 

 

 

 

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

평문으로 쓰여진 문제를 수식으로 표현하는 것도 도움이 되는 경우가 있다고 합니다 수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제를 해결하는데 도움을 줄 수 있기 때문이라는 군요

 

 

 

 

7) 문제를 분해 할 수 있을까?

또 다른 방법으로는 다루기 쉬운 문제 형태로 변형을 하는 것입니다

한 개의 복잡한 조건 보다, 여러 개의 단순한 조건이 낫다는 의미라고 하네요

(종만북에서의 예시는 운동 선수 기록에 대한 사실 확인 문제 등을 언급했습니다) 

 

 

 

 

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

문제에 내재된 순서를 역으로 생각하여 푸는 과정을 애기합니다

(종만북에서의 예시는 만일 사다리 타기 게임을 하게 될 경우 처음부터 시작해서 당첨에 나오는 방법을 고려하는 게 아니라, 반대로 당첨에서 부터 출발하여 시작점을 찾는 방법에 대해서 언급을 했습니다)

 

 

 

 

 

9) 순서를 강제할 수 있을까?

순서가 정해지지 않은 형태의 문제를 순서를 정함으로써 (순서를 임의로 정한다고 해도 문제의 의도와 방향이 달라지지 않으므로) 문제를 좀 더 쉽게 푸는 방법도 있다고 합니다

(종만북에서의 예시는 방의 전등을 켜는 문제의 해결책에 대해서 언급을 했습니다)

 

 

 

 

 

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

순서를 강제하는 방법의 연장선으로 정규화라는 방법에 대해서 제시를 했습니다

정규화의 경우 유용하지만 사용해야 할 정규화 기법이 문제마다 매우 달라 경험을 통하지 않으면 깨닫기 쉽지 않다고 언급하셨네요

(종만북에서의 예시는 점선 원을 모두 포함하는 원의 반지름 찾기 문제에 대해서 언급을 했습니다)

 

 

 

사실 2단원의 내용은 알고리즘의 문제를 풀기 위한 직접적인 알고리즘을 제시한 단원은 아니었습니다

이론적으로 알고리즘 문제를 풀기 위한 사고 과정에 대한 학습이며 문제를 푸는 방향에 대한 실질적인 해법이라기 보단 분석에 대한 초첨을 둔 단원이라고 생각이 되네요