[CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr Ch.01 알고리즘 개요 (효율, 분석, 차수) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr
프로그램의 설계 과정 알고리즘은 주어진 문제를 논리적으로 해결하는 과정이다. 만족? 프로그램 문제 알고리즘 설계 분석 예 아니오 재설계 알고리즘은 주어진 문제를 논리적으로 해결하는 과정이다. 분석을 통해 작성한 알고리즘의 정확성을 파악할 수 있고, 효율성을 정량적으로 나타낼 수 있다. (일반적으로) 알고리즘은 프로그래밍 언어에 독립적이다.
알고리즘 과목의 학습 목표 Design(설계): 다양한 문제에 대해, 알고리즘을 설계하는 기법을 배운다. Analysis(분석): 알고리즘을 분석하여 시간/공간의 계산 복잡도를 구하는 방법을 배운다. Computational Complexity(계산 복잡도) - 시간(time): CPU - 공간(storage): 메모리
알고리즘이란? 정의: 문제에 대한 답(해결책)을 찾기 위한 단계적인 계산 절차 좀 더 구체적인 정의 알고리즘은 단계별로 주의 깊게 설계된 계산 과정이다. 알고리즘은 입력을 받아서 출력으로 전환시켜주는 일련의 계산 절차이다. 음…. 결국, 알고리즘이라는 것은 어떤 절차를 기술하는 것이다. 또 한번 음… 주어진 입력이 있을 때, 원하는 해답을 출력하기 위해서, 어떻게 계산하면 되는지 그 절차를 기술하는 것이다.
알고리즘의 예 주어진 문제: 전화번호부에서 “홍길동”의 전화번호 찾기 알고리즘(해결책) 분석: 어떤 알고리즘이 더 좋은가? 순차검색(sequential search): 전화번호부의 첫 쪽부터 홍길동이라는 이름이 나올 때까지 순서대로 찾는다. (수정된) 이진검색(binary search): 전환번호부는 “가나다”순으로 되어있으므로 먼저 “ㅎ”이 있을 만한 곳으로 넘겨본 후 앞뒤로 뒤적여가며 찾는다. 분석: 어떤 알고리즘이 더 좋은가?
문제(Problem)의 표기/표현 방법 문제: 해결책을 찾고자 던지는 질문 매개변수(파라미터, parameter): 문제에서 어떤 특정 값이 주어지지 않은 변수(variable) 문제의 사례(instance) = 입력(input): 문제에 주어진 파라미터에 특정 값을 지정한 것 사례에 대한 해답(solution) = 출력(output): 주어진 사례에 관한 질문에 대한 답
문제의 표기 예 문제: n개의 수로 된 리스트 S에 x라는 수가 있는지 알아내시오. 그 결과, x가 S에 있으면 “예”, 없으면 “아니오”로 답하시오. 파라미터: S, n, x 입력의 예1: S = [10,7,11,5,3,8], n = 6, x = 5 출력의 예1: “예” 입력의 예2: S = [10,7,11], n = 3, x = 5 출력의 예2: “아니오”
알고리즘의 표기(기술) 자연어: 한글 또는 영어 ( 부정확하고 모호함) 프로그래밍언어: C, C++, Java, Pascal 등 ( 특정 언어에 의존적이어서 일반적인 알고리즘 기술에 부적합) 의사코드(Pseudo-code): 직접 실행할 수 있는 프로그래밍언어는 아니지만, 실제 프로그램에 거의 가깝게 계산과정을 표현할 수 있는 언어 알고리즘은 보통 의사코드로 표현한다. 본 강의에서는 Java 언어와 유사한 의사코드를 사용한다.
Java와 의사코드의 차이점 (1/3) 배열 인덱스의 범위에 제한 없음 지역배열에 변수 인덱스 허용 의사코드는 임의의 범위 값 사용 가능 (예: int x[5..10];) 지역배열에 변수 인덱스 허용 예: keytype[] S = new keytype[2..n]; S가 2부터 n까지 첨자를 가진 배열 Java에서는 0부터 시작되는 숫자 인덱스만 가능
Java와 의사코드의 차이점 (2/3) 수학 표현식 및 간단한 자연어 허용 Java 에 없는 타입 사용 가능 low <= x && x <= high (Java) low x high (의사 코드) temp = x; x = y; y = temp; (Java) exchange x and y; (의사 코드) Java 에 없는 타입 사용 가능 index: 첨자로 사용되는 정수 변수 number: 정수(int) 또는 실수(float) 모두 사용가능 bool: “true”나 “false” 값을 가질 수 있는 변수 이외에도 잘 알려진 타입(예: record, list)을 별도 정의 없이 사용
Java와 의사코드의 차이점 (3/3) 제어 구조 프로시저와 함수의 구분 repeat (n times) { … } for 루프 while 루프 프로시저와 함수의 구분 함수: type fname (…) {… return x;} 알고리즘 1.1: 순차검색 (P. 5) 알고리즘 1.2: 배열의 수 더하기 (P. 7) 프로시저: void pname(…) {…} 알고리즘 1.3: 교환정렬 (P. 8) 알고리즘 1.4: 행렬곱셈 (P. 9)
순차검색 (Sequential Search) (1/3) 문제: 크기가 n인 리스트 (배열) S에 x가 있는가? (교재: 알고리즘 1.1) 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면 0 알고리즘(자연어): x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사한다. 만일 x 와 같은 아이템을 찾으면 S에서 해당 위치를 출력하고, S 를 모두 검사하고도 찾지 못하면 0을 출력한다. 자연어 알고리즘은 문제를 풀기는 하였으나… 1) 프로그램으로 전환하기에는 용이하지 않고, 2) 모호한 표현이 많다.
순차검색 (Sequential Search) (2/3) 알고리즘(의사코드) index seqsearch(int n, // 입력(1) keytype[] S, // 입력(2) keytype x) // 입력(3) { index location; location = 1; while (location <= n && S[location] != x) location++; if (location > n) location = 0; return location; } while-루프: 아직 검사할 항목이 있고, x를 찾지 못하였나? if-문: 모두 검사하였으나, x를 찾지 못했나?
순차검색 (Sequential Search) (3/3) 키와 같은 항목의 위치에 따라 다름 최악의 경우: n 평균의 경우: n/2 좀 더 빨리 찾을 수는 없는가? 사실상 더 이상 빨리 찾을 수 있는 알고리즘은 존재하지 않는다. 배열 S에 있는 항목에 대한 정보가 전혀 없는 상황에서, 모든 항목을 검색하지 않고 임의의 항목 x를 항상 찾을 수 있다는 보장이 없음. 만약, 배열 S가 정렬되어 있다는 정보가 존재한다면? 이진검색 알고리즘 적용가능
이진검색 (Binary Search) (1/3) 문제: 크기가 n인 정렬된 배열 S에 x가 있는가? (교재: 알고리즘 1.5) 입력: (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면, 0 순차검색의 문제와 다른 점은 배열 S가 “정렬”되어 있다는 정보를 알고 있다는 점이다. 순차검색의 문제가 보다 일반적이므로, 순차검색을 사용하여서도 이 문제를 풀 수 있다. 그러나, 순차검색을 사용하면 “정렬”되어 있다는 정보를 사용 하지 못한다.
이진검색 (Binary Search) (2/3) 알고리즘(의사코드) index binsearch(int n, // 입력(1) keytype[] S, // 입력(2) keytype x) // 입력(3) { index location, low, high, mid; low = 1; high = n; location = 0; while (low <= high && location == 0) { mid = (low + high) / 2; // 나눗셈 & floor if (x == S[mid]) location = mid; else if (x < S[mid]) high = mid – 1; else low = mid + 1; } return location; while-루프: 아직 검사할 항목이 있고, x를 찾지 못하였나?
이진검색 (Binary Search) (3/3) 최악의 경우에 대한 비교 횟수를 (개략적으로) 분석해 본다. 최악의 경우: x가 배열 S에 저장된 값들보다 클 때 (즉, 검색을 실패할 때) 배열의 크기가 32라면 6번의 비교가 필요하다. 이때, 6 = lg 32 + 1이다. 그림 1.1참고 배열의 크기가 64라면 7번의 비교가 필요하다. 이때, 7 = lg 64 + 1이다. 배열의 크기가 2k라면 k+1번의 비교가 필요하다. 이때, k+1 = lg 2k + 1이다. … 이분검색 알고리즘으로 키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야 하는가? while 문을 수행할 때마다 검색 대상의 크기가 절반으로 감소하기 때문에, n = 2k라 하면 최악의 경우에 lg n + 1번을 비교함 [note] lg n = log2n
순차검색 vs. 이진검색 배열의 크기 순차검색 이진검색 비고 n lg n + 1 128 8 1,024 11 1,048,576 두 방법 모두 최악의 경우에 대한 비교 횟수임 128 8 1,024 11 1,048,576 21 4,294,967,296 33
[실습 1] 순차검색과 이진검색 순차검색과 이진검색에 대한 실제 Java 프로그램을 작성해보자. SearchMain.java 를 분석하기 완성되지 않은 다음 두 함수를 작성한다. public static int sequentialSearch() public static int binarySearch() [주의] 위 Java 코드에서 배열의 인덱스는 0 부터 시작하여 n-1 까지 유효하다. 교재 알고리즘의 의사코드와 다르게, 검색 결과 존재하지 않으면 -1을 리턴 num 변수 값을 키워가며 각 함수에 대한 수행 시간을 비교한다. num 값이 1000, 10000, 100000, 1000000 일 때의 각 함수에 대한 수행시간은? int[] s = new int[n]
피보나찌(Fibonacci) 수열 피보나찌 수열의 정의 예: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
자연계의 피보나찌 수열
피보나찌 수 구하기 – 재귀 알고리즘 (1/4) 문제: n번째 피보나찌 수를 구하라. (교재: 알고리즘 1.6) 재귀(recursive) 알고리즘: long fib(int n) { if (n <= 1) return n; else return (fib(n-1) + fib(n-2)); } 실제 Java 코딩시에 long 타입 사용할 것!
피보나찌 수 구하기 – 재귀 알고리즘 (2/4) 분석: 피보나찌 수 구하기 재귀 알고리즘은 수행속도가 매우 느리다. 이유: 같은 피보나찌 수를 중복하여 계산한다. 예: fib(5) 계산을 위해서는 fib(2)를 세 번이나 중복 계산한다. 함수 fib(5) 호출 시의 재귀 트리 (recursive tree) 실제 호출되는 상황을 봅시다!
피보나찌 수 구하기 – 재귀 알고리즘 (3/4) fib(n) 함수 호출 횟수 계산 T(n) = fib(n)을 계산하기 위하여 fib() 함수를 호출하는 횟수 즉, T(n)은 재귀 트리 상의 마디의 개수
피보나찌 수 구하기 – 재귀 알고리즘 (4/4) 정리: 재귀적 알고리즘으로 구성한 재귀 트리의 마디의 수를 T(n)이라 하면, n 2인 모든 n에 대하여 T(n) > 2n/2이다. 증명: (n에 대한 수학적 귀납법으로 증명) [Induction base] T(2) = T(1) + T(0) + 1 = 3 > 2 = 22/2 T(3) = T(2) + T(1) + 1 = 5 > 23/2 ( 2.83) [Induction hypothesis] 2 m < n인 모든 m 에 대해서 T(m) > 2m/2 이라 가정 [Induction step] T(n) > 2n/2임을 보인다. T(n) = T(n - 1) + T(n - 2) + 1 > 2(n - 1)/2 + 2(n - 2)/2 + 1 [귀납가정에 의하여] > 2(n - 2)/2 + 2(n - 2)/2 = 2 2(n / 2)-1 = 2 n/2
피보나찌 수 구하기 – 반복 알고리즘 (1/2) 문제: n번째 피보나찌 수를 구하라. (교재: 알고리즘 1.6) 반복(iterative) 알고리즘: int fib2 (int n) { index i; int[] f = new int[n+1]; f[0] = 0; if (n > 0) { f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; } return f[n]; 실제 Java 코딩시에는 long 타입 사용할 것!
피보나찌 수 구하기 – 반복 알고리즘 (2/2) 분석: 반복 알고리즘은 수행속도가 훨씬 더 빠르다. 이유: 재귀 알고리즘과는 달리 중복 계산이 없다. 계산하는 항(f[i])의 총 개수 T(n) = n + 1 즉, f[0]부터 f[n]까지 단 한번씩만 계산한다.
피보나찌 수 구하기 – 재귀 vs. 반복 노드 하나(혹은 항 하나) 계산에 1 ns 걸린다고 가정하자. n n+1 2n/2 반복 알고리즘 재귀 알고리즘 (하한) 40 41 1,048,576 41ns 1048s 60 61 1.1109 61ns 1s 80 81 1.11012 81ns 18min 100 101 1.11015 101ns 13days 120 121 1.21018 121ns 36years 160 161 1.21024 161ns 3.8 107years 200 201 1.31030 201ns 4 1013years
Factorial 구하기 – 재귀 vs. 반복 Iterative definition of factorial Recursive definition of factorial Recursive Definition A의 정의 파트에 다시 A를 사용하는 정의 Page 29
재귀 vs. 반복 재귀 알고리즘 보다는 반복 알고리즘이 항상 효율적이다? 꼭 그렇지만은 않다. (그럼 언제 재귀 알고리즘이 좋은데…?) 특히, 설계 단계에서 재귀 알고리즘은 매우 유용하다. 피보나찌 수 구하기의 재귀 알고리즘은 Ch. 2에서 다루는 분할정복(Divide & Conquer)의 전형적인 예이다. 피보나찌 수 구하기의 반복 알고리즘은 Ch. 3에서 다루는 동적 프로그래밍(Dynamic Programming) 또는 동적 계획법의 간단한 보기이다.
[실습 2-1] 재귀적 이진 검색 재귀적 이진검색에 대한 실제 Java 프로그램을 작성해보자. SearchMain.java 를 분석하기 완성되지 않은 다음 함수를 작성한다. public static int recursiveBinarySearch(int low, int high) [주의] Java에서 배열의 인덱스는 0 부터 시작하여 n-1 까지 유효하다. 교재 알고리즘의 의사코드와 다르게 검색 결과 존재하지 않으면 -1을 리턴 num 변수 값을 키워가며 각 함수에 대한 수행 시간을 비교한다. num 값이 1000, 10000, 100000, 1000000 일 때의 각 함수에 대한 수행시간은?
[실습 2-2] 피보나치 수열 피보나치 수열에 대한 재귀 알고리즘과 반복 알고리즘을 Java 프로그램으로 작성해보자. FibonacciMain.java 를 분석하기 완성되지 않은 다음 두 함수를 작성한다. public static long iterativeFibonacci(int num) public static long recursiveFibonacci(int num) num 값을 키워가며 각 함수에 대한 수행 시간을 비교한다. 최대한 큰 num 값을 할당해보자. Iterative 방법에서는 Fibonacci 값에 대한 long 의 제한 범위 내의 가장 큰 num 값이 무엇인지 확인해보자. Recursive 방법에서는 참을 수 있는 시간 한도 내에서 가장 큰 num 값이 무엇인지 확인해보자.