CHAP 1:자료구조와 알고리즘 순천향대학교 컴퓨터공학과 2016. 3. 8 하 상 호

1장 목차 자료구조와 알고리즘 추상 데이터 타입 알고리즘의 성능분석

자료구조와 알고리즘 자료구조란? 일상생활에서 사물들을 정리하고 조직화하는 방법들을 생각해 보면, 일상생활에서의 사물의 조직화 조직도 해야할일 리스트 일상생활에서의 사물의 조직화 사전 Ticket Box

자료구조와 알고리즘 자료구조는 프로그램에서 사용되는 자료를 표현하고, 저장하는 방법이고 수단 Ticket Box 해야할일 리스트 a b c NULL A B C Ticket Box 전단(front) 후단(rear) 일상생활에서의 예 자료구조 물건을 쌓아두는 것 스택 영화관 매표소의 줄 큐 할일 리스트 리스트 영어사전 사전, 탐색구조 지도 그래프 조직도 트리

자료구조와 알고리즘 알고리즘이란? 프로그램이란? 프로그램

예제: 자료구조와 알고리즘 성적을 읽어 들여서 최고 점수를 구하는 프로그램을 생각해보자. 자료구조는? 알고리즘은? 자료가 무엇이고, 어떻게 표현되는가? 알고리즘은? 자료 표현으로부터 어떻게 최고 점수를 구하는가?

예제: 자료구조와 알고리즘 성적처리 프로그램 자료구조 알고리즘 80 70 90 30 …

예제: 자료구조와 알고리즘 성적처리 프로그램의 고려사항 학생수가 미리 알려져 있는가? 그렇지 않은가? 위의 경우에 따라 자료구조가 결정되고, 자료구조에 따라 알고리즘이 결정된다.

알고리즘이란? 컴퓨터로 문제를 해결하기 위한 단계적 절차를 기술하는 것 특정 언어에 독립적 알고리즘 특징 입력 – 0개 이상의 입력 출력 – 1개 이상의 출력 명백성(definiteness) – 각 명령어의 의미는 모호하지 않고 명확하게 유한성(finiteness) – 알고리듬은 반드시 종료되어야 함 유효성(effectiveness) – 각 명령어는 실행가능한 연산

알고리즘이란? 알고리즘 기술 언어 자연어 흐름도(flow chart) 의사코드(또는 유사코드)(pseudocode) 프로그래밍 언어

예제: 알고리즘 기술언어 문제: 주어진 정수 배열에서 최대값을 찾아라. 분석하라. 1 2 3 4 5 6 7 8 9 10

예제: 알고리즘 기술언어 자연어 이해하기 쉽다 의미 모호성 초래 ArrayMax(A,n) 1 2 3 4 5 6 7 8 9 10 ArrayMax(A,n) 배열 A의 첫번째 요소를 변수 tmp에 복사 배열 A의 다음 요소들을 차례대로 tmp와 비교하면 더 크면 tmp로 복사 배열 A의 모든 요소를 비교했으면 tmp를 반환

예제: 알고리즘 기술언어 순서도 시작 직관적, 이해하기 쉽다 문제가 복잡한 경우, 상당히 복잡해짐 종료 tmp←A[0] i←1 i < n A[i]>tmp tmp←A[i] no yes i++ tmp 출력 종료

예제: 알고리즘 기술언어 의사코드 시작 알고리즘 기술 언어 사용 가장 많이 사용 종료 tmp←A[0] i←1 i < n A[i]>tmp tmp←A[i] no yes i++ procedure ArrayMax(A,n) integer A(0:n), tmp tmp ← A(0) for i←1 to n-1 do if tmp < A(i) then tmp ← A(i) endif repeat return tmp end ArrayMax tmp 출력 종료

코딩 알고리즘의 각 단계를 특정 언어의 문장으로 표현 알고리즘 C 프로그램 #define MAX_ELEMENTS 100 int score[MAX_ELEMENTS]; int find_max_score(int n) { int i, tmp; tmp=score[0]; for(i=1;i<n;i++){ if( score[i] > tmp ){ tmp = score[i]; } return tmp; procedure ArrayMax(A,n) integer A(0:n), tmp tmp ← A(0) for i←1 to n-1 do if tmp < A(i) then tmp ← A(i) endif repeat return tmp end ArrayMax

추상 데이터 타입 데이터 타입(data type) 데이터의 집합 데이터에 적용되는 연산들의 집합 (예) C의 int

추상 데이터 타입 추상 데이터 타입(ADT: Abstract Data Type) ADT 용도 데이터 타입을 추상적(수학적)으로 명세 데이터와 그 연산에 대한 수학적 명세 데이터와 연산이 무엇(what)인가 만을 정의하고, 데이터와 연산이 어떻게(how) 구현되는지는 정의하지 않음 ADT 용도 ADT의 구현 세부 사항을 외부에 알리지 않고, 외부와의 인터페이스만을 공개 정보 은닉 효과

추상 데이터 타입의 예: 자연수 객체는 집합의 개념을 이용하여 정의 Nat_No 객체: 0에서 시작하여 INT_MAX까지의 순서화된 정수 연산: x, y ∈ Nat_No zero() ::= return 0; is_zero(x) ::= if (x =0) then return TRUE; else return FALSE; add(x,y) ::= if( (x+y) <= INT_MAX ) then return x+y; else return INT_MAX sub(x,y) ::= if ( x<y ) then return 0; else return x-y; equal(x,y)::= if( x=y ) then return TRUE; successor(x)::= if( (x+y) <= INT_MAX ) then return x+1; is_greater(x,y)::=

Quiz Boolean 추상 데이터 타입을 정의하고, 다음과 같은 연산자들을 포함시켜라. And, Or, Not, Xor

Report Set(집합) 추상 데이터 타입을 정의하고, 다음과 같은 연산자들을 포함시켜라. Create, Insert, Remove, Is_In, Union, Intersection, Difference.

알고리즘 성능분석 알고리즘 성능분석의 필요성 알고리즘 성능 분석 방법 알고리즘의 효율성 중요 예제: 동일한 작업을 수행하는 2개 프로그램 고려 알고리즘 성능 분석 방법 실행 시간 측정 알고리즘 복잡도 분석 입력 자료의 개수 n = 6 36초 64초 n = 100

알고리즘 성능분석 실행 시간 측정 두 개의 알고리즘의 실제 실행 시간을 측정하는 것 실제로 프로그램으로 구현하는 것이 필요 동일한 하드웨어를 사용해야 하는 제한성 소프트웨어 환경 고려 실험 데이터의 제한성

알고리즘 성능분석:수행시간측정 프로그램 실행시간 측정(in C) // in C, clock_t clock(void) 함수 이용 실행시간 측정 #include <stdio.h> #include <stdlib.h> #include <time.h> void main( void ) {    clock_t start, finish; // clock_t => long    double  duration;    start = clock(); // 시스템 시각을 clock 단위로 반환     // 수행시간을 측정하고 하는 코드....     // .... // …    finish = clock();    duration = (double)(finish - start) / CLOCKS_PER_SEC; // 초 단위 시간계산 // CLOCKS_PER_SEC = 1000으로 설정되어 있음 // 1 clock은 0.001초이며, 1밀리초임    printf("%.3lf 초입니다.\n", duration); }

알고리즘 성능분석 알고리즘의 복잡도 분석 알고리즘이 수행하는 연산의 횟수를 측정하여 비교 시간 복잡도 분석: 직접 구현하지 않고서도 수행 시간을 분석하는 것 하드웨어, 소프트웨어 고려 필요 없음 시간 복잡도 분석: 알고리듬에 포함된 연산 회수 계산(배정, 비교, 이동 연산 등) 공간 복잡도 분석: 수행시 필요로 하는 메모리 공간 분석 공간보다는 시간이 더 중요 일반적으로 연산의 횟수는 n의 함수 시간 복잡도 함수: T(n), n은 입력의 개수

예제:알고리즘 성능분석 n을 n번 더하는 문제를 해결하는 다음 3개 알고리즘을 생각 위의 각 알고리즘에서 연산 회수는? (루프 제어 연산은 제외) 알고리즘 A 알고리즘 B 알고리즘 C sum ←n*n; sum ← 0; for i ← 1 to n do    sum ←sum + n; for i←1 to n do   for ←1 to n do     sum ←sum + 1;   알고리즘 A 알고리즘 B 알고리즘 C 배정연산 덧셈연산 곱셈연산 비교 연산 전체연산수

예제:알고리즘 성능분석 입력 개수에 따른 연산 회수를 그래프로 표현 연산의 횟수 알고리즘 C: T(n) = 알고리즘 B: 알고리즘 A: T(n) = 입력의 개수 n

빅오 표기법 입력 개수 n, 시간복잡도 함수 T(n)이 주어질 때, Ex. T(n) = 이면, n = 1,000일 때 각 항이 미치는 영향은?

빅오 표기법 알고리즘 비교에서 루프 제어 연산을 포함시키면? sum ← 0; for i ← 1 to n do    sum ←sum + n; repeat 루프제어문의 연산 횟수는? 2n+1 vs 5n+3 n이 커질 때 두 함수의 차이는 미미 T(n)에서 불필요한 정보를 제거하여 알고리즘이 증가 추세만 표현하는 것이 빅오 표기법. T(2n+1) = O(n) T(5n+3) = O(n)

빅오 표기법 빅오 표기법 정의: 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다. f(n)의 상한을 의미 연산의 횟수

빅오 표기법 예제: f(n) = 2n +1일 때, 그 빅오 표기는? f(n) = 5n + 3일 때, 그 빅오 표기는?

빅오 표기법 예제: f(n) = 일 때, 빅오 표기는?

빅오 표기법의 예 예제 함수 빅오 표기 f(n) = 5 f(n) = 2n+1 f(n)= f(n) =

빅오 표기법의 종류 O(1)     O(nlogn) O(n!) O(n) O(logn)  

빅오 표기법의 종류 O(1) : 상수형 O(logn) : 로그형 O(n) : 선형 O(nlogn) : 로그선형 O(nk) : k차형 O(2n) : 지수형 O(n!) : 팩토리얼형 참고: 표 1-5(pp.29)

빅오 표기법이외의 표기법 . 빅오메가 표기법 빅세타 표기법 모든 n≥n0에 대하여 |f(n)| ≥ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=Ω(g(n))이다. 빅오메가는 함수의 하한을 표시한다. (예) f(n)=2n+1, n ≥ 1에 대해 2n+1 >= n 이므로 f(n) = Ω(n) 빅세타 표기법 모든 n≥n0에 대하여 c1|g(n)| ≤ |f(n)| ≤ c2|g(n)|을 만족하는 3개의 상수 c1, c2와 n0가 존재하면 f(n)=θ(g(n))이다. 빅세타는 함수의 하한인 동시에 상한을 표시한다. f(n)=O(g(n))이면서 f(n)= Ω(g(n))이면 f(n)= θ(n)이다. (예) f(n)=2n+1. n ≥ 1에 대해 n ≤ 2n+1 ≤ 3n이므로 f(n) = θ(n) . 입력의 개수 n 연산의 수 상한 하한

최선, 평균, 최악의 경우 동일한 알고리듬이 입력 값에 따른 다른 수행시간을 가질 때, 알고리즘을 3가지 경우로 평가 가능 최악의 경우(worst case) 최선의 경우(best case) 평균적인 경우(average age) 최악의 경우 최선의 경우 평균적인 경우 A B C D E F G 입력 집합 수행시간 100 50 최악의 경우가 널리 사용됨

최선, 평균, 최악의 경우 예제 : 순차 탐색 알고리즘에서 비교 연산을 고려 최선의 경우는? 최악의 경우는? 평균적인 경우는? procedure seq_search(list, n, key) parameters integer list(0:n-1), n, key integer i for i <- 0 to n-1 do if list(i) = key then return i endif repeat return -1 end seq_search

문제 다음 코드에서 배정, 곱셈, 덧셈, 비교 연산의 개수를 계산하라. 그리고 시간 복잡도를 빅오 표기법으로 표현하라. 루프 제어 연산은 무시하라. procedure test (n) parameters integer n local integer i, total = 1 for i <- 2 to n-1 do total <- total * n repeat return total end test