Chapter 01 자료 구조와 알고리즘

Contents 1. 1 자료 구조와 알고리즘 1. 2 추상 데이터 타입 1. 3 알고리즘의 성능 분석 1. 1 자료 구조와 알고리즘 1. 2 추상 데이터 타입 1. 3 알고리즘의 성능 분석 1. 4 자료 구조 표기법

1. 1 자료 구조와 알고리즘 프로그램 (Program) 1. 1 자료 구조와 알고리즘 프로그램 (Program) 프로그램 = 자료구조 (data structure) + 알고리즘 (algorithm)

1. 1 자료 구조와 알고리즘 알고리즘 (Algorithm) 컴퓨터로 문제를 풀기 위한 단계적인 절차 알고리즘의 조건 1. 1 자료 구조와 알고리즘 알고리즘 (Algorithm) 컴퓨터로 문제를 풀기 위한 단계적인 절차 알고리즘의 조건 입 력 : 0개 이상의 입력 존재 출 력 : 1개 이상의 출력 존재 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 함 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 함 유효성 : 각 명령어들은 실행 가능한 연산이어야 함 알고리즘 기술 방법 영어나 한국어와 같은 자연어 흐름도 (flow chart) 유사 코드 (pseudo-code) C와 같은 프로그래밍 언어

1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 자연어 표기 인간이 읽기가 쉬움 1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 자연어 표기 인간이 읽기가 쉬움 그러나 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있음 예) 배열에서 최대값 찾기

1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 (Cont.) 흐름도 (flow chart) 1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 (Cont.) 흐름도 (flow chart) 직관적이고 이해하기 쉬운 알고리즘 기술 방법 그러나 복잡한 알고리즘의 경우, 상당히 복잡해짐

1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 (Cont.) 유사 코드 (pseudo-code) 1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 (Cont.) 유사 코드 (pseudo-code) 알고리즘의 고수준 기술 방법 자연어보다는 더 구조적인 표현 방법 프로그래밍 언어보다는 덜 구체적인 표현방법 알고리즘 기술에 가장 많이 사용 프로그램을 구현할 때의 여러가지 문제들을 감출 수 있음 즉 알고리즘의 핵심적인 내용에만 집중 가능

1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 (Cont.) C 언어 알고리즘의 가장 정확한 기술이 가능 1. 1 자료 구조와 알고리즘 알고리즘의 기술 방법 (Cont.) C 언어 알고리즘의 가장 정확한 기술이 가능 반면 실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있음

1. 2 추상 데이터 타입 데이터 타입 (Data type) 추상 데이터 타입 (ADT; Abstract Data Type) 데이터의 집합과 연산의 집합 추상 데이터 타입 (ADT; Abstract Data Type) 데이터 타입을 추상적(수학적)으로 정의한 것 데이터나 연산이 무엇(what) 인가는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않음

1. 2 추상 데이터 타입 추상 데이터 타입의 정의 객체 (object) 연산 (operation) 추상 데이터 타입에 속하는 객체가 정의 연산 (operation) 이들 객체들 사이의 연산이 정의 추상 데이터 타입과 외부를 연결하는 인터페이스의 역할

1. 2 추상 데이터 타입 추상 데이터 타입의 정의 (Cont.) 예) 자연수

1. 3 알고리즘의 성능 분석 알고리즘의 성능 분석 기법 수행 시간 측정 알고리즘의 복잡도 분석 1. 3 알고리즘의 성능 분석 알고리즘의 성능 분석 기법 수행 시간 측정 두개의 알고리즘의 실제 수행 시간을 측정하는 것 실제로 구현하는 것이 필요 동일한 하드웨어를 사용하여야 함 알고리즘의 복잡도 분석 직접 구현하지 않고서도 수행 시간을 분석하는 것 알고리즘이 수행하는 연산의 횟수를 측정하여 비교 일반적으로 연산의 횟수는 n의 함수 시간 복잡도 분석: 수행 시간 분석 공간 복잡도 분석: 수행시 필요로 하는 메모리 공간 분석 컴퓨터에서 수행시간을 측정하는 방법에는 주로 clock 함수가 사용 clock 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환

1. 3 알고리즘의 성능 분석 수행 시간 측정 (Cont.) 수행시간을 측정하는 전형적인 프로그램

1. 3 알고리즘의 성능 분석 알고리즘의 복잡도 분석 방법 1. 3 알고리즘의 성능 분석 알고리즘의 복잡도 분석 방법 시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시 산술 연산, 대입 연산, 비교 연산, 이동 연산의 기본적인 연산 수헹시간이 입력의 크기에 따라 변하면 안됨 기본적인 연산만 알고리즘이 수행하는 연산의 개수를 계산하여 두 개의 알고리즘 비교 연산의 수행횟수는 고정된 숫자가 아니라 입력의 개수 n에 대한 함수 → 시간복잡도 함수라고 하고  T(n) 이라고 표기

1. 3 알고리즘의 성능 분석 복잡도 분석의 예 n을 n번 더하는 문제 각 알고리즘이 수행하는 연산의 개수를 세어 봄 1. 3 알고리즘의 성능 분석 복잡도 분석의 예 n을 n번 더하는 문제 각 알고리즘이 수행하는 연산의 개수를 세어 봄 단 for 루프 제어 연산은 고려하지 않음

1. 3 알고리즘의 성능 분석 복잡도 분석의 예 (Cont.) n을 n번 더하는 문제

1. 3 알고리즘의 성능 분석 시간 복잡도 함수 계산 예 코드를 분석해보면 수행되는 수행되는 연산들의 횟수를 입력 크기의 함수로 만들 수 있음

1. 3 알고리즘의 성능 분석 빅오 표기법 연산의 횟수를 대략적(점근적)으로 표기한 것 1. 3 알고리즘의 성능 분석 빅오 표기법 연산의 횟수를 대략적(점근적)으로 표기한 것 두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))임 빅오는 함수의 상한을 표시 (예) n≥5 이면 2n+1 < 10n 이므로 2n+1 = O(n)

1. 3 알고리즘의 성능 분석 빅오 표기법 (Cont.)

1. 3 알고리즘의 성능 분석 빅오 표기법의 종류 O(1) : 상수형 O(logn) : 로그형 O(n) : 선형 1. 3 알고리즘의 성능 분석 빅오 표기법의 종류 O(1) : 상수형 O(logn) : 로그형 O(n) : 선형 O(nlogn) : 로그선형 O(n2) : 2차형 O(n3) : 3차형 O(nk) : k차형 O(2n) : 지수형 O(n!) : 팩토리얼형

1. 3 알고리즘의 성능 분석 빅오 표기법의 종류 (Cont.) 시간복잡도 n 1 2 4 8 16 32 logn 3 5 1. 3 알고리즘의 성능 분석 빅오 표기법의 종류 (Cont.) 시간복잡도 n 1 2 4 8 16 32 logn 3 5 nlogn 24 64 160 n2 256 1024 n3 512 4096 32768 2n 65536 4294967296 n! 40326 20922789888000 26313×1033

1. 3 알고리즘의 성능 분석 최선, 평균, 최악의 경우 알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있음 1. 3 알고리즘의 성능 분석 최선, 평균, 최악의 경우 알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있음 최선의 경우(best case): 수행 시간이 가장 빠른 경우 평균의 경우(average case): 수행시간이 평균적인 경우 최악의 경우(worst case): 수행 시간이 가장 늦은 경우

1. 3 알고리즘의 성능 분석 최선, 평균, 최악의 경우 (Cont.) 예) 순차탐색 1. 3 알고리즘의 성능 분석 최선, 평균, 최악의 경우 (Cont.) 예) 순차탐색 최선의 경우: 찾고자 하는 숫자가 맨앞에 있는 경우 ; O(1) 최악의 경우: 찾고자 하는 숫자가 맨뒤에 있는 경우 ; O(n) 평균적인 경우: 각 요소들이 균일하게 탐색된다고 가정하면 (1+2+…+n)/n=(n+1)/2 O(n)

1. 4 자료 구조 표기법 C 언어 표현 방법 자료구조와 관련된 데이터들을 구조체로 정의 1. 4 자료 구조 표기법 C 언어 표현 방법 자료구조와 관련된 데이터들을 구조체로 정의 연산을 호출할 경우, 이 구조체를 함수의 파라미터로 전달

1. 4 자료 구조 표기법 자료 구조 기술 규칙 상수 변수의 이름 함수의 이름 typedef의 사용 대문자로 표기 1. 4 자료 구조 표기법 자료 구조 기술 규칙 상수 대문자로 표기 예) #define MAX_ELEMENT 100 변수의 이름 소문자를 사용하였으며 언더라인을 사용하여 단어와 단어를 분리 예) int increment;     int new_node; 함수의 이름 동사를 이용하여 함수가 하는 작업을 표기 예) int add(ListNode *node)    // 혼동이 없는 경우 int list_add(ListNode *node) //혼동이 생길 우려가 있는 경우 typedef의 사용 C언어에서 사용자 정의 데이터 타입을 만드는 경우에 쓰이는 키워드

[ Exercises ] Chapter 01 (page. 37) 09 시간복잡도 함수 계산 18 프로그램 코드에 대한 답 09 시간복잡도 함수 계산 18 프로그램 코드에 대한 답 22 배열 연산 23 typedef 사용