[Python] 순열, 조합, 중복순열, 중복조합(itertools이용한 백트래킹)
https://knowallworld.tistory.com/228
Permutations()★순열,조합,중복순열,중복조합★기초통계학-[Chapter04 - 경우의 수]
https://knowallworld.tistory.com/146 [Python] 순열, 조합, 중복순열, 중복조합(itertools이용한 백트래킹) 순열 ==> 순열은 순서를 고려하여 뽑는 경우의 수 https://knowallworld.tistory.com/142 [백준 파이썬 15649번]N과M
knowallworld.tistory.com
==> 참고
순열
==> 순열은 순서를 고려하여 뽑는 경우의 수
https://knowallworld.tistory.com/142
[백준 파이썬 15649번]N과M★백트래킹★
백트래킹이란?? - 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행 - 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 VER 1.0 import sys def
knowallworld.tistory.com
==> 순열을 활용한 문제_N과 M
==>4 2 입력시 2개의 방에 4명이 들어갈 수 있는 경우의 수 구하라는것
nPr : 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 경우의 수
ex) 5P3 = 5!//2!
==>itertools 라이브러리에서 permutations 함수를 사용하여 순열을 구할 수 있다.
조합
==> 조합은 순서를 생각하지 않고 뽑는 경우의 수
https://knowallworld.tistory.com/143
[백준 파이썬 15650번]N과M_2★백트래킹★매개변수 고려
VER1.0 import sys def dfs(start): if len(s) == m: print(' '.join(map(str , s))) return for i in range(start, n+1): if visited[i]: continue visited[i] = True s.append(i) dfs(i+1) s.pop() visited[i]..
knowallworld.tistory.com
==> 조합을 활용한 문제 N과 M(2)
==>4 2 입력시 2개의 방에 4명이 들어갈 수 있는 경우의 수 구하라는것 ==> 다만 방의 순서는 상관없다!
==> nCr
nCr : 서로 다른 n개에서 순서를 생각하지 않고 r개를 택하는 경우의 수.
ex) 4C2 = 4!//[(4-2)!*2!]
==>itertools 라이브러리에서 combinations 함수를 사용하여 조합을 구할 수 있다.
중복순열
==> 중복순열은 순열과는 다르게 같은 숫자 중복하여 사용가능
https://knowallworld.tistory.com/144
[백준 파이썬 15651번]N과M_3★백트래킹★visited리스트 앞부분 고려
VER1.0 import sys def backtracking(): if len(s) == m: print(' '.join(map(str, s))) return for i in range(1, n+1): if visited[i] == True: # s.append(i) continue if visited[i-1] == True: s.append(i-1..
knowallworld.tistory.com
==> 중복순열을 활용한 문제 N과 M(3)
==>4 2 입력시 2개의 방에 4명이 들어갈 수 있는 경우의 수 구하라는것 ==> 방의 순서는 상관있다!
==>경우의 수로 사람이 복제되서 그냥 동시에 들어갈 수 있다고 생각하자.
==> nπr
nπr : 중복 가능한 n개에서 r개를 택하여 일렬로 나열하는 경우의 수.
ex) 4ㅠ2 = 4^2
==>itertools 라이브러리에서 product 함수를 사용하여 조합을 구할 수 있다.
중복조합
==> 중복조합은 조합과는 다르게 같은 숫자를 중복하여 사용가능
https://knowallworld.tistory.com/145
[백준 파이썬 15652번]N과M_4★백트래킹★visited리스트 앞부분 고려
VER2.0 import itertools import sys n,m = map(int , sys.stdin.readline().split()) res = [i for i in range(1, n+1)] array = itertools.combinations_with_replacement(res , m) for i in array: for j in i..
knowallworld.tistory.com
==> 중복조합을 활용한 문제 N과 M(4)
==>4 2 입력시 2개의 방에 4명이 들어갈 수 있는 경우의 수 구하라는것 ==> 방의 순서는 상관없다!
==>경우의 수로 사람이 복제되서 그냥 동시에 들어갈 수 있다고 생각하자.
==> nHr
nHr : 중복 가능한 n개에서 순서를 생각하지 않고 r개를 택하는 경우의 수
ex)4H2 = 4+2-1C2
==> nHr = n+r-1Cr
==>itertools 라이브러리에서 combinations_with_replacement 함수를 사용하여 조합을 구할 수 있다.
'Python(백준) > 백트래킹' 카테고리의 다른 글
| [PYTHON]_코테에서도 쓰일_조합_계산_파스칼의 삼각형_시간복잡도(이항정리, 이항계수) 사용하기!! (0) | 2022.12.22 |
|---|---|
| [백준 파이썬 15652번]N과M_4★백트래킹★visited리스트 앞부분 고려 (0) | 2022.10.25 |
| [백준 파이썬 15651번]N과M_3★백트래킹★visited리스트 앞부분 고려 (0) | 2022.10.25 |
| [백준 파이썬 15650번]N과M_2★백트래킹★매개변수 고려 (0) | 2022.10.25 |
| [백준 파이썬 15649번]N과M★백트래킹★ (0) | 2022.10.25 |