정리하기 위한 블로그 정리하기 위한 블로그

- 중복 조합 중복을 허용하여 원소를 선택하는 조합. n개의 원소를 r번 중복 허용하여 선택하는 경우의 수. nHr = n+r-1Cr 예를 들어보자. n개의 원소 {1,2,3,4,5}가 있다고 가정. 이때 3개를 중복 허용하여 선택한다고 하자. {1,1,1} , {1,1,2}, {1,1,3}, ... , {1,2,2} , {1,2,3} , ... , {5,5,5} 가 될 것이다. 조합이므로 순서 개념이 없으므로 {1,1,2}, {1,2,1}, {2,1,1} 은 하나의 경우로 취급. ( {1} 2개 , {2} 1개) - 왜 nHr = n+r-1Cr 일까? 위의 예를 든 5H3을 생각해보자. ㅁ ㅁ ㅁ 3개의 빈칸(r)과 / / / / 4개의 칸막이(n-1)가 있다고 생각. ㅁ ㅁ ㅁ / / / / -> 1..

permuation - 순서가 있는 경우의 수 combination - 순서 개념이 없는 조합의 경우의 수 permuation, combination 구현과 차이점 - permutaion은 탐색 시 처음 원소부터 다시 탐색. (3을 골라도 이후 재귀에서 1부터 다시 탐색) - combination은 탐색 시 현재 원소(idx)의 이후의 idx만 탐색. (3을 골랐으면 이후 재귀에서 4,5,6.. 만 고려) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmic..

용어에 대한 정리가 필요하여 작성. 백트래킹이란? - 모든 경우의 수를 전부 고려하는 알고리즘. 단 탐색 중에 유망하지 않은 경우에는 이전 단계로 돌아가서 다른 후보 탐색. 완전 탐색의 일종. 완전탐색(Bruteforce)과 백트래킹은 무엇이 다른가? - 완전탐색은 모든 경우의 수를 대입. 유망성을 검사하지 않음. 간단한 백트래킹 문제 하나. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 경우의 수는 nPr = n! / (n-r)! 이 된다..