Algorithm 공부 #23 - 조합(combination)

 

Algorithm 공부 #23 - 조합

 

 

조합(Combination)

  ● n개의 숫자에서 r개를 뽑는 경우의 수

  ● 코딩 테스트에서는 순열보다는 조합이 빈도수가 높음

  ● 조합은 동적 계획법의 시작이라고 할 수 있음

  ● 조합의 접근법 : 이미 그 전단계의 데이터의 선택여부가 결정되었다고 생각하기

                               D[i][j] = D[i-1][j] + D[i-1][j-1]

 

 

백준 11050번 이항 계수 1

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

11050번: 이항 계수 1

#include<iostream>
using namespace std;
int D[11][11];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	for (int i = 0; i <= N; i++) {
		D[i][0] = 1;
		D[i][i] = 1;
		D[i][1] = i;
	}
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
		}
	}

	cout << D[N][K];

}

 

 

 

 

백준 11051번 이항 계수 2

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

11051번: 이항 계수 2

#include<iostream>
using namespace std;
int D[11][11];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	for (int i = 0; i <= N; i++) {
		D[i][0] = 1;
		D[i][i] = 1;
		D[i][1] = i;
	}
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			D[i][j] = (D[i - 1][j] + D[i - 1][j - 1])%10007;
		}
	}

	cout << D[N][K];

}

 

 

 

 

백준 2775번 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

  ● 점화식 응용해서 dp형식으로 풀기

#include<iostream>
using namespace std;
int D[15][15];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;

	for (int i = 0; i <= 14; i++) // 0층 채워놓기
		D[0][i] = i;

	for (int i = 0; i <= 14; i++)
		D[i][1] = 1;
	for (int i = 1; i <= 14; i++) {
		for (int j = 2; j <= 14; j++) {
			D[i][j] = D[i][j - 1] + D[i - 1][j];
		}
	}
	for (int i = 0; i < T; i++) {
		int a, b;
		cin >> a >> b;
		cout << D[a][b] << "\n";
	}
}

 

 

 

백준 1010번 다리 놓기

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

1010번: 다리 놓기

#include<iostream>
using namespace std;

int dp[31][31];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i <= 30; i++) {
		dp[i][0] = 1;
		dp[i][1] = i;
		dp[i][i] = 1;
	}

	for (int i = 2; i <= 30; i++) {
		for (int j = 1; j < i; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
		}
	}
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		cout << dp[b][a] << '\n';
	}
}

 

 

 

백준 13251번 조약돌 꺼내기

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

13251번: 조약돌 꺼내기

#include <iostream>
using namespace std;

static int M, K, T;
static int D[51];
static double probability[51];
static double ans = 0.0;

int main()
{
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> D[i];
        T += D[i];
    }

    cin >> K;
    for (int i = 0; i < M; i++) {
        if (D[i] >= K) {
            probability[i] = 1.0;
            for (int k = 0; k < K; k++)
                probability[i] *= (double)(D[i] - k) / (T - k);
        }
        ans += probability[i];
    }
    cout << fixed;
    cout.precision(9); // 오차 범위내 출력을 위한 소수점 자리수 설정
    cout << ans;
}