1. Peak FInding

• One - Dimensional Version / Two - Dimensional Version

• Straightforward Algorithm(Brute force Algorithm) - O(n)

• Linear Search(nearly Binary Search/divide and conqure)

• How to Solve the Problems Efficiently

  (1) How did you organize your problems when you got the problem (2) How did you analyze time complexity (3) Which algorithm (straight forward, divide and square) is applied

1. Algorithms

• Sort - Why sorting?

  (1) Obvious Sorting (2) Problems that become easy once items are in sorted order (3) Non-Obvious applications

• Insertion Sort

  — pseudo sort: 특정 언어에 종속적이지 않게 알고리즘을 표현하는 방법(ex: (A,n), for j ← 2 to n)

  for j ← 2 to n insert key A[j] into the (already sorted_ sub-array A[1…j-1] by pariwise key - swaps down to its right positions

  lim n→infinite n(n-1) / 2 = O(n^2)

• Binary Insertion Sort → O(log n)

• Merge Sort

Divide and Conquer: 문제를 쪼개고 합치는 과정을 통해 해결

O(n log n)

(1) n = 1, done (2) Recursively sor A[1…(n/2)] amd A[n/2…n] (3) Merge the two sorted lists

T(n) = 2 * T(n/2) + c * n (where c > 0 is constant)

1. Heap

• Implenetation of Priority Queue
• nearly complete binary tree
• Max Heap Property: The key of a node(노드의 값) is ≥ them the keys of its children