해나의 컴공생존기

1. Problem Definition J1, J2,...,JN 이라고 표기되는 N개의 job이 있다. 각 J는 (D,P) 로 쓰이는데, D는 deadline이고 P는Profit 이다. 1시간 단위의 타임슬롯이 있고 모든 일은 1시간이 소요된다 ex) (2,2) , (1,3), (1,1) 또, 이 문제는 아래의 가정을 따른다. 모든 deadlines은 N이하라고 가정한다. (N보다 크면 N으로 생각해도 됨) Job들은 내림차순으로 정렬되어있다. Deadline 이후의 일은 안나온다고 가정한다. 직관적으로 보면, 이익이 큰 것부터 최대한 뒤쪽에 배치하는 것이 효율적인 것을 알 수 있다. 최대한 뒤쪽에 두는것이 다른 Job들에게 방해가 될 가능성이 적어보이기 때문이다. 이것도 Greedy 알고리즘이다. 2...

1. Shortest Path 시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다. shortest path의 모든 부분은 shortest path이다. 이는 여러가지 버전이 있다. 길이만 구하기 길이와 Path 구하기 가능한 여러개의 Path 구하기 2. Dijkstra Algorithm 이 알고리즘에 대해 설명해보겠다. 먼저 몇가지 정의를 하고가면 R: 정답이 확정된 노드들의 집합 B: Red Set에 있는 노드들만 거쳐서 갈 수 있는 노드들의 집합 Dmin : 최단거리 1) 먼저 시작 노드부터 각 노드까지의 weight를 dim에 기록한다. 연결이 되어있지 않으면 ∞라고 기록된다. 2) 시작 노드를 R에 넣고 아래의 과정을 반복한다 R 밖에 있는 Dmin(u)들 중 가장 작은..

1. greedy Algorithm greedy 알고리즘은 선택을 반복하는 알고리즘들 중 비교적 간단하게 선택하고 선택한 것은 바꾸지 않는 알고리즘이다. 2. Minimum Spanning Tree (MST) Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다. MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프이다. (단, 사이클을 생성X) 사이클이 있으면 안되는 이유는 사이클이 없어도 되기 때문이다. 사이클이 중 하나를 없애도 연결그래프는 유지가 된다. 게다가 비용까지 감소가 된다. 우리는 '최소'를 찾고 있으므로 사이클이 있을필요가 없다. 아니, 있으면 안된다. 3. Prim Algorithm 프림 알고리즘의 아이디어는 먼저 ..

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..

1. Binary Search 이진탐색트리 코드이다. l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다. 기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다. 처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다. 탐색은 l과 r이 만나면 종료된다. m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다. 1) n=2 l=0, r=1, m=0 으로 모두 탐색 가능하고 2) n-3 l=0, r=2, m=1 으로 모두 탐색 가능하다 a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다. 왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 ..