알고리즘 개론 :15 시작 장준영 1

상/중/하상/중/하 상 – 나는 알고리즘을 매우 잘 알고, 좀 더 어려운 난 이도의 문제들을 보고 싶다. 중 – 어느정도 알고리즘을 구현해본 적이 있다. 하 – 알고리즘의 A 조차 모른다. 2

다룰 내용 3

이 발표의 목적 알고리즘 수업에 도움이 된다. 다양한 레벨의 알고리즘을 경험 – 필수적으로 알아야 하는 것 – 약간 난이도가 있는 문제들 – 매우 어려운 문제들 ( 수업에서 일부를 다룸 ) – 알고리즘 대회 4

알고리즘이 뭔가요 ? 5

알고리즘 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임 –(from 위키백과 ) 문제 해결 절차를 체계적으로 기술한 것 –(from 문병로 교수님 ppt – 이하 강의자료 ) 6

알고리즘의 필요성 알고리즘을 왜 공부해야 하는가 ? 7

알고리즘의 필요성 ? 특정한 문제를 위한 알고리즘의 습득 체계적으로 생각하는 훈련 지적 추상화의 레벨 상승 –Intellectual abstraction – 연구나 개발에 있어 정신적 여유를 유지하기 위해 매우 중요한 요 소 (from 강의자료 ) 8

알고리즘의 필요성 ! (1) 바보는 되지 말자. –> 아주 기본적인 알고리즘은 필수 ! 9

알고리즘의 필요성 ! Big Integer – 자료구조 과제 1 – 큰 두 수의 덧셈, 뺄셈, 곱셈을 만든다. 10

알고리즘의 필요성 ! 곱셈을 덧셈으로 구현한다면 ? – 끝나지 않는다 * = … 11

알고리즘의 필요성 ! (2) 알고리즘을 알면 할 수 있는 것들이 있다. –SNS 를 통한 분석 – 동접자가 100 만이 넘는 온라인게임 관리 – 등등 많은 양의 데이터를 관리하는 경우 12

점근적 복잡도 ( 시간복잡도 ) 알고리즘의 속도 13

점근적 복잡도 흔히 말하는 O(n), O(n^2), O(log n) 등등 14

점근적 복잡도 이 알고리즘이 얼마나 빠른거죠 ? 15

점근적 복잡도 이 알고리즘이 얼마나 빠른거죠 ? –> 빠르다의 정의는 ? 16

점근적 복잡도 10 개의 숫자를 정렬하세요. 100 개의 숫자를 정렬하세요 개의 숫자를 정렬하세요. 17 n 개의 숫자를 정렬하세요.

점근적 복잡도 문제 크기 n 에 대해 어떤 함수에 비례하는 시간이 걸리는지 결정 ! 18

점근적 복잡도 (from 강의자료 ) 19

점근적 복잡도 (from 강의자료 ) 20

점근적 복잡도 몇 배 차이는 중요하지 않다 ! –( 같은 점근적 복잡도를 가지는 경우 몇 십 배 이상 차이 나지 않는다.) 21

점근적 복잡도 가장 큰 것 이외엔 중요하지 않다 ! –n 이 큰 경우만 점근적 복잡도가 의미가 있다. – 수행시간 = n^3 + 3n^2 + 2n + 4 O(n^3) 22

점근적 복잡도 g(n) 에 비례하는 함수를 나타내기 위한 기 호 –O(g(n)), Θ(g(n), Ω(g(n)), o(g(n)) 등 – 대략 g(n) 보다 작거나 같다, g(n) 과 같다 등등으 로 해석 가능. – 편의를 위해 O 만 사용. 23

점근적 복잡도 O(g(n)) 에서, g(n) 이 1 억 ~10 억이다 ? – 초 단위의 시간이 걸릴 것을 예상할 수 있다. 24

점근적 복잡도 ( 실제 수행 시간 ) Big Integer 곱셈을 덧셈으로 구현 –>O(dn) (n 은 숫자, d 는 n 의 자릿수 ) n <= 10^100 10^90 년 이상이 걸리지 않을까 ? 25

점근적 복잡도 ( 실제 수행 시간 ) Big Integer 곱셈을 의도한 방법으로 구현 –>O(n^2) (n 은 자릿수 ) n <= …01 초쯤 걸린다. 26

점근적 복잡도 n 을 뭐로 잡느냐에 따라 함수도 달라진다. g(n) 이 아니라 g(n,m), g(a,b,c,d) 등등일 수 도 있다. 27

점근적 복잡도 구하는 방법 – 점화식을 구한다. –g(n) = g(n-1) + 1 –g(n) = g(n-1) + n –g(n) = g(n/2)

점근적 복잡도 g(n) = g(n-1) + 1 = g(n-2) = g(n-3) … = g(0) … + 1 = n 29

점근적 복잡도 g(n) = g(n-1) + n = g(n-2) + (n-1) + n … = g(0) … + n = ½ n(n+1) = O(n^2) 30

점근적 복잡도 g(n) = g(n-1) + n = g(n-2) + (n-1) + n … = g(0) … + n = 0.5 * n^ * n 31

점근적 복잡도 g(n) = g(n/2) + 1 = g(n/4) = g(n/8) … ( 대략 log n 번 하면 ) = g(1) … + 1 = log n 32

점근적 복잡도 O(g(n)) 에서, g(n) 이 1 억 ~10 억이다 ? – 초 단위의 시간이 걸릴 것을 예상할 수 있다. 33

정렬 (SORTING) 기본적인 알고리즘 예시 34

정렬 문제 –n 개의 숫자를 오름차순으로 배열한다. 35

거품 정렬 (bubble sort) 36

거품 정렬 (bubble sort) 37

거품 정렬 (bubble sort) for (int i = n - 1; i > 0; i++) for (int j = 0; j < i; j++) if ( list[ j ] > list[ j+1 ] ) swap( list[ j ], list[ j+1 ] ); (n-1) + (n-2) + … + 1 = n(n-1)/2 = 0.5n^2-0.5n // O(n^2) 38

정렬 비슷한 정렬 – 삽입정렬, 선택정렬이 있고 모두 O(n^2) – 이 중에선 삽입정렬이 제일 좋다. 거의 다 정렬되어 있는 경우 빠르다. 39

정렬할 배열이 주어짐 배열을 반반으로 나눈다 각각 독립적으로 정렬한다 병합한다 ( 정렬완료 ) Mergesort (from 강의자료 ) 40

합병정렬 (mergesort) 크게 두 파트로 나누어져 있다. – 반으로 나누어 각각을 정렬한다. – 정렬된 두 리스트를 합친다. 41

i j t i j t i j t p q r Merge 의 작동 예 (from 강의자료 ) 42

i j t ij t i j t 43

i j t i j t i j t 44

i j t 45

합병정렬 (mergesort) 수행 시간을 g(n) 이라고 하면 – 반으로 나누어 각각을 정렬한다. 2 * g(n/2) – 정렬된 두 리스트를 합친다. O(n) 46

합병정렬 (mergesort) g(n) = 2*g(n / 2) + O(n) – 대충 계산해보면 g(n) = 2*g(n / 2) + n = 4*g(n / 4) + n + n … = n log (n) –O(n log n) 47

합병정렬 (mergesort) 마스터 정리를 사용하면 바로 알 수 있다. – 수업 시간에 배웁니다. 하지만 직관적으로 답을 알아내는 것도 좋 다. 48

DYNAMIC PROGRAMMING ( 동적 계획법 ) 약간 어려운 알고리즘 예시 49

Dynamic Programming 큰 문제를 풀기 위해 먼저 작은 문제를 푼다. 재귀적 해법 -> 반대로 한다면 ? 50

피보나치 1, 1, 2, 3, 5, 8, 13, 21, 34, … f(n) = f(n-1) + f(n-2) 51

피보나치 int f (int n) { if(n == 0 || n == 1) return 1; return f (n-1) + f (n-2); } // 끝나지 않는다 ?? 52

피보나치 f(10) = f(9) + f(8) = f(8) + f(7) + f(7) + f(6) = f(7) + f(6) + f(6) + f(5) + f(6) + f(5) + f(5) + f(4) … 53

피보나치 f(0)=1, f(1)=1 이다. f(2) = f(1) + f(0) = 2 f(3) = f(2) + f(1) = 3 … 54

피보나치 직전 두 개의 값 둘을 기억하고, 다음 값을 구한다. O(n) 55

최단경로 찾기 56 S E

최단경로 찾기

최단경로 찾기

최단경로 찾기 f(x, y) = f(x-1, y) + f(x, y-1) 59

최단경로 찾기 int f (int x, int y) { if(x == 0 || y == 0) return 1; return f (x - 1, y) + f (x, y - 1); } 60

더 어려운 알고리즘들 61

여기까진 공통으로 알아두면 좋다. 62

더 어려운 문제들 수업, 연구실에서 연구 P=NP 현재까지 안 풀린 문제를 연구 알고리즘 대회 – 풀린 문제만 사용 63

더 어려운 문제들 수업, 연구실에서 연구 P=NP 현재까지 안 풀린 문제를 연구 알고리즘 대회 – 풀린 문제만 사용 64

NP-COMPLETE 연구분야 65

문제의 종류 풀 수 없다 – 정지문제 (halting problem) 풀 수 있다 –(a) sorting, 최단거리 –(b) TSP, 3-sat 등등 66

문제의 종류 풀 수 있다의 (b) 는 ( 아직까지는 ) 현실적인 시간에 풀 수 없다. O(2^n), O(n!), O(n^n) 등등 … 그 중에 NP-complete 라는 이론이 있다. 67

NP-Complete NP-Complete 에 해당하는 문제들이 많이 있다. – 이들 중 하나만 다항시간 안에 계산된다면, 다 른 모든 것들도 풀린다. 68

NP-Complete 모든 문제를 Yes, No 로 바꾸어 해석한다. NP-Complete 는 –NP 이고 –NP-Hard 인 모든 문제를 말한다. 69

NP-Complete P – 다항시간 안에 해를 구할 수 있다. NP –Yes 가 나오는 해를 제공하면, 이것이 Yes 라는 것을 다항시간 안에 확인할 수 있다. –No 의 경우는 모름. 70

NP-Complete NP-Hard – 모든 NP 문제를 L 로 다항시간 안에 변환할 수 있으면, L 은 NP-Hard 이다. – 즉, L 의 난이도는 NP 의 가장 어려운 문제 이상 이다. 71

NP-Complete( 예시 ) 최단거리는 어떤 모양이어도 다항시간 안 에 풀리지만 최장거리 구하기 (Longest Path Problem) 은 NP-Complete 이다. 72

NP-Complete( 예시 ) Traveling Salesman Problem – 모든 도시를 돌고 처음으로 돌아오는 최단경로 ? 73

P=NP? 백만불의 상금이 걸려있는 문제. 74 NP P=NP (a) (b) P

비유 (from 강의자료 ) 1. 나는 답을 구할 수가 없습니다. 아마 나는 멍청한 모양입니다. 상사가 아주 어려운 문제를 해결하라고 지시했다 75

2. 나는 답을 구할 수가 없습니다. 왜냐하면 이 문제는 답이 없어요. 76

3. 나는 답을 구할 수가 없습니다. 그렇지만 저렇게 수많은 천재들도 이 문제를 해결할 수 없습니다. NP-Complete 이론의 상황을 비유적으로 보여줌 77

근사 알고리즘 완전한 해는 못 구해도, 최적해와 가까운 해는 다항식 안에 구할 수 있는 경우가 있다.(Heuristic) Traveling Salesman Problem – 다항식 시간에 최적해의 k 배 이내의 해를 구할 수 있는 경우가 있음 78

근사 알고리즘 NP-Hard 문제임이 증명되면 Heuristic 을 생 각하자 ! 79

알고리즘 대회 80

알고리즘 대회 많은 대회들이 있다. –google code jam –IPSC –ACM-ICPC – 등등 81

82

83

문제 예시 N 개의 수로 이루어진 배열 A 가 있을 때, 인 접한 두 수의 교환만으로 up and down sequence 를 만들려 한다. 최소의 교환 횟 수를 구하시오. (Google Code Jam 2014 Round 2) 84

문제 예시 Up and down sequence –A 1 A m+1 >... > A N –1, 4, 10, 14, 9, 7, 3, 2 85

문제 예시 ( 풀이 )

문제 예시 ( 풀이 ) (1) 최솟값을 찾는다

문제 예시 ( 풀이 ) (2) 왼쪽 끝이 가까운지 오른쪽 끝이 가까운 지 찾는다

문제 예시 ( 풀이 ) (3) 더 가까운 쪽으로 옮긴다

문제 예시 ( 풀이 ) (4) 나머지 숫자에 대해 이 과정을 반복한다

문제 예시 ( 풀이 ) (1) 최솟값을 찾는다 : O(n) (2) 왼쪽 끝이 가까운지 오른쪽 끝이 가까운지 찾는다 : O(n) (3) 더 가까운 쪽으로 옮긴다 : O(n) (4) 나머지 숫자에 대해 이 과정을 반복한다 : O(g(n-1)) O(g(n)) = O(g(n-1)) + O(n) + O(n) = O(g(n-1)) + O(n) O(g(n)) = O(n^2) 91

문제 예시 ( 풀이 ) n <= 1000 이므로 ok. 92

문제 예시 ( 풀이 ) 시간이 남는다면 왜 이게 맞는지 생각해보 는 것도 좋다. 하지만 대회는 시간이 생명 ! 93

문제 예시 ( 풀이 ) Up and down sequence 에서는 최솟값이 맨 왼쪽 또는 오른쪽에 있어야 한다. 인접한 두 값만 바꿀 수 있고, 맨 왼쪽 또는 오른쪽에 있는 값은 더 이상 변하지 않는다. 94

기타 Greedy 알고리즘 – 현재 상황에서 최선의 전략을 찾는다. 전체적으로는 최선이 아닐 수 있다. 95

End Q & A 96