5장. 선택 알고리즘.

Slides:



Advertisements
Similar presentations
Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
Advertisements

1 ‘ 우리나라의 주요공업 ’ - 정도웅, 주민혁, 안수진, 백경민, 엄다운, 박경찬 -.
1. 도형의 연결 상태 2. 꼭지점과 변으로 이루어진 도형 Ⅷ. 도형의 관찰 도형의 연결상태 연결상태가 같은 도형 단일폐곡선의 성질 연결상태가 같은 입체도형 뫼비우스의 띠.
출석수업 과제 – 총 5문제, 10월 25일 제출 정보통계학과 장영재 교수.
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
이진 나무 구조 강윤섭 2008년 5월 23일.
2.6 탐색(Search) 1. 순차검색 (Sequential Search, Linear Search)
공부할 내용 조상들이 살던 곳 자연과 잘 어울리는 한옥 지방에 따라 서로 다른 집의 모양 섬 지방의 집
사랑, 데이트와 성적 자율성 :데이트 성폭력!!! 성폭력예방교육 전문강사 / 여성학 전공 신 순 옥.
(Program = Algorithm + Data Structure)
1636 쇼핑몰.
퇴계와 율곡의 사회사상 비교 남 일 재 동서대학교 교수/ 정치학 박사 1. 퇴계 이황과 율곡 이이의 약전(略傳)
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
501. 군인들의 세상 502. 민정 이양과 한일회담 이선용.
Excel 일차 강사 : 박영민.
Chapter 7. 조건문.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
운영체제 4장 요약정리(CPU 스케줄링) 2A 박훈.
분할 정복 (Divide-and-Conquer)
CHAP 2:순환 순천향대학교 컴퓨터공학과.
Chapter 02 순환 (Recursion).
빠른정렬(Quick Sort) – 개요 (1/2)
8장 함수 함수의 필요성 라이브러리 함수와 사용자 정의 함수 함수의 정의, 원형, 호출 배열을 함수 인자로 전달 재귀호출.
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
13. 탐색 트리.
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
자바 5.0 프로그래밍.
프로그래밍 개요
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
군집 분석.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Programming Challenge!
CHAP 2:순환.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
8장. 상호 배타적 집합의 처리.
쉽게 배우는 알고리즘 1장. 알고리즘 설계와 분석의 기초.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
컴퓨터 프로그래밍 기초 - 5th : 조건문(if, else if, else, switch-case) -
정치개혁의 가능성 논의 권력구조 개편을 통하여 본 -개헌을 통한 정부형태의 변화를 중심으로 [한국정치론] 윤성이 교수님
CAD 실습 2013년 2학기.
빌드 성공.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
알고리즘 알고리즘이란 무엇인가?.
노년기 발달 장안대 행정법률과 세류반 정 오 손
자료구조론 12장 검색(search).
Excel 일차 강사 : 박영민.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
빠른정렬(Quick Sort) – 개요 (1/2)
태국 문학 욜라다 왓짜니 싸란차나 팟차라와라이 끼따야펀 르앙다우 타니다.
7주차: Functions and Arrays
CHAP 2:순환.
세일즈의 원칙과 기술.
Homework #8 (실습 #7) [1/2] 다음을 수행하는 PHP 프로그램을 작성하여 프로그램과 결과물을 프린트하여 제출한다. sin(45º), cos(45º), tan(45º)를 출력하는 프로그램을 작성하시오. 피보나치 수를 구하는 함수 fib($n)을 작성하고,
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
12 그리드 시스템.
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
상관계수.
7장 연습 문제 풀이 학번 : 이름 :조 재한.
실습 UBLAB.
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
제 4 장 Record.
워밍업 실뭉치 전달게임.
어서와 C언어는 처음이지 제21장.
음파성명학 최종욱.
빠른정렬(Quick Sort) – 개요 (1/2)
C++ Espresso 제15장 STL 알고리즘.
Presentation transcript:

5장. 선택 알고리즘

5장. 선택 알고리즘 일을 시작하기 위해 기분이 내킬 때까지 기다리는 따위의 짓을 하지 않으려면 시험 제도는 좋은 훈련이 된다. -아놀드 토인비

학습목표 평균 선형 선택 알고리즘의 원리를 이해한다. 평균 선형 선택 알고리즘의 수행 시간 분석을 이해한다. 평균 선형 선택 알고리즘의 수행 시간 분석을 이해한다. 최악의 경우에도 선형 시간 보장하는 선택 알고리즘의 원리를 이해한다. 최악의 경우에도 선형 시간 보장하는 선택 알고리즘의 수행 시간 분석을 이해한다. 평균 선형 선택 알고리즘과 최악의 경우에도 선형 시간 보장하는 선택 알고리즘의 관계를 이해한다.

선택 알고리즘 (i 번째 작은 수 찾기) 배열 A[p ... r]에서 i번째 작은 원소를 찾는다 두가지 알고리즘을 배운다 평균적으로 선형시간이 소요되는 알고리즘 최악의 경우에도 선형시간이 소요되는 알고리즘

평균 선형시간 선택 알고리즘 select (A, p, r, i) { if (p = r) then return A[p] ;    ▷ 원소가 하나뿐인 경우. i는 반드시 1.   q ← partition(A, p, r) ; k ← q-p+1; ▷ k : 기준원소가 전체에서 k 번째 작은 원소임을 의미     if (i < k) then return select(A, p, q-1, i) ; ▷ 왼쪽 그룹으로 범위를 좁힘 else if (i = k) then return A[q] ;          ▷ 기준원소가 바로 찾는 원소임 else return select(A, p, q-1, i) ;    ▷ 오른쪽 그룹으로 범위를 좁힘 } 평균 수행 시간: Θ(n) 최악의 경우 수행 시간: Θ(n2)

선택 알고리즘 작동 예 1 2번째 작은 원소 찾기 p r 31 8 48 73 11 3 20 29 65 15 입력배열 8 11 분할 왼쪽 그룹에서 2번째 작은 원소를 찾는다 8 11 3 15 31 48 20 29 65 73

선택 알고리즘 작동 예 2 7번째 작은 원소 찾기 p r 31 8 48 73 11 3 20 29 65 15 입력배열 8 11 분할 오른쪽 그룹에서 3번째 작은 원소를 찾는다 8 11 3 15 31 48 20 29 65 73 4개

평균 수행 시간 T(n) ≤ Σ max[T(k-1), T(n-k)] + Θ(n) 1 n 분할된 양쪽 중 큰 쪽을 처리하는 비용 재귀호출을 제외한 오버헤드 (분할이 대부분) 이것은 T(n) ≤ cn임을 추정 후 증명법으로 증명할 수 있다 ∴ T(n) = O(n) T(n) = Ω(n)임은 자명하므로 T(n) = Θ(n)

최악의 경우 수행 시간 T(n) = T(n-1) + Θ(n) ∴ T(n) = Θ (n2) 재귀호출을 재외한 오버헤드 (분할이 대부분) 분할이 0 : n-1로 되고 큰 쪽을 처리하는 비용 ∴ T(n) = Θ (n2)

최악의 경우 선형시간 선택 알고리즘 앞에서 배운 선택 알고리즘에서 이번 알고리즘은 수행 시간은 분할의 균형에 영향을 받는다 최악의 경우 분할의 균형이 어느 정도 보장되도록 함으로써 수행 시간이 Θ(n)이 되도록 한다 분할의 균형을 유지하기 위한 오버헤드가 지나치게 크면 안된다

최악의 경우 선형시간 선택 알고리즘 linearSelect (A, p, r, i) { ① 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. ② 전체 원소들을 5개씩의 원소를 가진 개의 그룹으로 나눈다. (원소의 총수가 5의 배수가 아니면 이중 한 그룹은 5개 미만이 된다.) ③ 각 그룹에서 중앙값을 (원소가 5개이면 3번째 원소) 찾는다. 이렇게 찾은 중앙값들을 m1, m2, …, m 이라 하자. ④ m1, m2, …, m 들의 중앙값 M을 재귀적으로 구한다. 원소의 총수가 홀수면 중앙값이 하나이므로 문제가 없고, 원소의 총수가 짝수일 경우는 두 중앙값 중 아무거나 임의로 선택한다. ▷ call linearSelect( ) ⑤ M을 기준원소로 삼아 전체 원소를 분할한다(M보다 작거나 같은 것은 M의 왼쪽에, M보다 큰 것은 M의 오른쪽에 오도록). ⑥ 분할된 두 그룹 중 적합한 쪽을 선택하여 단계 ①~⑥을 재귀적으로 반복한다. ▷ call linearSelect( ) }

기준 원소를 중심으로 한 대소 관계 … M 각 그룹의 중앙값 → ■ 기준 원소 M ●/■ M보다 작은 원소들 1 그룹 2 그룹 3 ●/■ M보다 큰 원소들 ●/■ M보다 작은 원소들 ○ M보다 크거나 작을 수 있는 원소들 ■ 기준 원소 M

최악의 경우 수행 시간 T(n) ≤ T( n/5 ) + T(7n/10 + 2) + Θ(n) ④ ①②③⑤ ⑥ 이것은 T(n) ≤ cn임을 추정 후 증명법으로 증명할 수 있다 ∴ T(n) = O(n) T(n) = Ω(n)임은 자명하므로 T(n) = Θ(n)

Thank you