[코딩테스트 준비] 완전 탐색 ( Brute-Force Search ) - 모의 고사 문제 (Python 풀이)

설명

완전 탐색이라는건 모든 경우의 수를 전부 찾고 그중에서 답을 찾는 알고리즘을 뜻한다.

 

완전 탐색을 하는 방법에는 여러가지가 있는데 

 

이중에 가장 대표적인게 Brute-Force Search 또는 Brute-Force Attack이라고도 불린다.

 

단어 그대로 직역을 해보자면 무차별 검색 또는 무차별 공격이라고 나오는데 

 

무슨 말인지 잘 감이 오질 않아서 영어로 된 설명을 좀 찾아보았다.

 

 

"Trying every single possibility rather than advanced technique to improve efficiency"

 

 

나는 이게 좀 더 와 닿았다.

 

시간 효율 고려하지 말고 가능한 경우의 수는 다 보자는 얘기 였다.

 

그렇다면 최소한 문제 내에서 시간 제한을 넉넉하게 주지 않을까 하는 기대를 하게 만든다.

 

문제

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

 

입출력 예 설명

 

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

 

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

 

풀이

수포자들이 찍는 방식에 따라 테이블을 만들었다.

 

시험 문제는 최대 10,000 문제인데 수포자들의 찍는 방식을 시험 문제 숫자에 맞게

 

나열하는게 이 문제의 포인트가 아닐까 

 

Modulo를 쓰기로 결정했다.

 

1번 수포자를 예로들면 1,2,3,4,5,1,2,3,4,5.... 이런식으로 반복된다.

 

modulo 5를 쓰면 remainder가 0,1,2,3,4까지 가능하기 때문에

 

[1,2,3,4,5] 테이블 한개만 만들어도 충분히 구현이 가능하다.

 

채점을 하고 난 후에는 가장 높은 점수를 찾은 다음

 

각 학생들의 점수들을 전부 가장 높은 점수와 비교해서

 

답을 찾는 방식으로 풀었다.

 

 

프로그래머스에 있는 완전 탐색 문제들중 가장 난이도가 낮은 문제 답게 큰 어려움은 없었다.

 

하지만 완전탐색을 이해하는데에 있어서 매우 도움이 되는 문제라고 할수 있다.