조합

[Java] DP – 응용

작성자:
Featured image for [Java] DP - 응용

1. 이항 계수 구하기 가. 이항 계수 조합으로 이항 계수를 구할 수 있다. 위와 같이 일반화할 수 있다. 나. 조합 공식 조합 공식 – 계산량이 많은 팩토리얼(n!, r!)을 계산하지 않고 아래의 수식을 이용한다. 이는 재귀 함수로 구현할 수 있다. 중복되는 계산을 줄이기 위해서 메모이제이션을 활용한다. 순수 함수, 중복 부분문제 구조, 최적 부분문제 구조를 만족하기 때문에 … 더 읽기

[Java] 순열과 조합

작성자:
Featured image for [Java] 순열과 조합

  종류 설명 기호 시간복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! / (r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 1. 순열 가. 반복문 nPr에서 r이 고정되어 있고, 일반적으로 3중 … 더 읽기

[C++] 조합

작성자:

1. 조합 서로 다른 n개에서 순서와 상관없이 r개를 고르는 걸 조합이라고 한다. 조합을 구현하는 두 가지 방법에 대하여 학습했다. 2. 중첩 for문 3개까진 중첩 for문을 사용하자. 3. 재귀함수 대략 4개 이상부터는 재귀함수를 사용해서 구현하자. 4. 주의점 nCr이나 nC(n-r)이나 똑같다. 3개 중에 2개를 뽑는 것 = 3개 중에 1개를 뽑는 것 1개를 뽑으면 나머지 2개가 나오기 … 더 읽기