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

Presentation on theme: "알고리즘 개론 2014.6.19. 15:15 시작 장준영 1. 상/중/하상/중/하 상 – 나는 알고리즘을 매우 잘 알고, 좀 더 어려운 난 이도의 문제들을 보고 싶다. 중 – 어느정도 알고리즘을 구현해본 적이 있다. 하 – 알고리즘의 A 조차 모른다. 2."— Presentation transcript:

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

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

3 다룰 내용 3

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

5 알고리즘이 뭔가요 ? 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36 거품 정렬 (bubble sort) 36

37 거품 정렬 (bubble sort) 37

38 거품 정렬 (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

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

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

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

42 383265731115202948 i j t 83265731115202948 3i j t 3165731115202948 38i j t p q r Merge 의 작동 예 (from 강의자료 ) 42

43 32657315202948 3811i j t 326573202948 381115ij t 3265732948 38111520i j t 43

44 32657348 3811152029i j t 657348 381115202932i j t 6573 38111520293248i j t 44

45 381115202932486573i j t 45

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

47 합병정렬 (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

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

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

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

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

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

53 피보나치 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

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

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

56 최단경로 찾기 56 S E

57 최단경로 찾기 57 111111 1231 1 1 1 1 1 1

58 최단경로 찾기 58 111111 1231 1361 1410 11 1102031 111113162 1231462 136202688

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

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

61 더 어려운 알고리즘들 61

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

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

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

65 NP-COMPLETE 연구분야 65

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

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

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

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

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

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

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

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

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

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

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

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

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

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

80 알고리즘 대회 80

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

82 82

83 83

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

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

86 문제 예시 ( 풀이 ) 86 651423

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

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

89 문제 예시 ( 풀이 ) (3) 더 가까운 쪽으로 옮긴다. 89 651423 615423 165423

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

91 문제 예시 ( 풀이 ) (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

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

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

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

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

96 End Q & A 96