쉽게 배우는 알고리즘 1장. 알고리즘 설계와 분석의 기초

1장. 알고리즘 설계와 분석의 기초 생각하는 방법을 터득한 것은 미래의 문제를 미리 해결한 것이다. - 제임스 왓슨

학습목표 알고리즘의 정의와 필요성을 인지한다. 아주 기초적인 알고리즘 수행시간 분석을 할 수 있도록 한다. 점근적 표기법을 이해한다.

알고리즘이란 무엇인가? 문제 해결 절차를 체계적으로 기술한 것 문제의 요구조건 입력과 출력으로 명시할 수 있다 알고리즘은 입력으로부터 출력을 만드는 과정을 기술

입출력의 예 문제 입력 출력 100명의 학생의 시험점수의 최대값을 찾으라 100명의 학생들의 시험점수 위 100개의 시험점수들 중 최대값

알고리즘 공부의 목적 특정한 문제를 위한 알고리즘의 습득 체계적으로 생각하는 훈련 지적 추상화의 레벨 상승 Intellectual abstraction 연구나 개발에 있어 정신적 여유를 유지하기 위해 매우 중요한 요소

바람직한 알고리즘 명확해야 한다 효율적이어야 한다 이해하기 쉽고 가능하면 간명하도록 지나친 기호적 표현은 오히려 명확성을 떨어뜨림 명확성을 해치지 않으면 일반언어의 사용도 무방 효율적이어야 한다 같은 문제를 해결하는 알고리즘들의 수행시간이 수백만배 이상 차이날 수 있다

알고리즘의 수행시간 수행시간 문제의 크기(n)

알고리즘의 수행시간 수행시간 문제의 크기

알고리즘의 수행시간

알고리즘의 수행시간을 좌우하는 기준은 다양하게 잡을 수 있다 예: for 루프의 반복횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟수, … 몇 가지 간단한 경우의 예를 통해 알고리즘의 수행시간을 살펴본다

알고리즘의 수행시간 n에 관계없이 상수 시간이 소요된다. sample1(A[ ], n) { k = ; return A[k] ; } n에 관계없이 상수 시간이 소요된다.

알고리즘의 수행시간 n에 비례하는 시간이 소요된다. sample2(A[ ], n) { sum ← 0 ;         for i ← 1 to n                  sum← sum+ A[i] ;          return sum ;      } n에 비례하는 시간이 소요된다.

알고리즘의 수행시간 n2에 비례하는 시간이 소요된다. sample3(A[ ], n) { sum ← 0 ;         for i ← 1 to n                                 for j ← 1 to n                         sum← sum+ A[i]*A[j] ;         return sum ;      } n2에 비례하는 시간이 소요된다.

알고리즘의 수행시간 n3에 비례하는 시간이 소요된다. sample4(A[ ], n) { sum ← 0 ;         for i ← 1 to n                                 for j ← 1 to n {                     k ← A[1 ... n] 에서 임의로 개를 뽑을 때 이들 중 최대값 ;                         sum ← sum + k ;                 }         return sum ;      } n3에 비례하는 시간이 소요된다.

알고리즘의 수행시간 n2에 비례하는 시간이 소요된다. sample5(A[ ], n) { sum ← 0 ;         for i ← 1 to n-1                                 for j ← i+1 to n                         sum← sum+ A[i]*A[j] ;          return sum ;      } n2에 비례하는 시간이 소요된다.

알고리즘의 수행시간 n에 비례하는 시간이 소요된다. factorial(n) { if (n=1) return 1 ;         return n*factorial(n-1) ;  } n에 비례하는 시간이 소요된다.

재귀와 귀납적 사고 재귀=자기호출(recursion) 재귀적 구조 어떤 문제 안에 크기만 다를 뿐 성격이 똑같은 작은 문제(들)가 포함되어 있는 것 예1: factorial N! = N×(N-1)! 예1: 수열의 점화식 an = an-1 + 2

재귀의 예: 병합정렬 mergeSort(A[ ], p, r) ▷ A[p ... r]을 정렬한다 {         if (p < r) then {                 q ← ; -----------------------  ①   ▷ p, q의 중간 지점 계산                 mergeSort(A, p, q);  ----------------  ②   ▷ 전반부 정렬                 mergeSort(A, q+1, r); --------------  ③   ▷ 후반부 정렬                 merge(A, p, q, r);  ------------------  ④   ▷ 병합         } } merge(A[ ], p, q, r)         정렬되어 있는 두 배열 A[p ... q]와 A[q+1 ... r]을 합쳐         정렬된 하나의 배열 A[p ... r]을 만든다.

②, ③은 재귀호출 ①, ④는 재귀적 관계를 드러내기 위한 오버헤드 mergeSort(A[ ], p, r) {         if (p < r) then {                 q ← ; -----------------------  ①   ▷ p, q의 중간 지점 계산                 mergeSort(A, p, q);  ----------------  ②   ▷ 전반부 정렬                 mergeSort(A, q+1, r); --------------  ③   ▷ 후반부 정렬                 merge(A, p, q, r);  ------------------  ④   ▷ 병합         } } ②, ③은 재귀호출 ①, ④는 재귀적 관계를 드러내기 위한 오버헤드

다양한 알고리즘의 적용 주제들 카 네비게이션 스케쥴링 Human Genome Project 검색 자원의 배치 반도체 설계 … TSP, 차량 라우팅, 작업공정, … Human Genome Project 매칭, 계통도, functional analyses, … 검색 데이터베이스, 웹페이지들, … 자원의 배치 반도체 설계 Partitioning, placement, routing, … …

알고리즘을 왜 분석하는가 무결성 확인 자원 사용의 효율성 파악 자원 시간 메모리, 통신대역, …

알고리즘의 분석 크기가 작은 문제 크기가 충분히 큰 문제 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라 한다 알고리즘의 효율성이 중요하지 않다 비효율적인 알고리즘도 무방 크기가 충분히 큰 문제 알고리즘의 효율성이 중요하다 비효율적인 알고리즘은 치명적 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라 한다

점근적 분석Asymptotic Analysis 입력의 크기가 충분히 큰 경우에 대한 분석 이미 알고있는 점근적 개념의 예 Ο, Ω, Θ, ω, ο 표기법 lim f(n) n→ ∞

점근법 표기법Asymptotic Notations O( f(n) ) 기껏해야 f(n)의 비율로 증가하는 함수 e.g., O(n), O(n log n), O(n2), O(2n), … Formal definition O( f(n) ) = { g(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cf(n) ≥ g(n) } g(n) ∈ O(f(n)을 관행적으로 g(n) = O(f(n))이라고 쓴다. 직관적 의미 g(n) = O(f(n)) ⇒ g 는 f 보다 빠르게 증가하지 않는다 상수 비율의 차이는 무시

점근적 표기법 예, O( n2 ) 알 수 있는 한 최대한 tight 하게 3n2 + 2n 7n2 – 100n nlogn + 5n 3n 알 수 있는 한 최대한 tight 하게 nlogn + 5n = O(nlogn) 인데 굳이 O( n2 )으로 쓸 필요없다 Tight하지 않은 만큼 정보의 손실이 일어난다

점근적 표기법 Ω( f(n) ) Formal definition 직관적 의미 적어도 f(n)의 비율로 증가하는 함수 O( f(n) )과 대칭적 Formal definition Ω(f(n)) = { g(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cf(n)≤g(n) } 직관적 의미 g(n) = Ω(f(n)) ⇒ g 는 f 보다 느리게 증가하지 않는다

점근적 표기법 Θ( f(n) ) Formal definition 직관적 의미 f(n)의 비율로 증가하는 함수 Θ( f(n) ) = O( f(n) ) ∩ Ω( f(n) ) 직관적 의미 g(n) = Θ(f(n)) ⇒ g 는 f 와 같은 정도로 증가한다

각 점근적 표기법의 직관적 의미 O( f(n) ) Ω( f(n) ) Θ( f(n) ) Tight or loose upper bound Ω( f(n) ) Tight or loose lower bound Θ( f(n) ) Tight bound

정렬 알고리즘들의 복잡도 표현 예 (3장에서 공부함) 점근적 복잡도의 예 정렬 알고리즘들의 복잡도 표현 예 (3장에서 공부함) 선택정렬 Θ( n2 ) 힙정렬 O(nlogn) 퀵정렬 O( n2 ) 평균 Θ(nlogn)

시간 복잡도 분석의 종류 Worst-case Average-case Best-case Analysis for the worst-case input(s) Average-case Analysis for all inputs More difficult to analyze Best-case Analysis for the best-case input(s) 별로 유용하지 않음

저장/검색의 복잡도 배열 Binary search trees Balanced binary search trees B-trees O(n) Binary search trees 최악의 경우 Θ(n) 평균 Θ(log n) Balanced binary search trees 최악의 경우 Θ(log n) B-trees Hash table 평균 Θ(1)

크기 n인 배열에서 원소 찾기 Sequential search Binary search 배열이 아무렇게나 저장되어 있을 때 Worst case: Θ(n) Average case: Θ(n) Binary search 배열이 정렬되어 있을 때 Worst case: Θ(log n) Average case: Θ(log n)

Thank you