분류 전체보기98 [1708번] 볼록 껍질(Convex Hull) 링크 : https://www.acmicpc.net/problem/1708대표적인 기하알고리즘 문제풀이 방법은 보통 3가지가 있다.1. Jarvis March 알고리즘 : O(NH)1) 주어진 정점에서 극단점 중 하나를 찾는다.(극단점 : 볼록 외피의 정점이 되는 점, 보통 x좌표나 y좌표가 제일 크거나 작은점을 선택한다. 이 점들은 반드시 극단점에 포함된다.)2) 다음 극단점 찾기 : 현재까지 찾은 마지막 극단점 다음에 올 극단점을 모든 점을 보면서 탐색3) 찾은 극단점이 처음 찾은 극단점일 떄 까지 반복2. Graham Scan 알고리즘 : O(NlogN)1) 시작점으로 사용할 극단점 선택2) 시작점을 (0,0)기준으로 모든 점을 평행이동.3) 각 점들을 각도 정렬해서 각도가 적은 순서대로 방문4) .. 2019. 8. 13. [11758번] ccw 링크 : https://www.acmicpc.net/problem/11758 1234567891011121314151617181920212223#include using namespace std; int ccw(paira, pairb,pairc) { int tmp1 = a.first*b.second + b.first*c.second + c.first*a.second; int tmp2 = a.second*b.first + b.second*c.first + c.second*a.first; int ans = tmp1 - tmp2; if (ans x >> y; tmp[i] = { x,y }; } cout 2019. 8. 13. [2133번] 타일 채우기 2133번: 타일 채우기 www.acmicpc.net 가로가 N, 세로가 3인 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제다. 간단한 DP 예제 중 하나다. 가로가 1일 때, 채울 수 있는 경우의 수는 0이다. 그렇기 때문에 N이 홀수 일 경우 벽을 채울 수 없다. 가로가 2일 때, 채울 수 있는 경우의 수는 3이다. 가로가 4일 때, 가로가 2인 경우를 2번 계산하면 되겠다고 생각하겠지만 예외적인 모양이 존재한다. 맨 아래 2개의 경우가 가로가 2일 때와는 다른 모양으로 채울수 있는 경우인데 이런 경우가 N이 증가할 수록 늘어난다. 규칙을 찾아보면 아래와 같이나온다. 이 규칙으로 점화식을 만들어 보면 경우의 수 = A[N-2] * 3 + (* 2)가 된다. (에서 .. 2019. 6. 11. K-d tree vs Brute-force 탐색 속도비교 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816.. 2019. 6. 7. 이전 1 ··· 6 7 8 9 10 11 12 ··· 25 다음
