본문 바로가기
코딩테스트

[Python] 조합

you__me 2024. 5. 25. 22:16

# 10-1. 조합 알아보기

조합(Combination)이란?

  • nCr로 표현하며, n개의 숫자 중에서 r개를 뽑는 경우의 수
  • 순열은 nPr로 표현되며, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기 한다.

 

조합의 핵심 이론

  • 순열 공식 nPr = n!/(n-r)!
  • 조합 공식 nCr = n!/(n-r)!r!
  • 알고리즘에서 조합을 구현할 때는 위 공식을 코드화하지 않고 점화식을 사용해 표현한다.
    • 예를 들어, 5개의 데이터 중 3개를 선택하는 경우는 5개의 데이터 중 4개의 데이터의 선택 여부가 결정된 상태로 가정한다.
    • 따라서 5번째 데이터의 선택 여부에 따라 이전 4개의 데이터 중 2개 혹은 3개를 선택하는 경우의 수로 나뉜다.
    • 위를 점화식으로 표현하면 D[5][3] = D[4][2]+D[4][3]이 된다.
    • 위 과정을 바탕으로 일반 점화식을 도출할 수 있다. D[i][j] = D[i-1][j] + D[i-1][j-1]

 

https://www.acmicpc.net/problem/11050

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
D = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(0, N+1): # DP 테이블 초기화
    D[i][1] = i # i개에서 1개 선택하는 경우의 수는 i개
    D[i][0] = 1 # i개에서 1개도 선택하지 않는 경우의 수는 1개
    D[i][i] = 1 # i개에서 모두 선택하는 경우의 수는 1개

for i in range(2, N+1):
    for j in range(1, i):
        D[i][j] = D[i-1][j]+D[i-1][j-1] # 조합 점화식

print(D[N][K])
  • N,K의 값을 입력받고 DP 테이블을 초기화 한다.
  • 점화식으로 DP 테이블의 값을 채운 후 D[N][K]의 값을 출력한다.
  • 이때 j는 i값(선택 수, 총 개수)을 넘지 않는다. 즉, 대각선 윗부분은 채워지지 않음.

 

 

https://www.acmicpc.net/problem/11051

  • N의 범위가 커지고 결괏값을 10,007로 나눈 나머지를 출력한다.
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
D = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(0, N+1):
    D[i][1] = i # i개에서 1개 선택하는 경우의 수는 i개
    D[i][0] = 1 # i개에서 1개도 선택하지 않는 경우의 수는 1개
    D[i][i] = 1 # i개에서 모두 선택하는 경우의 수는 1개

for i in range(2, N+1):
    for j in range(1, i):
        D[i][j] = D[i-1][j]+D[i-1][j-1] # 조합 점화식
        D[i][j] = D[i][j]%10007 # mod 연산

print(D[N][K])
  • 모듈러 연산의 특성 : (A mod N + B mod N) mod N = (A+B) mod N
  • DP 테이블에 결괏값이 나올 때마다 모듈러 연산을 수행한다.

 

https://www.acmicpc.net/problem/2775

import sys
input = sys.stdin.readline
D = [[0 for j in range(15)] for i in range(15)]

for i in range(1, 15):
    D[i][1] = 1 # i층의 1호는 항상 1의 값을 지니므로 초기화 가능
    D[0][i] = i # 0층의 i호는 i의 값을 지니도록 주어짐

for i in range(1, 15):
    for j in range(2, 15):
        D[i][j] = D[i][j-1]+D[i-1][j] # 점화식

T = int(input())

for i in range(0, T): # D 테이블을 모두 구해 놓은 후 질의에 대한 답 출력
    K = int(input())
    N = int(input())
    print(D[K][N])
  • a층의 b호에 살려면 자신의 아래층 (a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다.
  • 즉, D[a][b] = D[a-1][0]+...+D[a-1][b-1]+D[a-1][b]로 나타낼 수 있다. 이 내용을 응용하면 a층 b호는 a층 b-1호의 값에서 자기 아래층(a-1층 b호)의 사람 수만 더하면 된다.
  • 이를 일반화된 점화식으로 나타내면 D[a][b] = D[a][b-1] +D[a-1][b]가 된다.

 

 

https://www.acmicpc.net/problem/1010

import sys
input = sys.stdin.readline
D = [[0 for j in range(31)] for i in range(31)]

for i in range(1, 31):
    D[i][1] = i # i개에서 1개 선택 경우의 수는 i개 
    D[i][0] = 1 # i개에서 1개도 선택하지 않는 경우의 수는 1개
    D[i][i] = 1 # i개에서 모두 선택하는 경우의 수는 1개

for i in range(2, 31):
    for j in range(1, i):
        D[i][j] = D[i-1][j]+D[i-1][j-1] # 점화식

T = int(input())

for i in range(0, T): # D 테이블을 모두 구해 놓은 후 질의에 대한 답 출력
    N, M = map(int, input().split())
    print(D[M][N])
  • M개의 사이트에서 N개를 선택하는 조합 문제로 변경한다.
  • D[31][31]로 DP 테이블을 선언하고 초기화 한다.
  • 점화식을 이용해 DP 테이블을 채운다. M(행)개 중 N(열)개를 뽑는 것임.

 

https://www.acmicpc.net/problem/13251

  • 단순 확률식으로 풀 수 있지만 테이블을 이용해서 풀어보자.
D = [0]*51
prob = [0]*51

M = int(input())
D = list(map(int, input().split()))
T = 0

for i in range(0, M):
    T += D[i] # 조약돌 개수 더하기

K = int(input())
ans = 0

for i in range(0, M):
    if D[i]>=K:
        prob[i]=1
        for k in range(0, K):
            prob[i] = prob[i]*(D[i]-k)/(T-k) # 확률식
        ans += prob[i]

print(ans)
  • 색깔별 조약돌의 개수에서 K를 뽑을 수 있는 경우의 수를 구한 후, 전체 돌에 관해 n개를 뽑는 경우의 수를 나눈다.
  •  색깔별 조약돌의 개수를 D테이블에 저장하고, 전체 조약돌의 개수 T를 구한다.
  • 한 색깔의 조약돌만 뽑을 확률을 색깔별로 구한다. 입력 K에 따라 구하기.
  • 각 확률을 더해 출력한다.

 

https://www.acmicpc.net/problem/1722

  • 첫줄에 입력받은 N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다.
import sys
input = sys.stdin.readline

F = [0]*21
S = [0]*21
visited = [False]*21
N=int(input())
F[0] = 1

for i in range(1, N+1): # 팩토리얼 초기화 -> 각 자릿수에서 만들 수 있는 경우의 수
    F[i] = F[i-1]*i

inputList = list(map(int, input().split()))

if inputList[0]==1:
    K = inputList[1]
    for i in range(1, N+1):
        cnt = 1
        for j in range(1, N+1):
            if visited[j]: # 이미 사용한 숫자는 사용 X
                continue
            if K<=cnt*F[N-i]: # 주어진 K에 따라 각 자리에 들어갈 수 있는 수 찾기
                K-=(cnt-1)*F[N-i]
                S[i]=j
                visited[j]=True
                break
            cnt+=1
    for i in range(1, N+1):
        print(S[i], end=' ')
else:
    K = 1
    for i in range(1, N+1):
        cnt = 0
        for j in range(1, inputList[i]):
            if not visited[j]:
                cnt += 1 # 미사용 숫자 개수만큼 카운트
        K += cnt*F[N-i] # 자릿수에 따라 순서 더하기
        visited[inputList[i]] = True
    print(K)
  • 먼저 자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산한다. 4자리의 경우, list = [4!, 3!, 2!, 1!]로 저장이 된다. 이후 문제에 따라 2가지 경우로 나뉜다.
  • K번째 순열 출력하기
    • 주어진 값 K와 현재 자리(N)-1에서 만들 수 있는 경우의 수를 비교한다. 
      • if K<=cnt*F[N-i]에 해당하지 않는다면 cnt +1(아래)
    • K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가한다.
    • K가 더 작아지면 순열에 값을 저장하고, K를 K-(경우의 수 * (cnt-1))로 업데이트 한다.
    • 순열이 완성될 때까지 위 과정을 반복한다.
  • 입력된 순열의 순서 구하기
    • 현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자를 카운트 한다.
    • 미사용 숫자 개수*(현재 자리 -1에서 만들 수 있는 순열의 개수)를 K에 더한다.
    • 모든 자릿수에 관해 위 과정을 반복한 후 K값을 출력한다.
  • 개인적으로 너무 어려웠다....플레보다....아래 참고

https://karla.tistory.com/43#--%--K%EB%B-%--%EC%A-%B-%--%EC%--%-C%EC%--%B-%--%EC%B-%-C%EB%A-%A-

 

 

https://www.acmicpc.net/problem/1256

  • a와 z의 개수가 각각 N,M개일 때 이 문자들로 만들 수 있는 모든 경우의 수는 N+M개에서 N개 혹은 M개를 뽑는 경우의 수와 동일하다.
import sys
input = sys.stdin.readline
N,M,K = map(int, input().split())
D = [[0 for j in range(202)] for i in range(202)]

for i in range(0, 201): # 조합 테이블 만들기
    for j in range(0, i+1):
        if j==0 or j==i:
            D[i][j]=1
        else:
            D[i][j] = D[i-1][j-1] + D[i-1][j]
            if D[i][j] > 1000000000:
                D[i][j] = 1000000001 # K값의 범위가 넘어가면 최댓값 저장

if D[N+M][M]<K: # 주어진 자릿수로 만들 수 없는 K번째 숫자의 경우
    print(-1)

else:
    while not(N==0 and M==0):
        if D[N-1+M][M]>=K: # a를 선택해도 남은 경우의 수가 K보다 큰 경우
            print("a", end='')
            N-=1
        else:
            print("z", end='')
            K-=D[N-1+M][M]
            M-=1
  • 조합의 경우의 수를 나타내는 DP테이블을 초기화하고 점화식으로 저장한다.
    • D[i][j] = D[i-1][j-1] + D[i-1][j]
  • 몇 번째 문자열을 표현해야 하는지 나타내는 변수를 K라 한다. 현재 자릿수에서 a를 선택했을 때 남아있는 문자들로 만들 수 있는 모든 경우의 수를 T라고 지정한다. T와 K를 비교해 문자를 선택한다.
    • T >= K : 현재 자리 문자를 a로 선택
    • T < K : 현재 자리 문자를 z로 선택하고, K=K-T로 업데이트
  • 위 과정으로 a와 z의 문자들의 수를 합틴만큼 반복해 정답 문자열을 출력한다.

 

https://www.acmicpc.net/problem/1947

  • 완전 순열 : n개의 원소의 집합에서 원소들을 재배열할 때 이전과 같은 위치에 배치되는 원소가 1개도 없을 때를 말한다.
N = int(input())
mod = 1000000000
D = [0]*1000001
D[1] = 0
D[2] = 1

for i in range(3, N+1):
    D[i] = (i-1)*(D[i-1]+D[i-2])% mod # 완전 순열 점화식

print(D[N])
  • D[N] 테이블을 N명일 때 선물을 교환할 수 있는 모든 경우의 수로 정한다. N명이 존재하며, A가 B에게 선물을 주었을 때 교환 방식은 2가지가 존재한다.
    • B도 A에게 선물을 줌(양방향) : 남은 경우의 수는 D[N-2]
    • B는 A에게 주지 않음(단방향) : 남은 경우의 수는 D[N-1], B만 받은 선물이 전해진 것!
  • A는 (N-1)명의 학생에게 선물을 전달할 수 있으므로, 점화식을 도출하면 D[i] = (i-1)*(D[i-1]+D[i-2])가 된다.
  • DP테이블을 초기화 한 후 완전 순열 점화식으로 정답을 구한다.

 

# 회고

 

조합 너무어렵다ㅜㅜ

조합은 진짜 브론즈문제부터 차근차근...해야할 듯. 점화식을 도출해내는 머리가 부족한 듯 하다. 🥲🥲🥲🥲🥲

'코딩테스트' 카테고리의 다른 글

[Python] 조합 문제 풀이 정리(2)  (0) 2024.05.30
[Python] 조합 문제 풀이 정리(1)  (0) 2024.05.29
[Python] 트리 문제 풀이 정리  (0) 2024.05.21
[Python] 그래프 문제 풀이 정리(1)  (0) 2024.05.19
[Python] 트리  (0) 2024.05.17

'코딩테스트' Related Articles

티스토리툴바