MIT - Introduction to Algorithms
- Lecture 1 : Algorithmic Thinking, Peak Finding
극댓값 찾기 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
1. Efficient procedures for solving large scale problems
2. Scalability : 확장성 ((사용자 수의 증대에 유연하게 대응할 수 있는 정도))
- 시간에 따라 큰 입력의 정의는 달라지겠지만으로 큰 입력이 주어졌을 때 효율적인 복잡도가 낮게끔 알고리즘을 구성하는 것이 중요
3. Classic data structure & classical algorithms
(binary search tree, hash table(dict) etc)
4. Read Implementation in Python
- 이론과 실습으로 나뉘어져 있음
연습문제 제공(어렵지만 보람있는 과제)
Content
8 modules : 각각 연습문제가 있음
1. Algorithmic thinking : Peak Finding
복잡도 분석, 효율성을 따져서 증명해야하는 연습문제의 과정
2. Sorting & Trees : Event Simulation
가장 흔한 트리는 이진 트리, Scheduling ...
3. Hashing : Genome Comparision
인간 게놈과 쥐 게놈이 99% 비슷하다 그러나 너무 크기 때문에 효율적인 비교법을 사용해야한다. 복잡도를 낮춰야 프로그램이 완료될 것
4. Numerics : RSA encryption
32 bits로 표현하기 어려운 SSL에서 사용하는 RSA 암호화, https backend로 RSA 사용 어떻게 다뤄야할까
5. Graph : Rubik's Cube 2x2x2
컴퓨터 과학의 핵심적인 자료구조
6. Shortest Paths : Caltech -> MIT
이번에는 보스턴 지도를 주고 Paul Revere 목적지까지 갔는가에 최단 경로을 해볼 것
7. Dynamic programming : Image Compression
8. Advanced Topics
Peak Finding
One - dimensional version
Position 2 is a peak if and only if $b\ge a$ and $b \ge c$
Position 9 is a peak if $i \ge h$
끝이기 때문에 하나만 비교
Problem : Find the peak if it exists(항상 존재하는가?)
Straghtforward algorithm
Start from left
왜 문제에 존재하냐 exist라는 표현을 썼는가
any arrays will have the peak 항상 존재하지만 그 존재의 증명을 바람
극대값의 정의가 단순히 크기만 했다면 어땠을가하는 생각
Look at n/2 elements
Worst case complexity : $\theta(n)$
1번부터 n번까지 전체 다 봐야하므로 $\theta(n)$
asymptotic complexity 점근적 복잡도는 여기서 선형
cf) asymptotic 점근선의
더 좋은 복잡도를 찾는 방법은?
=> 중간에서부터 찾으면 좌우 중 하나를 절삭해낼 수 있기 때문에 복잡도가 줄어듭니다.
Recursive Algorithm 재귀 알고리즘을 수행
Divide & Conquer
Look at n/2 position
왼쪽 -> 오른쪽
if a[n/2] < a[n/2-1] then only look at left half 1 ~ (n/2-1) to look for a peak.
peak의 존재를 1개만 찾으면 되므로 위 조건하의 단계를 수행
else if a[n/2] < a[n/2+1] then look at (n/2+1) ~ n to look for a peak
else n/2 position is a peak
$T(n) = T(n/2) + \theta(1)$
base case $T(1) = \theta(1)$
$T(n) = \theta(1) \cdots \theta(1) = \theta(log_2n)$
이것을 재귀적으로 반복실행하기 때문에 위와 같은 식이 나옴
$\theta(1)$ : 왼쪽과 오른쪽을 확인하여 두 번의 비교 연산을 실행하는 시간
2는 상수이므로 $\theta(1)$
n = 1000만일 경우 초기$\theta(n)$ = 13s
$\theta(log_2n)$ = 0.001s
2D version - n x m
a is a 2D-peak if $a \ge b, a \ge d, a \ge c, a \ge e$
Greedy Ascent Algorithm : Worst Complexity : $\theta(nm)$
n x m 전체를 도는 경우를 생각하므로 위와 같은 복잡도가 나옴
$\theta(n^2)$ if m = n
Attempt 1 Divide & Conquer
Pick middle column j=m/2
Find a 1D-peak at (i,j)
Use (i,j) as a start to find a 1D-peak on row i
=> Efficient but Incorrect
정확하고 비효율적인 것이 부정확하고 효율적인 것 보다 낫습니다.
문제에 대한 답이 맞는 것이 우선!
Problem : 2D peak may not exist on row i
12가 존재하는 열에서부터 시작한다고 가정한다면 우리는 12가 11,10보다 크므로 12가 존재하는 행에서 다시 1D-peak 찾기 방식을 구현할 것이고 14가 극댓값으로 선택될 것입니다.
14 is not a 2D-peak
Pick middle column j=m/2
j 열일 때, i가 바뀌면서 최대가 되는 행의 값을 찾습니다.
Compare (i, j − 1), (i, j), (i, j + 1)
Pick left columns of (i, j − 1) > (i, j)
Similarly for right
If (i,j) $\ge$ (i,j-1), (i,j+1) => (i,j) is a 2D peak
Solve the new problem with half the number of columns. 재귀한다는 의미
When you have a single column, find global maximum and you‘re done.
$T(n,m) = T(n,m/2) + \theta(n)$
$\theta(n)$는 해당 열 전체 중 최댓값을 찾아야하므로 생기는 값
$T(n,1) = \theta(n) \cdots \theta(n) = \theta(nlog_2m)$
주어진 숙제
Analyze the Algorithm => 맞는 것은 증명, 맞지 않는 것은 반례를 찾습니다
