본문 바로가기

전체 글

 (163)
알고리즘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-2 Divide and Conquer 입력을 나누어 더 작은 문제를 풀고 작은 문제들의 답을 조합하여 전체 문제의 답을 만든다. 아주 작은 문제는 어쨌든 풀린다. 어떻게 나누지?? Recursive Merge Sort n log(n) 모든 것을 다 sort할 수 있는 알고리즘(Comparison Model) 중에 n log(n)는 없다. 같은 값이 있으면 먼저나온 것이 더 작다라고 하면 비교가능 가능한 n!가지 중 어느 것인지 알아낸다 = sorting a(i) log N번 질문해야 한다. = n log(n) Why Quick Sort? annotation상에서는 m..
알고리즘9 "성능이 어떻게 나오냐"를 이유를 가지고 얘기할 수 있다! 엔진에서 불가능한 수준의 힘이 나온다. => 급발진 ECU : 신호만 공급하는 전력도 얼마 안쓰는 전자회로 "프로그램을 이렇게 짜면 빨라" 이유가 있어야 한다. Tape Storage 비교적 간단한 그리드 알고리즘 테이프에 데이터를 저장한다. (테이프: 데이터를 저장하는 1차원 장소로 사이즈가 다른 데이터 덩어리들을 저장한다.) N개의 길이가 다른 데이터 아이템이 있다. L: 사이즈 F: 몇번이나 자주 사용되느냐 (현실적으로 추정치) 추가,삭제 없이 한번에 저장되어 있다. 읽는 건 빠르지만 찾는 과정이 느리다. * 한번 읽고나면 무조건 앞으로 돌아간다. (이 조건이 없다면 굉장히 어려운 문제가 된다.) -> 직전에 어디를 읽었는지와 상관이 없다...
알고리즘8-2 O(N^2) 처음에 다 넣어놓고 1번job, 2번job넣기 ...... 빈자리가 있냐 없냐 알아야 하고, 빈자리 중에 가장 오른쪽 찾아야 한다. (쭉 다 보고 빈자리 있으면 넣고 아니면 버리고) 특정한 자리에 스케줄이 되면 죽는다. 살아 있는 자리들 중에 얼마 이하인 것중에 제일 큰 것 찾기 AVL Tree, Red-Black Tree (밸런스 트리) 바이너리 서치 트리 처음엔 다 살아있으므로 모든 값 BST insert O(n) x 스케줄되면 죽는다 BST delete O(log n) => 트리에 있는 값들은 아직 안들어간 애들 = O(nlog n) 살아 있는 것 중 일정 값 이하 중에 제일 큰 거 찾기 있는 값이면 그냥 그 값을 찾아서 들어감 ex) 14 10 > 15 14 ex) 12 ..
알고리즘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 처음에 하나만 확정 여기서 레드 노드가 추가될 때마다 하나씩 마킹해주면 됨 우선순위 큐를 쓰면 된다. 작은 것부터 나오는 큐 방금 추가된 노드와 직접 연결된 노드만 고려하자. 지..
알고리즘6-2 Djikstra Algorithm 다익스트라 알고리즘 앞의 내용 요약 - (not R)파란 것 중에 파란 값이 가장 작은 것을 찾아 u라고 하자 - R집합에 u를 넣자 작은 순서대로 15넣고 17넣고 19넣고 20 넣으면 끝나는 거 아냐? ㄴㄴ 빨간 집합이 업데이트되었으므로(15노드 추가) 밖의 숫자들도 업데이트 해줘야 한다. 현재 dmin(u) = 15 (지금 들어간 값) 둘 중에 더 좋은 걸 집어넣어야 한다.(현재 값 or 지금 들어간 값+엣지의 weight) 즉, 원래 집합에서 가장 좋은 값(0,8,10집합에서 가장 가까운 17) vs (새로 추가된 노드를 포함한 0,8,10,15집합에서 가장 좋은 값) 다익스트라 알고리즘의 주장: 방금 추가된 노드와 연결된 노드만 업데이트하겠다 예를 들면 15와 인접한 17,19노드를 이렇게 업데..

티스토리툴바