[완전 탐색] 순열 & 조합 익숙해지기

순열, 조합과 같은 유형들에 익숙하지 않아서 공부가 많이 필요할 듯. 

 

아래 포스팅에서 이와 관련된 유형을 정리해주셨는데 참고하면 좋을 듯
https://5myohan.tistory.com/88

[삼성SW테스트 준비] 순열과 조합 연습 문제-1 (백준 15649, 15654, 15655, 15657, 15663, 15664, 15665, 15666)

 

우선 대표 유형으로 아래 문제를 가져왔고 아래 문제는 "순열"로 푸는 문제다. 

순열 + 소수 찾기 유형이고, python의 permutation 함수에 익숙해지자. 또한 중간에 중복을 제거해주는 것이 매우 중요하다

순열은 순서로 경우가 구분되는 경우
조합은 순서로 경우가 구분되지 않는 경우 꼭 명심하자

이미 안다고 생각하지만 막상 헷갈릴 때가 있다.
순열은 ('1','7')과 ('7','1')이 같은 경우, 조합은 같은 1, 7을 선택한 경우라고 생각한다. 

그래서 이를 사용한 첫 코드는 다음과 같다.

from itertools import permutations ## 순열 쓰는 함수에 주목

### 소수 판별함수. 
def is_Prime(num) :
    if num == 0 or num == 1 :
        return False
    for div in range(2,num) :
        if num%div == 0 :
            return False
    return True

def solution(numbers) :
    num_set = list(numbers)

    num_represent = []

    for i in range(1,len(numbers)+1) :
        permutation = permutations(num_set,i)
        for ele in permutation :
            cases = ''
            for num in ele :
                cases += num
            num_represent.append(int(cases))

	### 중복 체크에 주의하자
    num_represent = list(set(num_represent))
    print(num_represent)

    cnt = 0
    for element in num_represent :
        if is_Prime(element) :
            cnt +=1

    return cnt

하지만 중간에 for loop가 두 번 들어가서 코드가 더러운데, map을 많이 쓰더라. 난 map에 익숙하지 않은데 이거에도 익숙해지면 좋을 듯

from itertools import permutations

def is_Prime(num) :
    if num == 0 or num == 1 :
        return False
    for div in range(2,num) :
        if num%div == 0 :
            return False
    return True

def solution(numbers) :
    num_set = list(numbers)

    num_represent = []

    for i in range(1,len(numbers)+1) :
        permutation = permutations(num_set,i)
		### map 사용에도 익숙해져보자
        num_represent.extend(map(int,map(''.join,list(permutation))))

    num_represent = list(set(num_represent))
    
    cnt = 0
    for element in num_represent :
        if is_Prime(element) :
            cnt +=1

    return cnt

또한 이 분의 풀이를 보면 재귀로 멋지게 구현도 할 수 있는데 이것도 익숙해지면 좋을 듯
https://www.youtube.com/watch?v=m3kCKV8oc1g&t=26s

def is_Prime(num) :
    if num == 0 or num == 1 :
        return False
    for div in range(2,num) :
        if num%div == 0 :
            return False
    return True

num_represent = []

### '' 이런 문자열에 '1', '17' 이런 식으로 더해주면서 재귀함수로 경우의 수 탐색
def DFS(curr,rest) :
    if curr != "" :
        if is_Prime(int(curr)) :
            num_represent.append(int(curr))
	
    ### 모든 for loop를 돌리게 되면 경우의 수 마침
    for i in range(len(rest)) :
        DFS(curr+rest[i], rest[:i]+rest[i+1:])

def solution(numbers) :

    curr = ''

    DFS(curr,numbers)

    return len(set(num_represent))

 

 

여기서 중요한 게 "중복"은 순열과 조합 모두에서 발생한다는 점 명심하자. 혼동하지 말아. 둘의 차이는 오직 "순서"임