파이썬 - 순열, 조합 (permutaions, combinations)

목차

-시작

-permutaions

-combinations

-문제

 

시작

파이썬 itertools를 이용하면.

쉽게 순열조합을 처리할 수 있습니다.

대부분 순열조합을 사용하는 문제는 인풋값이  10개 정도로 작아.

모든 경우의 수를 탐색해도 작은 시간을 소요할떄 사용합니다.

인풋값이 작아 모든 경우를 탐색해도 무방할 때.

"순열조합을 사용하면 편하겠군, 개꿀~!"

이란 생각이 나는 것을 목표로 학습하면 좋습니다.

permutaions

permutaions(리스트, r)  permutaions는 리스트와 같은 반복 가능한 객체와 자연수 r을 파라매터로 받습니다.

이를 실행하면 리스트에서 r개를 뽑아 순서를 고려하여 나열한 모든 경우의 수를 리턴합니다.

 

아래의 예시는 반복 가능한 객체 집합 {A, B, C}에 대해 2개를 뽑아 나열할 수 있는 경우의 수를 구한 것입니다.

permutaions 밖에 List로 변환 처리를 해주었는데.

permutaions는 튜플을 성분으로 가지는 generater이기 때문에 그렇습니다.

만약 몰라도 않더라도 상관은 없지만.

궁금하다면 구글에 파이썬 generator을 검색해 봅시다. 

# ex {A,B,C}
from itertools import permutations
perm = list(permutations({"A","B","C"},2))
print(perm)

[('A', 'C'), ('A', 'B'), ('C', 'A'), ('C', 'B'), ('B', 'A'), ('B', 'C')]

# 뽑는 수가 집합의 크기를 초과하면 []를 리턴한다
perm = list(permutations({"A","B","C"},4))
print(perm)

[]

 

combinations

combinations(반복 가능한 객체, r)  permutaions과 동일하게 반복 가능한 객체와 자연수 r을 파라매터로 받습니다.

이를 실행하면 반복 가능한 객체에서 r개를 뽑고 순서를 고려하지 않는 모든 경우의 수를 리턴합니다.

 

permutaion과 달리 성분이 반복이 되지 않는 것을 확인할 수 있습니다.

ex {A,B,C}
from itertools import combinations 
comb = list(combinations({A,B,C},2))
print(comb)

[('A', 'C'), ('A', 'B'), ('C', 'B')]

# 뽑는 수가 집합의 크기를 초과하면 []를 리턴한다
comb = list(combinations({"A","B","C"},4))
print(comb)

[]

문제

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 12주차

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

방문할 수 있는 최대 던전수를 구하는 문제입니다.

문제를 보면 특이한 점을 확인할 수 있습니다.

가장 큰 dungens가 8개라는 점입니다.

이 말은 무지성으로 전부 탐색해도 무방하니.

제발 순열조합으로 리스트업 하고.

코드를 작성하라는 뜻입니다.

그러면 구라코드를 작성해 봅시다.

 

구라코드

1. permutaion을 이용하여 모든 던전의 순서를 리스트업 한다.

2. 리스트업 한 경우들을 루프를 돌며 방문 가능한 던전수를 체크한다.

    그리고 마지막에 결괏값을 저장한다.

3. 저장한 결과값 중 최댓값을 출력한다.

 

아래의 코드는 heapq를 이용하여 최대값을 출력했지만.

인풋이 작기 때문에 max()를 이용해도 무방합니다.

from itertools import permutations
import heapq
def solution(k, dungeons):
    permus =  permutations(dungeons,len(dungeons))
    dum = k
    answer = []
    heapq.heapify(answer)
    for ele in permus:
        k = dum
        count = 0
        for ith_dunden in ele:
            if ith_dunden[0] <= k:
                k -= ith_dunden[1]
                count += 1
            else:
                continue
        heapq.heappush(answer, -count)
    return -heapq.heappop(answer)

 

이전 글 - 파이썬 스택 큐

다음 글 - 파이썬 정렬