🧚‍♂️알고리즘🧚‍♂️ - 조합/순열 1

🧮조합🧮

n개의 숫자에서 r 개를 뽑는 경우의 수 (순서 고려 없음)

 

🧮순열🧮

n개의 숫자에서 r 개를 순서를 정해 뽑는 경우의 수 (순서 고려)

 

---

수학 식으로 표현하지 않고 동적 계획법처럼 점화식으로 표현함!

 

1. 특정 문제를 가정하기

 

2. 모든 부분 문제가 해결된 상황이라고 가정 하고 지금 문제 생각하기

 

3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

 

 

 

조합 점화식

D[i][j] = D[i-1][j](남은 하나를 선택하지 않는 경우) + D[i-1][j-1](남은 하나를 선택하는 경우) 

---

참고

0! = 1

---

브론즈1

11050번: 이항 계수 1

예전에는 팩토리얼 함수를 구현해서 식으로 풀었었다.

def factorial(N):
    if N == 0 or N == 1:
        return 1

    result = 1
    while (N != 1):
        result *= N
        N -= 1
    return result

print(factorial(N)//(factorial(K)*factorial(N-K)))

점화식으로 DP 테이블을 채워 푸는 방법도 있다.

from sys import stdin
N , K = map(int,stdin.readline().split())

# DP 테이블 초기화
DP = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(N+1): # 기본값들 세팅
    DP[i][1] = i # i 중에서 1 개 뽑기 : i
    DP[i][0] = 1 # i 중에서 0 개 뽑기 : 1
    DP[i][i] = 1 # i 중에서 i 개 뽑기 : 1

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

print(DP[N][K])

---

실버1

11051번: 이항 계수 2

숫자가 커져서 덧셈 연산 시 오버플로우를 조심해야 한다. 

모듈러 연산을 매 연산마다 추가시킨다.

for i in range(2,N+1):
    for j in range(1,i):
        DP[i][j] = DP[i-1][j] + DP[i-1][j-1] #조합 점화식 이용
        DP[i][j] = DP[i][j] % 10007 # 모듈러 연산 중요!!

---

브론즈2

2775번: 부녀회장이 될테야

푼문제임

---

실버5

1010번: 다리 놓기

- M개의 사이트에서 N개의 사이트를 선택하는 문제(순서 다르게 ㄴㄴ)

- 조합 점화식 쓰기!!!

를 해도 되지만 

그냥 팩토리얼 구현해서 풀었엇네

---

실버3

13251번: 조약돌 꺼내기

조약조약

 

모두 다 같은 색깔 돌 뽑으려면 

개수만큼 반복하면서

현재색깔돌개수 / 전체 돌개수 * 현재색깔돌개수-1 / 전체 돌개수-1 * 현재색깔돌개수-2 / 전체 돌개수-2 ..... 

오끼

from sys import stdin
M = int(stdin.readline()) # 조약돌의 색은 1-M
M_list = list(map(int, stdin.readline().split()))
K = int(stdin.readline()) # 랜덤하게 k 개 뽑았을 때 다 같을 확률 구하기
T = sum(M_list) # 전체 조약돌의 개수

answer = 0
for i in range(M):
    if M_list[i] >= K : #이 색깔 조약돌 개수가 뽑아야 할 조약도 수보다 클 떄만!
        tmp = 1
        for j in range(K):
            tmp *= (M_list[i]-j) / (T-j)
        answer += tmp
print(answer)