0주차-3. 기초 개념 : 조합(Combination)
조합이란? 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음) 조합이 순열과 다른 대표적인 점은 순서가 달라도 요소가 같으면 같은 조합으로 본다는 것이다. 1, 2, 3, 4, 5라는 집합이 있을 때 {1, 2, 3, 4, 5}, {2, 1, 3, 4, 5}, {3, 1, 2, 4, 5} .... 등등 순서를 바꿔도 같은 조합으로 본다는 것이 대표적인 차이점이다. 조합은 n C r로 표현하며 개수를 구하는 식은 아래와 같다. 재귀함수를 이용한 구현 (뽑아야 할 수(r) 가 4개 이상인 경우) void combination(int start, int n, int k, std::vector& v) { // n : 최대 조합 수 'n'Cr // k : 그 조합에서 추출할 요..
2022. 9. 3.
0주차-2. 기초 개념 : 순열(Permutation)
순열이란? 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음) 1, 2, 3이라는 수들의 집합이 있을 때 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 이렇게 6가지 순열이 나온다. n P r이란, 쉽게 말해 n개중에 r개로 이루어진 수열을 만든다는 뜻. 프로그램에서 구현 방법은? do-while문을 이용한 구현 #include #include #include #include template void print(const T& container) { for (auto e : container) std::cout
2022. 9. 3.
