해나의 컴공생존기

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. 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. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0]

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의 바로 전 인덱스로 설정되고 오른쪽 ..