모종닷컴

문제 해결 전략 질문들 본문

3학년/알고리즘

문제 해결 전략 질문들

모종 2018. 11. 16. 09:11
반응형

1.비슷한 문제를 풀어본 적이 있던가?



형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면 이전에 적용했던 방법과 비슷한 접근 방법을 사용할 거라고 예측할 수 있다. 따라서 기존에 접했던 문제가 온전히 경험이 되기 위해 그 원리를 완전히 이해하고 변형할 수 있어야 한다. 


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



비슷한 문제를 본 적이 없거나, 비슷한 문제의 해법이 곧장 적용되지 않는다면 "무식하게 풀 수 있을까?"라는 질문으로 시작한다. 이렇게 만든 단순한 알고리즘에 효율적인 자료 구조를 사용하거나, 계산 과정에서 같은 정보를 두 번 중복으로 계산하지 않는 등의 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선하는 식으로 문제를 풀 수 있다.


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



손으로 간단한 입력, 예를 들어 문제에 주어진 예제 입력을 직접 해결해보는 것. 자신이 문제를 해결한 과정을 공식화해서 답을 만드는 알고리즘을 만들 수 있는 경우가 흔히 있고, 그렇지 못하더라도 이 과정에서 알고리즘이 어떤 점을 고려해야 하는지를 알게 된다.


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



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


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



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


6.문제를 분해할 수 있을까?



문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해한다. 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문에 이 변형은 종종 유용하다. 


7.순서를 강제할 수 있을까?



순서를 뒤집는 방법의 연장선으로, 순서가 없는 문제에 순서를 강제해서 문제를 푸는 방법도 있다. 순서 강제 기법은 경우의 수를 셀 때도 유용하다. 특정 조건을 만족하는 답들의 수를 세는 문제를 흔히 볼 수 잇는데, 이때 까다로운 것은 한 가지 답을 두 가지 이상의 방법으로 만들 수 있을 때 이답들을 중복하여 세는 경우다. 



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



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




반응형

'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15