조합
[Algorithm Study] 파이썬 부분집합 구하기 예시
반복문을 이용해 부분집합 구하기 arr = list(map(int, input().split())) subsets = [[]] for i in arr: L = len(subsets) for l in range(L): subsets.append(subsets[l] + [i]) print(subsets) 비트연산자를 이용해서 부분집합 구하기 arr = list(map(int, input().split())) n = len(arr) for i in range(1
[백준 파이썬] # 11727 2xn 타일링 2
Silver III # 11727 2xn 타일링 2 링크 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 n = int(input()) dp = [0] * n dp[0] = 1 for i in range(1, n): if i%2 == 0: dp[i] = dp[i-1] + dp[i-1] - 1 else: dp[i] = dp[i-1] + dp[i-1] + 1 print(dp[-1] % 10007) 후기 이전 문제인 11726과 동일한 유형의 문제다. 수열의 n번째 값을..
[백준 파이썬] # 11726 2xn 타일링
Silver III # 11726 2xn 타일링 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) if n == 1: print(1) else: dp = [0] * n dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1]+dp[i-2] print(dp[-1] % 10007) 후기 결과부터 말하자면 피보나치 수열임을 발견할 수 있다. dp를 이용해서 원하는 값을 찾아가도록 구..
[확률과 통계] 순열과 조합
순열(nPr) 서로 다른 n개 중 r개를 선택하는 경우의 수 순서가 중요할 때 $$ _nP_r = \frac{n!}{(n-r)!} $$ 3명 중 2명을 뽑아 처음 사람에게 밥을 주고, 두 번째 사람에게 음료를 준다. 이때의 경우의 수는? a, b // b, a 는 서로 다른 경우 : 순서가 중요하다 조합(nCr) 서로 다른 n개 중 r개를 선택하는 경우의 수 순서가 중요하지 않을 때 $$ _nC_r = \frac{n!}{(n-r)!r!} $$ 3명 중 2명을 뽑아서 밥을 주려고 할 때, 경우의 수는? a, b // b, a 는 같은 경우 : 순서가 중요하지 않다 같은 것이 있는 순열 같은 것의 개수만큼 팩토리얼로 나눠준다 case 1: aaabb를 나열하는 경우의 수 case 2 : 원순열 case 3 ..