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

- 중복 조합 중복을 허용하여 원소를 선택하는 조합. 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)! 이 된다..

외판원 순회 문제 - 여러 도시가 있고 도시 간 이동 비용이 있을 때 모든 도시를 한 번씩만 방문하여 시작 위치로 돌아오는 경로의 최소 비용을 구하는 문제. 각 도시가 20개라하면 20개의 도시를 모두 방문하는 경우의 수는 20! 이 된다. 모두 계산하지 않고 bitmask + memoization을 이용한다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 왜 dp[12 의 경로를 탐색하고 dp[101]의..

LIS 구현 1. lower bound 사용하여, 2. 새로운 값 x가 기존 lower bound 배열의 가장 큰 값보다 크면 뒤에 추가 기존 lower bound 배열에서 x보다 같거나 큰 값 중 첫 번째를 찾아 업데이트 해준다. 즉 F, F, ... F, T, .. T 인 분포에서 x

풀이를 안 보고 풀진 못 했다. 해답이 많이 올라와 있지만 스스로 정리를 하며 기억하기 위해 작성해본다. 1. 문제 https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 1번부터 N번까지 원형으로 앉아있고 K번째 마다 제거 할 때, 마지막에 남은 번호를 구하는 문제. 1 > n >> k; int ans = 1; for(int i=2; i

예전에 어떤 알파벳은 특정 알파벳 다음에만 올 수 있다는 규칙의 문제와 같다 (ex u는 e,i,o 다음에 올 수있고 e 는 a,u,o 다음에 올 수있고..) 특정시점의 어느 위치는 그 바로 이전의 연결된 위치에서만 올 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include #include #include #include #include #include #define INF 1e9 #define MOD 1000000007 using namespace..

모든조합, 즉 완탐하면 5000*5000*5000으로 터진다(아마) 모든 기준점(mid)에 대해 투포인터로 탐색하면 되는데 이 경우 O(n^2)으로 가능하다. 정렬 후 세용액의 합이 0보다 클때 그 시점의 right보다 큰 값은 탐색할 필요가없다 당연히 현재 세용액의 합보다 더 클테니 반대로 세용액의 합이 0보다 작을때는 그 시점의 left보다 작은 값은 탐색할 필요가 없다. 결론 투포인터 응용문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include..