전체보기
PS에서 Master Theorem
Master Theorem은 알고리즘의 동작 시간을 대략의 수행시간을 big O notation으로 계산하는 방법이다. 일반적으로 divide-and-conquer와 같은 recursion에서 자주 사용하며, 입력이 n개인 task를 문제를 입력이 n/b개인 a개의subtask로 나눴을 때, 그 subtask를 f(n)만에 해결할 수 있다면 아래 식과 같이 표현한다. $T(n) = aT(\frac{n}{b}) + f(n)$ (단, a >= 1, b > 1, p >= 0) Master Theorem은 T(n)에 관한 점화식을 푼다. 그러나 대부분의 PS에서 f(n)은 $\Theta(n^{k}log^{p}n)$으로 정의되니, 이 식에서 답을 도출해 볼 것이다. 1. if $log_{b}a < k (\Left..
이진탐색 Binary Search, Lower/Upper Bound, Parametric Search
이진 탐색 : O(logn) 개념 Binary search는 정렬된 array에서 어떤 값 k를 찾는 방법이다. 이 또한 divide and conquer를 사용하는 방식으로, 재귀방정식을 세우면 아래와 같다. $T\left(n\right)\ =\ T\left(\frac{n}{2}\right)\ +\ c$ 따라서 시간복잡도는 O(logn). 다른 방식으로, 처음 n개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다. 다음 n/2개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다. ... 마지막 것이 탐색된다. 즉, n개의 input이 있을 때 탐색은 logn번 진행한다. 반복문으로 탐색 : O(logn) int search(vector& v, int input){ int star..
순열, 조합, 중복순열, 중복조합 - 코드
순열 서로 다른 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개를 뽑을 때, "중복을 ..
Docker + (Spring Boot + VS Code) 준비 단계
0. Docker 설치 Windows subsystem for Linux인가 뭐시긴가 이게 없어서 자꾸 docker 실행에서 에러가 났다. Ctrl + Shift + Esc - 성능 - CPU - 가상화 : 사용 으로 나와있어야 한다. 나는 분명 Windows 기능 켜기/끄기에서 WSL, 가상환경 다 체크해놨는데 에러 나서, 찾아봤더니 Bios 화면에서 설정을 해주니까 되더라. 그리고 WSL 에러나길래 2로 업그레이드 해주니까 잘 되었다. 이 컴퓨터에서 개발환경 아무것도 안 만들어둬서, 아마 다음 번 초기 설정에도 이렇게 하면 될 것이다. 1. vs code + spring 설정 https://sambalim.tistory.com/67 위 블로그 보면서 VS code + spring local 환경을 구..
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
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와 비슷한데, 특정 조건을 만족하지 않으면 다..
[GCP Tutorial] GCP + Code Server
https://sionuu.com/amazon%20web%20service/2020/11/17/code-server/ 이 분의 글을 많이 참고했다. 1. Install Nginx, Code Server on GCP VM Instance programmers에 있는 문제들을 lv3까지 문제들을 거의 다 풀어서 이제 baekjoon이나 codeforce 등의 다른 ps 사이트로 넘어가야 한다. 그러기 위해서 c++ 실행환경을 갖춰야 한다. 언제까지고 online gdb c++을 쓸 수는 없으니까. 그래서 GCP에 VS Code Server를 올려서 c++ 개발/디버깅 환경을 갖추고자 한다. AWS를 하지 않고 GCP를 한 이유는 GCP는 37만원 상당의 무료 크레딧을 주기 때문이다. 유료 회원으로 업그레이드..