[C/C++] 순열과 조합 알고리즘 구현하기 3
저번 시간까지 순열의 개념을 학습하고, 일반적인 순열과 중복이 가능한 순열을 알고리즘으로 구현하는 방법을 알아보았다.오늘은 조합에 대해서 알아보고 알고리즘을 구현해 보자.조합 조합이란 Combination이라고도 하며 순열과 마찬가지로 n개 중에서 r개를 고르는 경우의 수를 의미한다.순열과 다른 점은 순서를 고려하지 않는 다는 것이다.여기서 순서란 이런 의미이다.순열의 경우 1, 2, 3 중에서 2개를 고를 때 (1, 2), (1, 3), (2, 1) ... 순서로 1과 2를 뽑았더라도 나중에 2와 1 순서로 다시 한 번 뽑을 수 있는 것이다.하지만 조합은 (1, 2)와 (2, 1)를 같은 것으로 본다.그러므로 1, 2, 3 중에서 2개를 고른다면 조합은 (1, 2), (2, 3), (3, 1) 3개의 ..
2024. 12. 26.
[C/C++] 순열과 조합 알고리즘 구현하기 1
고등학생 때 배우는 내용 중 순열과 조합이 있다.흔히 nCr, nPr이라고 부르는데, 오늘은 순열에 대해서 먼저 공부하자.최근 조합론을 공부하면서 순열과 조합에 대해서 다시 살펴보게 되었다.한 번 공부해두면 프로그래밍을 하는데 큰 도움이 되니 꼭 숙지하도록 하자.순열 nPr 순열은 Permutation이라고도 하며, n개의 숫자 중 r개를 고를 경우의 수를 의미한다.예를 들어 1, 2, 3 중 2개의 숫자를 고른다고 가정해보자.(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 총 6개의 경우의 수가 있다.앞에서부터 한 개를 고르고, 나머지 숫자 중에서 차례대로 두 번째 숫자를 고른다.1을 고른 뒤 2, 3을 순차적으로 한 뒤에 2로 시작할 때 다시 1, 3을 고른다.r개..
2024. 12. 24.
