PS

순열, 조합, 중복순열, 중복조합 - 코드

순열 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하지 않고", "뽑는 순서를 고려하는" 것 1. DFS로 탐색 : O(nPr) 다만 이 경우는 중복이 있는 경우는 못 잡는다! // nPr의 경우 // arr : 순열할 원소, size n // visited[i] : arr[i]가 방문되었는지 여부, 초기값 false, size n // result : 순열 결과, size r void permutation(int depth, int r, vector& arr, vector& visited, vector& result){ if(depth == r){ for(int i : result){ cout

순열, 조합, 중복순열, 중복조합 - 개념

기본적으로 위 4개 개념은 다음과 같은 명제에서 시작한다. 서로 다른 공 n개가 든 상자에서 r개를 뽑는 경우의 수 이제 어떻게 뽑느냐가 결정을 하는데, 뽑는 순서를 고려한다면 순열, 그렇지 않다면 조합이다. 또한, 중복을 허용하는 것과 그렇지 않은 것으로 나눈다. 그래서 2 * 2, 총 4개의 개념이 있는 것이다. 이 때, 중복을 허용한다는 것은 공을 뽑고, 다시 복원한다고 생각하면 될 것이다. 순열 - "중복을 허용하지 않고", "뽑는 순서를 고려함" 조합 - "중복을 허용하지 않고", "뽑는 순서를 고려하지 않음" 중복순열 - "중복을 허용하고", "뽑는 순서를 고려함" 중복조합 - "중복을 허용하고", "뽑는 순서를 고려하지 않음" 순열 개념 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 ..

sort 시 seg fault발생 - strict weak ordering

지난주에 programmers lv1 실패율 문제를 풀다가 seg fault가 났었다. 내가 알던 seg fault는 잘못된 memory에 접근하는 경우에 생겼기 때문에 vector의 index를 잘못 참조하지 않는지 확인했지만 아무리 봐도 그런 경우가 없었다. 그래서 이것저것 디버깅을 해 보다가 sort 함수를 빼면 seg fault가 안 나는 것을 확인했고, 그러다가 결국 정렬 함수에 문제가 있다는 것을 알게 되었다. 아래는 내가 쓴 코드다. #include #include #include #include using namespace std; typedef pair pid; bool comp(pair& a, pair& b){ if(a.second > b.second) return true; else{..

빠른 거듭제곱 Fast Exponentiation (+ 피보나치 수)

빠른 거듭제곱 : O(log(exp)) a^b을 구할 때, simple하게는 a를 b번 곱하면 된다. 그러나 b가 너무 커져버릴 경우에는 시간 안에 연산을 끝내지 못할 수도 있다. 이 때 사용하는 게 빠른 거듭제곱 알고리즘이다. divide and conquer 방식을 사용하는 것으로, $a^{b}$에서 b가 홀수라면 $a^{b} = a^{\tfrac{b}{2}} \times a^{\tfrac{b}{2}} \times a$ b가 짝수라면 $a^{b} = a^{\tfrac{b}{2}} \times a^{\tfrac{b}{2}}$ 를 반복해, b가 0이 될 때까지 반복하는 알고리즘이다. top case부터 b=0인 base case까지 귀납적으로 보이면 되고, $\tfrac{b}{2} + \tfrac{b}{..

행렬곱 알고리즘

1. 일반적인 행렬곱 : $O(n^{3})$ vector solution(vector arr1, vector arr2) { int row1 = arr1.size(), col1 = arr1[0].size(); // = row2 int col2 = arr2[0].size(); vector answer(row1, vector(col2, 0)); for(int i =0; i

약수, 소인수분해, 최대공약수/최소공배수 알고리즘

약수 1. Simplest Version : $O(n)$ set getFactorNumber(int n){ set v; for(int i = 1; i

소수 판정 알고리즘

소수 판정 알고리즘 1. 1개의 수만 판정할 때 : $O(n^{0.5})$ bool isPrime(int n){ if(n

2020/07/08 공부 - dynamic programming

오늘은 LIS 쪽 문제를 풀었다. 먼저 11053번. LIS의 제일 기본이 되는 문젠데, 이 문제는 n square로 풀어도 되지만 어차피 DP를 배우니까 nlogn으로 풀었다. 다른 DP 문제와 동일하게, 일단 memoization을 위해 몇 가지 array를 만든다. 내 코드에서는 DP는 각 index별로 최대 length를 저장하는 곳, LIS_array에는 LIS를 저장하는 곳으로 두었다. DP[i]에는 input vector의 index i까지 LIS를 저장해 두었다고 가정하고, 새 index i+1을 볼 때는 2가지 경우의 수가 있다. 먼저 input[i+1]이 지금까지의 LIS_array의 마지막 항보다 큰 경우는 바로 LIS_array vector의 마지막에 추가하면 된다. 반면 마지막 항..

2020/07/07 공부 - dynamic programming

어제에 이어서 DP 공부를 했다. 작년 이맘쯤에 객체지향 프로그래밍 첫 과제로 BFS와 LIS가 나왔었는데, 당시 BFS는 이해했는데 LIS는 이해를 잘 못했었다. 그 해 여름방학 관심 생겨서 공부했을 때도 다른 DP는 점화식으로 어떻게 풀었는데 LIS와 냅색은 잘 이해하지 못했었던 기억이 있다. 각설하고, 오늘은 문제를 몇 개 풀었다. 먼저 1463번. 1로 만드는 데 몇 번의 연산이 필요하냐는 문제이다. DP의 정석으로, 필요한 것은 미리 계산해 두고, 점화식에서 이 미리 계산해둔 것들을 불러오는 방식을 취한다. void solve() { int N; cin >> N; vector make_one(N+1); make_one[0] = 0; make_one[1] = 0; if (N >= 2)make_on..

2020/07/06 공부 - dynamic programming

backtrack을 끝내고 이제 DP를 해볼 차례다. DP는 원래 n square의 시간복잡도가 걸리는 일을 2가지 방법을 이용해 n에 linear하게 수행할 수 있도록 해주는 기법 중 하나이다. 이 2가지 방법은 첫째, 현재의 state로 미래의 state를 계산해 주는 점화식 둘째, 이미 계산했던 값이라면 계산했던 값을 사용하는 memoization 두 가지를 사용한다. 대표적으로 DP를 사용해서 시간을 줄일 수 있는 것이 조합이다. nCr에서 파스칼의 삼각형 특징을 이용해서 복잡한 계산을 조금 간단하게 줄일 수 있는데, 순열 점화식 $_nC_0=_nC_n=1$ $_nC_r=_{n-1}C_{r-1}+_{n-1}C_r$ 에서 2번째 점화식의 우항 부분이 계산되어 있다면 이를 저장해둔 후, 필요할 때 불..

2020/07/06 공부 - backtracking

오늘은 backtrack 마지막 문제, 스타트와 링크를 풀었다. 총 N명의 사람 중 N/2명을 고르는 것이므로 $_nC_{n/2}$ 만큼의 경우의 수를 봐 주어야 한다. 총 1부터 8까지 사람이 있으면 1 2 3 4 1 2 3 5 1 2 3 6 1 2 3 7 1 2 3 8 1 2 4 5 1 2 4 6 1 2 4 7 ... 2 3 4 5 2 3 4 6 ... 대충 이런식으로 조합 경우의 수가 정해지기 때문에, 제일 최근에 탐색한 사람 다음 사람부터 DFS를 실행했다. 그리고 N이 짝수인 것은 보장되었기 때문에 depth가 N/2가 되면 점수 계산을 진행한다. 조금 더 깔끔한 코드도 존재할 수 있겠지만 아직 그 정도의 실력이 안 되는 것 같다. 전체적인 구조는 다른 backtrack 문제들과 동일하다. de..

2020/07/04 공부 - backtracking

오늘은 저번에 이어 backtrack의 다른 예제를 풀었다. 백준 2580번 스도쿠이다. 내가 알고 있는 CSP와 굉장히 유사한 문제이기 때문에 backtrack으로 푸는 것이 좋다. 숫자를 채워 넣을 때 lookahead 등의 heuristics를 쓸 수도 있지만 귀찮아서 순서대로 채워 넣었다. 먼저 backtrack의 pseudo code는 다음과 같았다. 이 pseudo code를 따라가면 코드를 완성할 수 있다. DFS(list, depth, N) { if (depth == N) return; else { if (bounding_function() == true) DFS(list, depth + 1, N) else return; } } DFS(list, 0, N) 스도쿠에서 boundnig fun..

2020/07/02 공부 - backtracking

방학 때 공부해서 ACM-ICPC에 나가려 팀을 모았는데, 어쩌다 팀이 터졌다. 그래서 카카오 코페나 SCPC같은 것들만 조금 해 보려 한다. 글에 한글과 영어를 많이 혼용하는데, 영어 수업을 듣다보니 이게 더 편해졌다. 이번 학기 AI 수업을 들으면서 배웠던 backtracking을 조금 복습했다. backtracking은 CSP를 풀기 위해 나온 알고리즘이다. '순서'가 중요하지 않기 때문에, 내 맘대로 순서를 설정해도 되기 때문에 재귀를 이용한 DFS로 구현한다.(queue로 구현해도 되는데 재귀는 알아서 stack이 만들어지는 반면 queue는 내가 직접 만들어 줘야 해서 귀찮다. 시간복잡도에 유의미한 차이가 있는 것도 아니고) 또 brute-force와 비슷한데, 특정 조건을 만족하지 않으면 다..