본문 바로가기

전체 글

 (163)
14-2 15-1 추가된 내용 전형적인 동적 프로그래밍 문제 일하면 받는 돈이 써있다. 단, 연속된 날은 일할 수 없다. 마지막 날이 일할 수도, 안할 수도 있다. 마지막날에 일하는 날 중 제일 좋은 답이 있을 것이고 마지막날에 일 안하는 날 중 제일 좋은 답이 있을 것이다. 마지막 전날은 마지막 날에 영향을 받는다. 마지막 날을 제외하고 가장 좋은 답을 구하기 둘 중 하나는 제일 좋은 답일 것이다. 앞에서부터 계산해두면 뒤에서 사용할 수 있다. 인덱스0: 그 날 일을 안하는 것중에 제일 좋은 것 인덱스1: 그 날 일을 하는 것중에 제일 좋은 것 배열 생성하고 첫 날 일을 할 때&안할 때의 초기값을 넣어준다. day2부터 계산한다.{ 그 날 일을 안할 때 = MAX(그 전날 일 할때 , 그 전날 일 안할때) 그 ..
14 Dynamic Programming Dynamic Programming 굉장히 어려운 문제가 쉽게 풀리게 해준다. 어떨 때 사용할 수 있는지, 어떻게 동작하는지를 알기 위해 큰 틀을 보겠다. 기본적으로 재귀 재귀는 독립적으로 실행할 수 있어야 한다. 전체 문제가 있고 잘라서 자른 문제가 전체인 것처럼 동작한다. 머지소트는 왼쪽 배열이 오른쪽배열의 영향을 받지 않는다. 하지만 그래프와 같은 경우는 영향을 받을 수 밖에 없다 완전히 독립적으로 잘라서 재귀로 적용하기 힘들다. 독립적인 부분문제의 답으로 전체의 답을 만든다는 점에서 분할정복과 비슷하지만 재사용에서 다르다. 피보나치에서 F(n)의 값은 변하지 않는다. F(6) = F(5) + F(4) F(7) = F(6) + F(5) 여러 곳에서 쓰이지만 F(5)의 값은 같다. By Recursi..
알고리즘13-2 Matrix Multiplication nxn 행렬 두개를 곱하면 계산할 값 = n^2개 하나 계산하는 데에 n개의 계산 => 덧셈말고 곱셈만 고려했을 때 O(n^3) 같은 값이 곱해지는 경우가 없다! 더 빨리할 수 있는가? 실용적이진 않지만 특이한 방법 원래 행렬끼리 곱하듯이 재귀로 => 그냥 곱하는 것보다 느림 원래 n^3인데 분할정복해도 n^3? 더하기도 계산할 수 있지만 곱하기만 세겠다. R: 1 S: 1 T: 1 U: 1 V: 1 W: 1 X: 1 변수가 7개x곱하기 1번씩 곱하기8번 => 곱하기7번이 된다. 이 정도 차이가 의미가 있냐? 웬만하면 의미가 없지만 웬만하지 않은 곳이 많다. ex) 물리..과학 계산.. n^2보다 빠르게는 못한다. 입력, 출력사이즈가 n^2이기 떄문에. n^3보다는..
알고리즘13 Plane Sweeping - Right Hull Only * 지금까지 본 점들의 Right Hull이 계산되어 있다고 믿는다. 새로 들어온 점은 더 오른쪽에 있기 떄문에 무조건 convex에 들어가게 될 것 중간의 점들이 사라지게 될 수 있다. 따라서 접선을 찾는다. (기하문제에서는 점 3개가 일직선에 있지 않는다. x좌표, y좌표가 다 다르다고 생각한다.) right hull이 있고 오른쪽 점이 있다. (여태까지 본 x좌표 중 가장 큼) 접선을 구한다. (가장 모든 점을 쳐다봤을 때 가장 위쪽&가장 아래쪽이 접선이 된다,) 새로운 convex hull이 생긴다, (x표시가 빠짐) 더 밑에 점이 찍힌다면 위쪽 접선은 나오지만 밑은 다 사라지게 됨` 즉, 접선 2개를 구해야 한다. 전체 nlog n을 위..
알고리즘12-2 Convex Hull 전체가 볼록한 다각형 변의 길이가 가장 작아지고 면적도 제일 작아짐 느린 방법부터 생각해보자 N^3 convex위에 있는 선분을 직선으로 늘린다. 모든 점이 한쪽에 다 있으면 convex위에 있는 것 모든 점이 다 한쪽에 있다! 그림으로 보면 쉬운데 코드는 어떻게 짜지..? (설명을 편하게 하기 위한 가정) 1. 모든 X좌표는 다름 2. 모든 Y좌표도 다름 3. 한 직선 위에 3개 점이 있는 경우 없음 CCW (Counter-Clock-Wise) 시계반대방향 x좌표, y좌표가 다 다르다고 가정~ 기울기로 풀려고 한다. 여기에도 이 식이 똑같이 성립한다! (좌회전) 이 변을 테스트할 것임 우회전 좌회전 다른 모든 점들에 대해서 CCW를 돌리면 좌회전도 있고 우회전도 있을 것임 = 한 ..
알고리즘12 Plane Sweeping 다른 방법으로 풀어보는 가장 가까운 점 찾기~ divde&conquer는 아님! Plane Sweeping - 평면을 쓸다 그림으로 설명하기 어려운 문제 중 하나임 직선을 만들고 오른쪽으로 밀면서 풀겠다. 직선으로 미는 것을 컴퓨터로 어떻게 구현할 것인가? 실제 직선은 제일 왼쪽 끝 점에서 시작한다. 다음 점으로 jump => 직선을 총 n개를 왼쪽에서부터 순서대로 그리게 된다. 1. 직선을 x좌표로 sorting한다. n log n 직선 안에 어떤 자료구조가 저장이 되어 있다고 생각하자 왼쪽부분에 이 문제를 푸는데에 필요한 정보가 저장이 되어 있다. 문제마다 어떤 자료구조가 저장되어 있을 것인지 다르다. 여기까지 왔다고 치자. 2. 왼쪽 점부터 순서대로 (n번) 다음 점에 갔을 때, 재귀적으로(수학점 ..
알고리즘 11 기하문제를 현실에서 생각보다 많이 풀고 있다. 분할과 정복을 배우는 와중에 기하를 배우는 이유는 두 개의 방식으로 풀리는 알고리즘이 있기 떄문에 CLosest Pair: 가장 가까운 쌍 찾기 사람처럼 직관적으로 푸는 것은 힘들다. x,y좌표로 주어진다. (3,2) (3,7), (5,5) 직관 -> 숫자로 바꿀 수 있는 문제는 바꾸는 것이 좋다 기하문제의 특징: 같은 문제를 1차원,2차원,3차원에서 생각할 수 있다. 현실은 3차원이기 떄문에 3차원 문제를 풀 일이 종종 있다. 하지만 난이도는 크게 차이 난다. 2차원 기하도 의미있는 경우가 많기 떄문에 2차원을 많이 푼다! 1차원에서 먼저 생각해보자. 가장 가까운 점찾기와 가장 먼 점 찾기는 같은문제일까 다른문제일까? 다른문제이다. shortest는 빨리 ..
알고리즘10-2 pivot을 어떤걸 잡을 거냐? Selection을 해야 한다. Selection: n개 중에 k등을 찾을 것 minimum, maximum (selection보다 쉬운 문제인듯) median(중간값), selection sorting을 했다면 selection은 쉬운 문제이지만 quick sort에서 중간값을 찾기위해 sorting한다?? sorting없이 selection할 수 있을까? "k등이 x다" 만 알 수 있어야 한다. x보다 작은 수, 큰 수는 알 수 있지만 이들사이에 누가 크고작은지 모른다 => 알면 그게 sorting한 것 sorting엔 nlog n 시간이 필요하다. selection을 nlog n보다 작은 시간 안에 풀어야 한다. (아주 해피엔딩은 아닐 것임) The Approxima..

티스토리툴바