알고리즘 (54) 썸네일형 리스트형 알고리즘13 Plane Sweeping - Right Hull Only * 지금까지 본 점들의 Right Hull이 계산되어 있다고 믿는다. 새로 들어온 점은 더 오른쪽에 있기 떄문에 무조건 convex에 들어가게 될 것 중간의 점들이 사라지게 될 수 있다. 따라서 접선을 찾는다. (기하문제에서는 점 3개가 일직선에 있지 않는다. x좌표, y좌표가 다 다르다고 생각한다.) right hull이 있고 오른쪽 점이 있다. (여태까지 본 x좌표 중 가장 큼) 접선을 구한다. (가장 모든 점을 쳐다봤을 때 가장 위쪽&가장 아래쪽이 접선이 된다,) 새로운 convex hull이 생긴다, (x표시가 빠짐) 더 밑에 점이 찍힌다면 위쪽 접선은 나오지만 밑은 다 사라지게 됨` 즉, 접선 2개를 구해야 한다. 전체 nlog n을 위.. 알고리즘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 남들보다 좋은 코드를 짜기 위해선 남들이 왜 이런 코드를 짰는지 알아야 한다. pivot의 왼쪽과 오른쪽이 비슷하면 n log n을 보장할 수 있지만 전혀 예상할 수 없는 상태이다. Q(n): n개를 퀵소트로 정렬하는 시간이라고 하자. Worst Case: pivot이 한 쪽 끝에 있는 경우 Q(n) = n + Q(n-1) => Q(n) = O(n^2) 어느경우에도 worst case는 피할 수 없다(너무 긴 얘기) Best Case: 반으로 잘라지는 경우 Q(n) = n + 2Q(n/2) => Q(n) = O(n log n) Average Case: 모든 가능한 경우가 동일한 확률로 들어온다. 현재 compansion model이므로 비교만하면 된다. 1, 3, 2 / 2, 7, 4 => 같다. 1, .. 알고리즘9 "성능이 어떻게 나오냐"를 이유를 가지고 얘기할 수 있다! 엔진에서 불가능한 수준의 힘이 나온다. => 급발진 ECU : 신호만 공급하는 전력도 얼마 안쓰는 전자회로 "프로그램을 이렇게 짜면 빨라" 이유가 있어야 한다. Tape Storage 비교적 간단한 그리드 알고리즘 테이프에 데이터를 저장한다. (테이프: 데이터를 저장하는 1차원 장소로 사이즈가 다른 데이터 덩어리들을 저장한다.) N개의 길이가 다른 데이터 아이템이 있다. L: 사이즈 F: 몇번이나 자주 사용되느냐 (현실적으로 추정치) 추가,삭제 없이 한번에 저장되어 있다. 읽는 건 빠르지만 찾는 과정이 느리다. * 한번 읽고나면 무조건 앞으로 돌아간다. (이 조건이 없다면 굉장히 어려운 문제가 된다.) -> 직전에 어디를 읽었는지와 상관이 없다... 알고리즘8 Deadline Scheduling N개의 할일. 각 할일의 분량은 1시간 1시간동안 한 가지 일만 가능 (example: 데드라인이 전부 2이다. 1,2 슬롯 안에 다 넣어야 하는데 2개밖에 못 넣는다 3개를 다 넣을 수 없으므로 profit이 가장 높은 방법을 찾아야 한다.) => 이런 식의 직관을 코드로 바꾸기는 굉장히 어려움! 간단한 작전이 있다! 가정1 꼭 필요한 것 같지는 않지만, deadline이 n보다 큰 건 의미가 없다. 가정2 profit이 큰거부터! 문제에서 순서는 상관없지만(Set) 나중에 편하기 위해서 (데드라인이 같은 게 있으면 큰 거부터 해야하니까) 가정3 deadline 이후에 job이 등장하지 않는다. 데드라인 이후의 job을 지워도 profit이 똑같기 때문에 높은 이익을 가진 job부터 스케쥴을 한다 (이.. 알고리즘7-2 BFS 단점 : 엄청나게 느리다. 해결하면 결국 다익스트라 알고리즘이 된다. 0인 애들이 우선마킹~ 1 마킹~ 2 마킹~ 3 마킹~ 4 마킹 ~ ~ ~ 필요없는 계산을 줄일 수 있을까? 0 마킹~ 1 마킹~ 2 마킹~ 3 마킹~ 4 마킹~ 5 마킹~ 6 마킹~ 7 마킹~ 8 마킹~ 새로 임의로 추가한 노드말고 기존 노드가 마킹 되는 곳 임의 추가 노드는 스킵한다면 실제 노드만 작업 할 수 있을 것이다. 0 -> 3 알 수 있을까? 다음 번 의미 있는 라운드는 3번 더 감 , 6번 더 감 알 수 있다! 먼저나오는 것부터 해야하니까 당연히 3! 3을 마킹하면서 3+9 =12가 고려대상으로 들어간다. 당연히 6이 작으므로 6먼저! 6을 마킹하면서 6+4=10 & 6+2=8 들어간다. 의미 있는 라운드들을 넣고, 가장.. 알고리즘7 다익스트라, BFS 지난번까지 다익스트라의 정확성에 대한 하나의 설명 직관을 위한 설명 추가 그 전에 먼저 코드로 바꾸자. G를 입력으로 받아야 한다. G = (V, E, g) (노드set, 엣지set, 엣지마다 weight) 방법은 여러개! 엣지 순서대로, weight 순서대로 줄 수도 있고 노드노드 weight, 노드노드 weight로 줄 수도 있겠지 처음에 source노드와 연결된 노드는 모두 블루 노드로! 처음에는 다 무한대로 셋팅 시작노드는 V0 벡터나 링크드 리스트로 따라가면서 초기치를 바꾼다. (3,2)추가 Red set marking 처음에 하나만 확정 여기서 레드 노드가 추가될 때마다 하나씩 마킹해주면 됨 우선순위 큐를 쓰면 된다. 작은 것부터 나오는 큐 방금 추가된 노드와 직접 연결된 노드만 고려하자. 지.. 이전 1 2 3 4 5 6 7 다음
