[완전탐색] 문제에서 '완전탐색일 수 밖에 없는 이유' 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

문제

<왜 완전탐색일 수 밖에 없는가?>

 

  1. '순열(순서쌍)' 문제이면서, 최대 조합의 길이가 '7'이기 때문이다.

    결국 입력값들의 모든 순열을 구해야한다. 위 문제는 특히 1~n개 일때의 순열을 모두 구하여야한다.

    위 문제의 최대길이는 7 (n=7)이기 때문에 순서쌍을 구하는 모든 경우의 수는 1! + 2! + 3! + ... + 6! + 7! ~= 5,000 이다

 

    2초가 코테의 제한시간이라면, 대략 2억번의 연산이 가능하다.

    그리고 gpt에 따르면, 대략적으로 완전탐색을 적용할 수 있는 현실적인 한계는 숫자 문자열의 길이가 7 또는 8 이하일 때이다.

    그렇기 때문에 순서쌍을 구해야하는 상황이 있을 때 길이 제한이 7~8이라면, 고민없이 순열을 쓰면된다.

     (python의 경우 itertool Library가 있기 때문에... 정말 간편!)

 

  2. '소수'판별 문제이기 때문이다.

     소수에는 규칙이없다. 

    소수의 규칙찾는 문제는 정말 1,000년 넘게 수학자들의 뜨거운 감자였다고 알고 있다. 그러나 21세기 현재 소수에 가장 가깝게 다가간        것이 그 유명한 리만가설이지 않는가? 

    (리만가설을 한줄로 말하지면 '소수의 규칙이 있을 수도 있다'라는 '가설'이라고 알고있다.)

 

    소수는 규칙이 없다. 그렇기 때문에 2부터 소수의_제곱근_+1 까지의 모든 자연수를 나눔으로써 해당 숫자의 소수인지 여부를 알 수 밖에 없다.

    (모든 수의 약수는 대칭성이 있다. 예를들어 36의 약수는 1,2,3,4,6,9,12,18,36 인데, 가운데 6을 두고 데칼코마니처럼 양쪽 숫자를 곱하면 36이다. 그 가운데의 기준의 숫자의_제곱근 이다.)

 

그렇다면 순서쌍 찾기와 소수판별 파트는 각각 완전탐색이라는 것을 인정하고 시간복잡도를 생각해보자

 

1. permutation(순열): 숫자 순서쌍 ->  7!+6!+...1! ~= 7000

2. 소수탐색: 2~현_숫자의_제곱수+1 까지 나눠보기 -> 제일큰수의 횟수 <10,000

7,000 * 10,000 = 7e7 < 2e8(2억) ---> 가능!

 

    

마지막으로 코딩 전에 고려했던 것이, "011"과 "11"을 같은 숫자로 처리하는 부분인데,

두 문자열 모두 integer로 바꾸면 11로 같아지고, 구별 할 수 있는 방법이 없어지므로,

String 상태일때 "만약 0.startswith("0")이라면 continue" 로 해결했다. (어차피 소수찾기때 0 or 1이면 continue도 써야됐기 때문에 생각보다 간편하게 해결되었다.)

 

from itertools import permutations
def solution(numbers):
    undividable = 0
    length = len(numbers)
    for i in range(1, length+1):
        comb_set = set(permutations(numbers, i))
        # print(comb_set) {('1', '1', '0'), ('0', '1', '1'), ('1', '0', '1')}
        for comb in comb_set:
            num = "".join(comb)
            # print(num)# 110 011 101
            if num.startswith("0") or num=="1":
                continue
            num = int(num)
            flag = True
            for i in range(2, num):
                if num%i == 0:
                    flag = False
                    break
            if flag is True:
                # print(num)
                undividable += 1
    return undividable


print(solution("011"))

 

순열찾는데에는 itertools library의 permutation을 사용했고,

순열을 List로 만드는 대신에 set로 만듦으로써 ('1', '1', '0')이 두번 나오는 것을 방지했다.

comb_set 안의 각 순서쌍을 "".join으로 String으로 규합하고,

.startswith("0") or =="1"이 아니라면 소수탐색 하게했다.

 

코딩테스트를 약 한달전에 입문했는데, 그동안 타 문제를 풀고 다른 사람의 문제들을 참고해보면서 얻은 지식들이 이렇게 유용하게 쓰이니 짜릿함을 느꼈다.

 

위 코드에 쓰인 기억할만한 function들을 다시 한 번 써보면서 오늘 코테공부를 마치는걸로.

 

from itertools import permutations

comb_set = set(permutations(iterable_object, n))

"".join(comb)

String.startswith("0")