** 평소 생각하던 문제 해결 전략들을 적어나갈 생각이다. 1. x좌표와 y좌표를 분리해서 생각하기x좌표만 있다고 생각하고 문제를 더 쉽게 풀어보고 이후에 y좌표를 추가하면 어떻게 풀 수 있는지 생각하는 접근 방법이다. 2. 순서를 강제하기주어진 문제가 임의의 순서를 추가 하였을 때 더 쉽게 접근할 수는 없는지 생각해보는 접근이다.보통 dp문제에서 많이 사용하는 접근 방법이다. 3. 주어진 문제를 반으로 나누기주어진 문제를 반으로 나누었을 때 왼쪽 범위에서 시작하고 오른쪽 범위에서 끝나는 답을 비교적 구하기 쉬운지 \(O(n)\)판단하여 분할정복으로 푸는 접근 방법이다. 4. 뒤에서부터 생각하기보통 앞에서 부터 결정하면 결정하기 난해한 문제들은 뒤에서부터 결정하였을 때 쉽게 풀리는 경우도 있다. 5. 일..
PS에서 사용하는 복잡도는 시간복잡도와 공간복잡도가 있다. 시간복잡도는 프로그램 수행시간을 분석하는 것이고 반복문에 크게 영향을 받는다.빅오 표기법에서 입력의 크기가 n일 때 주어진 프로그램의 수행시간이 \(5n^4-7n^3+n^2+4\) 의 식을 가진다면.최고차항의 계수와 그보다 낮은 차수의 항을 제외시켜 \(O(n^4)\)와 같이 표기한다.주어진 입력의 크기가 n이라고 하였을 때 아래와 같은 코드들은 각각의 시간 복잡도를 가진다. 주어진 순서대로 위가 가장 빠르다.PS에서 보통 1억을 1초로 잡고 계산한다.예를 들어 n이 1000이라면 6번 이하로는 가능한 알고리즘이다. 공간복잡도는 프로그램의 메모리 사용량을 분석하는 것이다.간단하게 사용한 배열의 크기 * (해당 자료형의 크기) 로 계산한다. 보통 ..
이분매칭 포드 풀커슨 \(O(VE)\) 이분매칭 호프크로프트 카프 \(O(\sqrt{v}E)\) a->b 형태로 매칭 한다고 하였을 때. 1. 매칭되지 않은 a 정점을 level 0으로 하여 bfs 한다. 2. b정점이 매칭되어 있고 (matched_b[b]!=-1) 해당하는 a 정점의 level이 정해지지 않았다면 (level[matched_b[b]]==-1) 해당 정점의 level을 갱신한다. (level[matched_b[b]]=level[a]+1) 3. 매칭되지 않은 모든 정점에서 dfs 한다. b정점이 매칭되지 않았거나, 매칭된 a정점의 level이 현재 정점 level+1이라면 새로운 증가경로를 탐색한다. (matched_b[b]==-1||(level[matched_b[b]]=level[a]+..
네트워크 플로우 포드풀커슨 \(min(O(Ef),O(VE^2))\)네트워크 플로우 디닉 \(O(V^2E)\) 1. 잔여용량이 존재하는 간선을 따라 BFS하면서 정점들의 level을 매겨준다. s가 level 0- t의 level이 정해지지 않는다면 더 이상 증가경로는 없음. (현재 유량이 최대 유량) 2. s부터 DFS하면서 t에 도달할 때 까지 항상 level[u]+1==level[v] 를 만족하는 edge만 따라서 이동한다.- DFS 종료 하면서 유량 갱신해주고 더 이상 증가경로가 없을 때 까지 반복한다.- DFS 시 추가적으로 현재 몇 번 간선까지 사용하였는지 저장하는 배열을 이용해서 불필요한 탐색을 줄인다. 3. 더 이상 증가 경로가 없다면 1.로 돌아간다.