알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

프로그램의 설계 과정 알고리즘은 주어진 문제를 논리적으로 해결하는 과정이다. 알고리즘: 효율, 분석, 차수 – Part 1 만족? 프로그램 문제 알고리즘 설계 분석 예 아니오 재설계 알고리즘은 주어진 문제를 논리적으로 해결하는 과정이다. 분석을 통해 작성한 알고리즘의 정확성을 파악할 수 있고, 효율성을 정량적으로 나타낼 수 있다. (일반적으로) 알고리즘은 프로그래밍 언어에 독립적이다.

알고리즘 과목의 학습 목표 Design(설계): 다양한 문제에 대해, 알고리즘을 설계하는 기법을 배운다. 알고리즘: 효율, 분석, 차수 – Part 1 Design(설계): 다양한 문제에 대해, 알고리즘을 설계하는 기법을 배운다. Analysis(분석): 알고리즘을 분석하여 시간/공간 복잡도를 구하는 방법을 배운다. Computational Complexity(계산 복잡도): 문제를 분석하여 계산 복잡도를 구하는 방법을 배운다.

알고리즘이란? 정의: 문제에 대한 답(해결책)을 찾기 위해서 계산하는 절차이다. 좀 더 구체적인 정의 알고리즘: 효율, 분석, 차수 – Part 1 정의: 문제에 대한 답(해결책)을 찾기 위해서 계산하는 절차이다. 좀 더 구체적인 정의 알고리즘은 단계별로 주의 깊게 설계된 계산 과정이다. 알고리즘은 입력을 받아서 출력으로 전환시켜주는 일련의 계산 절차이다. 음…. 결국, 알고리즘이라는 것은 어떤 절차를 기술하는 것이다. 또 한번 음… 주어진 입력이 있을 때, 원하는 해답을 출력하기 위해서, 어떻게 계산하면 되는지 그 절차를 기술하는 것이다.

알고리즘의 예 주어진 문제: 전화번호부에서 “홍길동”의 전화번호 찾기 알고리즘(해결책) 분석: 어떤 알고리즘이 더 좋은가? 알고리즘: 효율, 분석, 차수 – Part 1 주어진 문제: 전화번호부에서 “홍길동”의 전화번호 찾기 알고리즘(해결책) 순차검색(sequential search): 전화번호부의 첫 쪽부터 홍길동이라는 이름이 나올 때까지 순서대로 찾는다. (수정된) 이진검색(binary search): 전환번호부는 “가나다”순으로 되어있으므로 먼저 “ㅎ”이 있을 만한 곳으로 넘겨본 후 앞뒤로 뒤적여가며 찾는다. 분석: 어떤 알고리즘이 더 좋은가?

문제(Problem)의 표기/표현 방법 문제: 해결책을 찾고자 던지는 질문 알고리즘: 효율, 분석, 차수 – Part 1 문제: 해결책을 찾고자 던지는 질문 매개변수(파라미터, parameter): 문제에서 어떤 특정 값이 주어지지 않은 변수(variable) 문제의 사례(instance) = 입력(input): 문제에 주어진 파라미터에 특정 값을 지정한 것(예) 사례에 대한 해답(solution) = 출력(output): 주어진 사례에 관한 질문에 대한 답

문제의 표기 예 알고리즘: 효율, 분석, 차수 – Part 1 문제: 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: “아니오”

알고리즘의 표기(기술) 자연어: 한글 또는 영어 ( 부정확하고 모호함) 알고리즘: 효율, 분석, 차수 – Part 1 자연어: 한글 또는 영어 ( 부정확하고 모호함) 프로그래밍언어: C, C++, Java, Pascal 등 ( 특정 언어에 의존적이어서 일반적인 알고리즘 기술에 부적합) 의사코드(Pseudo-code): 직접 실행할 수 있는 프로그래밍언어는 아니지만, 실제 프로그램에 거의 가깝게 계산과정을 표현할 수 있는 언어 알고리즘은 보통 의사코드로 표현한다. 본 강의에서는 C++(혹은 C)에 가까운 의사코드를 사용한다.

C++과 의사코드의 차이점 (1/3) 배열 인덱스의 범위에 제한 없음 프로시저의 파라미터에 2차원 배열 크기의 가변성 허용 알고리즘: 효율, 분석, 차수 – Part 1 배열 인덱스의 범위에 제한 없음 C++는 반드시 0부터 시작 의사코드는 임의의 값 사용 가능 (예: int x[5..10];) 프로시저의 파라미터에 2차원 배열 크기의 가변성 허용 예: void pname(A[][]) { … } C++에서는 다음과 같이 제한이 필요함: void pname(A[][10]){ … } 지역배열에 변수 인덱스 허용 예: keytype S[low..high]; C++에서는 숫자 인덱스만 가능함

C++과 의사코드의 차이점 (2/3) 수학 표현식 및 간단한 자연어 허용 C++에 없는 타입 사용 가능 알고리즘: 효율, 분석, 차수 – Part 1 수학 표현식 및 간단한 자연어 허용 low <= x && x <= high  low  x  high temp = x; x = y; y = temp;  exchange x and y; C++에 없는 타입 사용 가능 index: 첨자로 사용되는 정수 변수 number: 정수(int) 또는 실수(float) 모두 사용가능 bool: “true”나 “false” 값을 가질 수 있는 변수 이외에도 잘 알려진 키워드(예: record, list)는 별도 정의 없이 사용

C++과 의사코드의 차이점 (3/3) 제어 구조 프로시저와 함수의 구분 알고리즘: 효율, 분석, 차수 – Part 1 제어 구조 repeat (n times) { … } 프로시저와 함수의 구분 프로시저: void pname(…) {…} 함수: returntype fname (…) {… return x;} 참조 파라미터(reference parameter)를 사용하여 프로시저의 결과값 전달 방법 (call by reference를 설명하고 있음) 배열: (기본적으로) 참조 파라미터로 전달 나머지: 데이터 타입 이름 뒤에 &를 붙임 const 배열: 전달되는 배열의 값이 불변

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

순차검색 (Sequential Search) (1/3) 알고리즘: 효율, 분석, 차수 – Part 1 문제: 크기가 n인 배열 S에 x가 있는가? 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면 0 알고리즘(자연어): x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사한다. 만일 x 와 같은 아이템을 찾으면 S에서 해당 위치를 출력하고, S 를 모두 검사하고도 찾지 못하면 0을 출력한다.  자연어 알고리즘은 문제를 풀기는 하였으나, 프로그램으로 전환하기에는 용이하지 않다.

순차검색 (Sequential Search) (2/3) 알고리즘: 효율, 분석, 차수 – Part 1 알고리즘(의사코드) void seqsearch(int n, // 입력(1) const keytype S[], // 입력(2) keytype x, // 입력(3) index& location) // 출력 { location = 1; while (location <= n && S[location] != x) location++; if (location > n) location = 0; } while-루프: 아직 검사할 항목이 있고, x를 찾지 못하였나? if-문: 모두 검사하였으나, x를 찾지 못했나?

순차검색 (Sequential Search) (3/3) 알고리즘: 효율, 분석, 차수 – Part 1 순차검색 알고리즘으로 키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야 하는가? 키와 같은 항목의 위치에 따라 다름 최악의 경우: n 평균의 경우: n/2 좀 더 빨리 찾을 수는 없는가? 더 이상 빨리 찾을 수 있는 알고리즘은 존재하지 않는다. 배열 S에 있는 항목에 대한 정보가 전혀 없는 상황에서, 모든 항목을 검색하지 않고 임의의 항목 x를 항상 찾을 수 있다는 보장이 없기 때문이다. 만약, 배열 S가 정렬되어 있다는 정보가 존재한다면?  이진검색

이진검색 (Binary Search) (1/3) 알고리즘: 효율, 분석, 차수 – Part 1 문제: 크기가 n인 정렬된 배열 S에 x가 있는가? 입력: (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면, 0 순차검색의 문제와 다른 점은 배열 S가 “정렬”되어 있다는 정보를 알고 있다는 점이다. 순차검색의 문제가 보다 일반적이므로, 순차검색을 사용하여 이 문제를 풀 수 있다. 그러나, 순차검색을 사용하면 “정렬”되어 있다는 정보를 사용하지 못하는 것이 된다.

이진검색 (Binary Search) (2/3) 알고리즘: 효율, 분석, 차수 – Part 1 알고리즘(의사코드) void binsearch(int n, // 입력(1) const keytype S[], // 입력(2) keytype x, // 입력(3) index& location) // 출력 { index low, high, mid; low = 1; high = n; location = 0; while (low <= high && location == 0) { mid = (low + high) / 2; // 정수나눗셈 if (x == S[mid]) location = mid; else if (x < S[mid]) high = mid – 1; else low = mid + 1; } while-루프: 아직 검사할 항목이 있고, x를 찾지 못하였나?

이진검색 (Binary Search) (3/3) 알고리즘: 효율, 분석, 차수 – Part 1 비교 횟수를 분석해 본다. 배열의 크기가 32라면  6번의 비교가 필요하다. 이때, 6 = lg 32 + 1이다. 배열의 크기가 64라면  7번의 비교가 필요하다. 이때, 7 = lg 64 + 1이다. 배열의 크기가 2k라면  k+1번의 비교가 필요하다. 이때, k+1 = lg 2k + 1이다. … 이분검색 알고리즘으로 키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야 하는가? while 문을 수행할 때마다 검색 대상의 크기가 절반으로 감소하기 때문에 최악의 경우라도 lg n + 1번만 비교하면 된다. 상기 횟수 분석에서 n = 2k라 하면, 비교 횟수는 lg n + 1이 된다.

순차검색 vs. 이진검색 배열의 크기 순차검색 이진검색 비고 n lg n + 1 128 8 1,024 11 1,048,576 알고리즘: 효율, 분석, 차수 – Part 1 배열의 크기 순차검색 이진검색 비고 n lg n + 1 두 방법 모두 최악의 경우에 대한 비교 횟수임 128 8 1,024 11 1,048,576 21 4,294,967,296 33

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

피보나찌(Fibonacci) 수열 피보나찌 수열의 정의 알고리즘: 효율, 분석, 차수 – Part 1 피보나찌 수열의 정의 예: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

피보나찌 수 구하기 – 재귀 알고리즘 (1/4) 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 알고리즘: 효율, 분석, 차수 – Part 1 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 출력: n 번째 피보나찌 수 재귀(recursive) 알고리즘: int fib(int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); }

피보나찌 수 구하기 – 재귀 알고리즘 (2/4) 분석: 피보나찌 수 구하기 재귀 알고리즘은 수행속도가 매우 느리다. 알고리즘: 효율, 분석, 차수 – Part 1 분석: 피보나찌 수 구하기 재귀 알고리즘은 수행속도가 매우 느리다. 이유: 같은 피보나찌 수를 중복하여 계산한다. 예: fib(5) 계산을 위해서는 fib(2)를 세 번이나 중복 계산한다. 함수 fib(5) 호출 시의 재귀 트리 (recursive tree)

피보나찌 수 구하기 – 재귀 알고리즘 (3/4) fib(n) 함수 호출 횟수 계산 알고리즘: 효율, 분석, 차수 – Part 1 fib(n) 함수 호출 횟수 계산 T(n) = fib(n)을 계산하기 위하여 fib() 함수를 호출하는 횟수 즉, T(n)은 재귀 트리 상의 마디의 개수

피보나찌 수 구하기 – 재귀 알고리즘 (4/4) 알고리즘: 효율, 분석, 차수 – Part 1 정리: 재귀적 알고리즘으로 구성한 재귀 트리의 마디의 수를 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 > 2.83  23/2 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번째 피보나찌 수를 구하라. 입력: 양수 n 알고리즘: 효율, 분석, 차수 – Part 1 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 출력: n 번째 피보나찌 수 재귀(iterative) 알고리즘: int fib2 (int n) { index i; int f[0..n]; 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];

피보나찌 수 구하기 – 반복 알고리즘 (2/2) 분석: 반복 알고리즘은 수행속도가 훨씬 더 빠르다. 알고리즘: 효율, 분석, 차수 – Part 1 분석: 반복 알고리즘은 수행속도가 훨씬 더 빠르다. 이유: 재귀 알고리즘과는 달리 중복 계산이 없다. 계산하는 항(f[i])의 총 개수 T(n) = n + 1 즉, f[0]부터 f[n]까지 단 한번씩만 계산한다.

피보나찌 수 구하기 – 재귀 vs. 반복 (1/2) 노드 하나(혹은 항 하나) 계산에 1 ns 걸린다고 가정하자. n n+1 알고리즘: 효율, 분석, 차수 – Part 1 노드 하나(혹은 항 하나) 계산에 1 ns 걸린다고 가정하자. n n+1 2n/2 반복 재귀(하한) 40 41 1,048,576 41ns 1048s 60 61 1.1109 61ns 1s 80 81 1.11012 81ns 18min 100 101 1.11015 101ns 13days 120 121 1.21018 121ns 36years 160 161 1.21024 161ns 3.8 107years 200 201 1.31030 201ns 4 1013years

피보나찌 수 구하기 – 재귀 vs. 반복 (2/2) 알고리즘: 효율, 분석, 차수 – Part 1 재귀 알고리즘 보다는 반복 알고리즘이 항상 효율적이다?  꼭 그렇지만은 않다.  특히, 설계 단계에서 재귀 알고리즘은 매우 유용하다. 피보나찌 수 구하기의 재귀 알고리즘은 Ch. 2에서 다루는 분할정복(Divide & Conquer)의 전형적인 예이다. 피보나찌 수 구하기의 반복 알고리즘은 Ch. 3에서 다루는 동적 프로그래밍(Dynamic Programming)의 간단한 보기이다.

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

알고리즘의 분석(analysis) 시간복잡도(Time Complexity) 분석 표현 척도 알고리즘: 효율, 분석, 차수 – Part 1 시간복잡도(Time Complexity) 분석 입력 크기에 따라서 단위 연산이 몇 번 수행되는지 결정하는 절차 표현 척도 단위연산(basic operation): 비교문(comparison), 지정문(assignment) 등 입력크기(input size): 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 꼭지점과 에지의 수

분석 방법의 종류 (1/2) 모든 경우 분석(Every-case analysis) 알고리즘: 효율, 분석, 차수 – Part 1 모든 경우 분석(Every-case analysis) 복잡도는 입력 크기에만 종속(dependent)적임 입력 값과는 무관(independent)하게 복잡도는 항상 일정 최악의 경우 분석(Worst-case analysis) 복잡도는 입력 크기와 입력 값 모두에 종속 단위연산이 수행되는 횟수가 최대(최악)인 경우 선택

분석 방법의 종류 (2/2) 평균의 경우 분석(Average-case analysis) 알고리즘: 효율, 분석, 차수 – Part 1 평균의 경우 분석(Average-case analysis) 입력 크기와 입력 값 모두에 종속 모든 입력에 대해서 단위연산이 수행되는 기대치(평균) 각 입력 값에 대해서 확률 할당이 가능  확률에 따라 기대치가 다르게 계산될 수 있음 일반적으로 최악의 경우보다 계산이 복잡 최선의 경우 분석(Best-case analysis) 단위 연산이 수행되는 횟수가 최소(최선)인 경우 선택

배열 덧셈 알고리즘 문제: 크기가 n인 배열 S의 모든 수를 더하라. 입력: 양수 n, 배열 S[1..n] 알고리즘: 효율, 분석, 차수 – Part 1 문제: 크기가 n인 배열 S의 모든 수를 더하라. 입력: 양수 n, 배열 S[1..n] 출력: 배열 S에 있는 모든 수의 합 알고리즘: number sum (int n, const number S[]) { index i; number result; result = 0; for (i = 1; i <= n; i++) result = result + S[i]; return result; }

배열 덧셈 알고리즘: 시간 복잡도 분석 단위연산: 덧셈 입력크기: 배열의 크기 n 모든 경우 분석: 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 덧셈 입력크기: 배열의 크기 n 모든 경우 분석: 배열 내용에 상관없이 for-루프가 n번 반복된다. 각 루프마다 덧셈이 1회 수행된다. 따라서, n에 대해서 덧셈이 수행되는 총 횟수는 T(n) = n 이다. 단위연산: 지정문 (for-루프의 첨자 지정문 포함) 입력크기: 배열의 크기 n 모든 경우 분석: 배열 내용에 상관없이 for-루프가 n번 반복된다. 따라서, 지정문이 T(n) = n + n + 1번 수행된다. 기본 동작을 다르게 함으로써, 시간 복잡도가 다르게 나왔다.  그러나, 사실 둘 모두는 같은 복잡도 카테고리에 속한다.

버블 정렬(Bubble Sort) 알고리즘 알고리즘: 효율, 분석, 차수 – Part 1 문제: 비내림차순으로 n개의 키를 정렬 입력: 양수 n, 배열 S[1..n] 출력: 비내림차순으로 정렬된 배열 알고리즘: void exchangesort (int n, keytype S[]) { index i, j; for (i = 1; i <= n-1; i++) for (j = i+1; j <= n; j++) if (S[j] < S[i]) exchange S[i] and S[j]; } for(j = 1;j <= (n-i); j++) if (S[j] < S[j-1]) exchange S[j] and S[j-1];

버블 정렬 알고리즘: 시간 복잡도 분석 I 단위연산: 조건문 (S[j]와 S[i]의 비교) 입력크기: 정렬할 항목의 수 n 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 조건문 (S[j]와 S[i]의 비교) 입력크기: 정렬할 항목의 수 n 모든 경우 분석: j-루프가 수행될 때마다 조건문을 1번씩 수행 조건문의 총 수행횟수 i = 1 : j-루프 n – 1 번 수행 i = 2 : j-루프 n – 2 번 수행 i = 3 : j-루프 n – 3 번 수행 i = n – 1 : j-루프 1 번 수행 따라서

버블 정렬 알고리즘: 시간 복잡도 분석 II 단위연산: 교환하는 연산 (exchange S[j] and S[i]) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 교환하는 연산 (exchange S[j] and S[i]) 입력크기: 정렬할 항목의 수 n 최악의 경우 분석: 조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다. 최악의 경우 = 조건문이 항상 참(true)이 되는 경우 = 입력 배열이 거꾸로 정렬되어 있는 경우

순차 검색 알고리즘: 시간 복잡도 분석(1/4) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 입력크기: 배열 안에 있는 아이템의 수 n 최악의 경우 분석: x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우, 단위 연산이 n번 수행된다. 따라서, 순차검색 알고리즘의 경우 입력배열의 값에 따라서 검색하는 횟수가 달라지므로, 모든 경우(every-case)의 시간 복잡도 분석은 불가능하다.

순차 검색 알고리즘: 시간 복잡도 분석(2/4) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 입력크기: 배열 안에 있는 아이템의 수 n 가정:배열의 아이템이 모두 다르다. 평균의 경우 분석(경우 1): x가 배열 S안에 있는 경우만 고려 에 대해서 x가 배열의 k번째 있을 확률 = 1/n x가 배열의 k번째 있다면, x를 찾기 위해서 수행하는 단위연산의 횟수 = k 따라서,

순차 검색 알고리즘: 시간 복잡도 분석(3/4) 평균의 경우 분석(경우 2): x가 배열 S안에 없는 경우도 고려 알고리즘: 효율, 분석, 차수 – Part 1 평균의 경우 분석(경우 2): x가 배열 S안에 없는 경우도 고려 x가 배열 S안에 있을 확률을 p라고 하면, x가 배열에 있을 확률 = p (x가 배열의 k번째 있을 확률 = p/n) x가 배열에 없을 확률 = 1 – p 따라서, 참고:

순차 검색 알고리즘: 시간 복잡도 분석(4/4) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 입력크기: 배열 안에 있는 아이템의 수 n 최선의 경우 분석: x가 S[1]일 때, 입력의 크기에 상관없이 단위연산이 1번만 수행된다. 따라서, B(n) = 1

계산(시간) 복잡도: 어떤 것을 사용하지? 알고리즘: 효율, 분석, 차수 – Part 1 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석이 가장 정확한가? ( 분석 자체야 모두 정확해야 한다.) 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석을 사용할 것인가? ( 응용에 따라 다르나, 대개 최악/평균을 사용한다.)

정확도 분석? 알고리즘이 의도한 대로 수행되는지를 증명하는 절차 (즉, 알고리즘이 정확하게 수행되는지를 증명하는 절차) 알고리즘: 효율, 분석, 차수 – Part 1 알고리즘이 의도한 대로 수행되는지를 증명하는 절차 (즉, 알고리즘이 정확하게 수행되는지를 증명하는 절차) 정확한 알고리즘이란? 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘 정확하지 않은 알고리즘이란? 어떤 입력에 대해서 멈추지 않거나, 또는 틀린 답을 출력하면서 멈추는 알고리즘 정확도 분석은 프로그램 증명(Program Verification)과 마찬가지로 매우 이론적인 분야로서, Dijkstra 등에 의해서 연구되었다.