[코테준비] 전체탐색으로 문제를 해결하자 - 1

들어가기에 앞서

 단순히 문제를 많이 풀고 이를 통해 얻어진 내공으로 직관적으로 문제를 푸는 것은 한계가 있다. 알고리즘을 본격적으로 공부한지 7일차가 되는 오늘 내가 느낀 것은 바로 이것이다. 

 

'알고리즘은 수학문제 풀이와 사고과정이 비슷하다'

 

특히 수능 30번,21번 문제를 푸는 사고과정과 닮아있음을 체감하였다. 

여담이지만, 알고리즘(코딩테스트) 은 '정시' 와 닮았고 포트폴리오(프로젝트)는 '수시 스펙'과 닮은 것 같다. 

 

전체탐색으로 문제를 풀어보자

 

시뮬레이션

 보통 시뮬레이션 문제는 특징이 다음과 같다. 

• 문제에서 주어진 처리를 수행하기만 하면 되는 간단한 내용이 주를 이룬다
• "이런 과정을 거쳐서 나온 결과가 무엇인가?" 라고 물어보는 문제가 많다. 

전체탐색 vs 시뮬레이션

• 시뮬레이션 : 수행해야 하는 과정이 모두 나와있는 문제
• 전체탐색 : 모든 패턴을 조사해야 하는 것과 그것을 필요로 하는 문제

문제 A)

3만원, 5만원, 8만원의 가치가 있는 물건이 있다. 여기서 2개의 물건을 들고 갈 수 있다. 가치의 합이 최대가 되도록 비싼 순서대로 2개를 들고 돌아왔다. 당신이 들고 온 물건의 가치 합계는 얼마인가?

 -> 비싼 순서대로 2개를 들고 돌아왔다 라고 과정이 명확히 쓰여 있다. 즉, 8만원짜리와 5만원짜리를 선택하는 경우밖에 없다. 

문제 B)

3만원, 5만원, 8만원의 가치가 있는 물건이 있다. 여기서 2개의 물건을 들고 갈 수 있다. 가치의 합이 최대가 되도록 물건을 고르려 한다. 당신이 들고 돌아갈 수 있는 최대 가치의 합계는 얼마인가?

 -> 가치의 합이 최대가 되도록 고르려 한다 라고 쓰여 있다. 하지만, 구체적으로 무엇을 어떻게 하라는지 밝혀져 있지 않다. 즉, 답을 얻으려면 모든 경우를 전체탐색 해야한다. 

 

눈치를 챘겠지만 문제 A가 시뮬레이션 문제이며 문제 B는 전체탐색 문제이다. 가만보면 문제B를 문제 A처럼 풀수도 있음을 알 수 있다. 다시 말해, 전체 탐색으로 모든 합 중 최대를 찾는 대신 가장 큰 값인 두개를 선택하면 빠르게 문제를 해결할 수 있다. 하지만 문제에서 총합 12만원 이상은 들고 갈 수 없다는 제한 조건이 붙는다면? 이때는 문제B를 문제A처럼 풀 수 없다. 그러니까 결론은 '이러한 제약조건이 있을 수 있으므로 전체 탐색을 사용하는 방법을 확실히 익혀야 한다'는 말이다. 

 

---

InterestingDigits 문제

 

저작권 문제가 있을 수 있으므로 문제에 대한 설명은 생략한다. 궁금하신 분은 댓글 달아주시면 알려드리겠습니다

 

전체 탐색을 이용한 풀이

 필자가 강조하는 방법이다. 수학에서 처럼 개념에 입각한 모든 문제를 관통하는 본질적 풀이라고 생각을 한다. 이 부분은 내일 쓰려고 한다.. 그 이유는 아직 완전히 내 것으로 체화하지 못하였기 때문이다. 

 

나의 풀이

 

모듈러 합동을 이용한 풀이

 

---

마치며

필자의 말로는 대부분의 문제는 전체 탐색으로 풀 수 있다고 주장을 한다. 그리고 전체 탐색하는 문제도 전체 탐색으로 풀 수 있는지 눈치를 못채는 경우도 있다고 한다. 즉 이렇게 전체 탐색으로 풀 수 있는 문제인지 알 기 위해서는 많은 문제를 풀어 경험을 쌓는 것 외에는 답이 없어보인다.

 

 

참고자료

• TopCoder 알고리즘 트레이닝, 타카하시 나오히로 지음

 

 

 

처음에는 도대체 '왜' 하냐고 물을 것이고,

나중에는 도대체 '어떻게' 해낸거냐고 물을 것이다.

어니스트 헤밍웨이

 

저자 깃허브