펭로그

문제링크 : https://noj.am/6603 N개의 원소를 가지는 집합에서 K개를 고르는 조합(Combination) 문제로 STL의 permutation을 사용하면 쉽게 풀 수 있다.algorithm 헤더에 있는 next_permutation()과 prev_permutation()으로 순열을 구할 수 있다.[1, 2, 3, 4]를 next_permutation()을 사용하면[1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] ..... 이런 식으로 사전 순서대로 순열이 적용된다.prev_permutation()은 그 반대라고 볼 수 있다. 그렇다면 조합을 사용하려면 어떻게 해야할까?[1, 1, 0, 0]을 prev_permutation()으로 돌려보면 아래와 ..

문제링크 : https://noj.am/8916 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071// BOJ 8916 이진 검색 트리#include using namespace std; long long comb(int n, int r) { // nCr r = n - r > r ? r : n - r; long long result = 1; for (int i = 0; i tc; while (tc--) { int num, input; vector tree(1); cin >> num; while(num--) { int i..

문제링크 : https://boj.kr/1010 이 문제는 M개의 사이트에 N개의 다리를 놓는 가지수를 구하면 되는 문제로 조합을 이용하여 풀었다.MCN = M! / ((M-N)! * N!) 을 구현하면 된다.6C4를 구하는 경우 (6*5*4*3*2*1) / ( (2*1) * (4*3*2*1) ) 인데 (4*3*2*1)에 해당하는 N!이 약분되어 (6*5) / (2*1)인 것을 중학교때 많이 배웠을 것이다. (M-N)!과 N! 중에서 더 많은 숫자를 제거할 수 있는 값을 고르면 되고 이를 그대로 식으로 표현하면 된다. 123456789101112131415161718192021222324252627282930// BOJ 1010 다리 놓기#include using namespace std; int mai..