[CPA340] Algorithms and Practice Youn-Hee Han

Slides:



Advertisements
Similar presentations
6 장. printf 와 scanf 함수에 대한 고찰 printf 함수 이야기 printf 는 문자열을 출력하는 함수이다. – 예제 printf1.c 참조 printf 는 특수 문자 출력이 가능하다. 특수 문자의 미 \a 경고음 소리 발생 \b 백스페이스 (backspace)
Advertisements

알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
이진 나무 구조 강윤섭 2008년 5월 23일.
(Program = Algorithm + Data Structure)
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
컴퓨터 프로그래밍 기초 [Final] 기말고사
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
7장 배열 ②.
분할 정복 (Divide-and-Conquer)
10장 함수.
CHAP 2:순환 순천향대학교 컴퓨터공학과.
Chapter 02 순환 (Recursion).
빠른정렬(Quick Sort) – 개요 (1/2)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
8장 함수 함수의 필요성 라이브러리 함수와 사용자 정의 함수 함수의 정의, 원형, 호출 배열을 함수 인자로 전달 재귀호출.
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
컴퓨터 프로그래밍 기초 #02 : printf(), scanf()
11장. 1차원 배열.
Method & library.
JA A V W. 03.
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
CHAP 2:순환.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
제 1 장 알고리즘 : 효율, 분석, 그리고 차수.
HTTP 프로토콜의 요청과 응답 동작을 이해한다. 서블릿 및 JSP 를 알아보고 역할을 이해한다.
Ch.02 Divide and Conquer (분할정복)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
[CPA340] Algorithms and Practice Youn-Hee Han
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
제 1 강.
보고서 (due 5/8) 다음과 같은 방식으로 문제를 해결하시오. 문제 분석 알고리즘 작성 프로그램 작성 테스트 및 검증
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
메모리 타입 분석을 통한 안전하고 효율적인 메모리 재사용
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
문자열 컴퓨터시뮬레이션학과 2015년 봄학기 담당교수 : 이형원 E304호,
Fucntion 요약.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
[CPA340] Algorithms and Practice Youn-Hee Han
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
함수(Function) ◈ 함수의 개념 및 사용 이유 ◈ 함수 정의, 호출 및 선언 ◈ 지역변수와 전역변수 ◈ return 문
2nd day Indexing and Slicing
알고리즘 알고리즘이란 무엇인가?.
디버깅 관련 옵션 실습해보기 발표 : 2008년 5월 19일 2분반 정 훈 승
에어 PHP 입문.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
빠른정렬(Quick Sort) – 개요 (1/2)
Flow Diagram IV While.
CHAP 2:순환.
Homework #8 (실습 #7) [1/2] 다음을 수행하는 PHP 프로그램을 작성하여 프로그램과 결과물을 프린트하여 제출한다. sin(45º), cos(45º), tan(45º)를 출력하는 프로그램을 작성하시오. 피보나치 수를 구하는 함수 fib($n)을 작성하고,
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
Chapter 10 데이터 검색1.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
Python.
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
어서와 C언어는 처음이지 제21장.
개정판 누구나 즐기는 C언어 콘서트 제13장 동적 메모리 출처: pixabay.
빠른정렬(Quick Sort) – 개요 (1/2)
Report #2 (기한: 3/16) 데이터 구조 과목의 수강생이 50명이라고 가정한다. 이 학생(학번은 2016????으로 표현됨)들의 중간 시험(0~100), 기말 시험(0~100) 성적을 성적 파일에 작성하라(프로그램을 통해서 또는 수작업으로). 성적 파일을 읽어들여서.
7 생성자 함수.
6 객체.
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

[CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr Ch.01 알고리즘 개요 (효율, 분석, 차수) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

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

알고리즘 과목의 학습 목표 Design(설계): 다양한 문제에 대해, 알고리즘을 설계하는 기법을 배운다. Analysis(분석): 알고리즘을 분석하여 시간/공간의 계산 복잡도를 구하는 방법을 배운다. Computational Complexity(계산 복잡도) - 시간(time): CPU - 공간(storage): 메모리

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

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

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

문제의 표기 예 문제: 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: “아니오”

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

Java와 의사코드의 차이점 (1/3) 배열 인덱스의 범위에 제한 없음 지역배열에 변수 인덱스 허용 의사코드는 임의의 범위 값 사용 가능 (예: int x[5..10];) 지역배열에 변수 인덱스 허용 예: keytype[] S = new keytype[2..n]; S가 2부터 n까지 첨자를 가진 배열 Java에서는 0부터 시작되는 숫자 인덱스만 가능

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

Java와 의사코드의 차이점 (3/3) 제어 구조 프로시저와 함수의 구분 repeat (n times) { … } for 루프 while 루프 프로시저와 함수의 구분 함수: type fname (…) {… return x;} 알고리즘 1.1: 순차검색 (P. 5) 알고리즘 1.2: 배열의 수 더하기 (P. 7) 프로시저: void pname(…) {…} 알고리즘 1.3: 교환정렬 (P. 8) 알고리즘 1.4: 행렬곱셈 (P. 9)

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

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

순차검색 (Sequential Search) (3/3) 키와 같은 항목의 위치에 따라 다름 최악의 경우: n 평균의 경우: n/2 좀 더 빨리 찾을 수는 없는가? 사실상 더 이상 빨리 찾을 수 있는 알고리즘은 존재하지 않는다. 배열 S에 있는 항목에 대한 정보가 전혀 없는 상황에서, 모든 항목을 검색하지 않고 임의의 항목 x를 항상 찾을 수 있다는 보장이 없음. 만약, 배열 S가 정렬되어 있다는 정보가 존재한다면?  이진검색 알고리즘 적용가능

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

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

이진검색 (Binary Search) (3/3) 최악의 경우에 대한 비교 횟수를 (개략적으로) 분석해 본다. 최악의 경우: x가 배열 S에 저장된 값들보다 클 때 (즉, 검색을 실패할 때) 배열의 크기가 32라면  6번의 비교가 필요하다. 이때, 6 = lg 32 + 1이다. 그림 1.1참고 배열의 크기가 64라면  7번의 비교가 필요하다. 이때, 7 = lg 64 + 1이다. 배열의 크기가 2k라면  k+1번의 비교가 필요하다. 이때, k+1 = lg 2k + 1이다. … 이분검색 알고리즘으로 키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야 하는가? while 문을 수행할 때마다 검색 대상의 크기가 절반으로 감소하기 때문에, n = 2k라 하면 최악의 경우에 lg n + 1번을 비교함 [note] lg n = log2n

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

[실습 1] 순차검색과 이진검색 순차검색과 이진검색에 대한 실제 Java 프로그램을 작성해보자. SearchMain.java 를 분석하기 완성되지 않은 다음 두 함수를 작성한다. public static int sequentialSearch() public static int binarySearch() [주의] 위 Java 코드에서 배열의 인덱스는 0 부터 시작하여 n-1 까지 유효하다. 교재 알고리즘의 의사코드와 다르게, 검색 결과 존재하지 않으면 -1을 리턴 num 변수 값을 키워가며 각 함수에 대한 수행 시간을 비교한다. num 값이 1000, 10000, 100000, 1000000 일 때의 각 함수에 대한 수행시간은? int[] s = new int[n]

피보나찌(Fibonacci) 수열 피보나찌 수열의 정의 예: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

자연계의 피보나찌 수열

피보나찌 수 구하기 – 재귀 알고리즘 (1/4) 문제: n번째 피보나찌 수를 구하라. (교재: 알고리즘 1.6) 재귀(recursive) 알고리즘: long fib(int n) { if (n <= 1) return n; else return (fib(n-1) + fib(n-2)); } 실제 Java 코딩시에 long 타입 사용할 것!

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

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

피보나찌 수 구하기 – 재귀 알고리즘 (4/4) 정리: 재귀적 알고리즘으로 구성한 재귀 트리의 마디의 수를 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 > 23/2 ( 2.83) [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번째 피보나찌 수를 구하라. (교재: 알고리즘 1.6) 반복(iterative) 알고리즘: int fib2 (int n) { index i; int[] f = new int[n+1]; 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]; 실제 Java 코딩시에는 long 타입 사용할 것!

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

피보나찌 수 구하기 – 재귀 vs. 반복 노드 하나(혹은 항 하나) 계산에 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

Factorial 구하기 – 재귀 vs. 반복 Iterative definition of factorial Recursive definition of factorial Recursive Definition A의 정의 파트에 다시 A를 사용하는 정의 Page 29

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

[실습 2-1] 재귀적 이진 검색 재귀적 이진검색에 대한 실제 Java 프로그램을 작성해보자. SearchMain.java 를 분석하기 완성되지 않은 다음 함수를 작성한다. public static int recursiveBinarySearch(int low, int high) [주의] Java에서 배열의 인덱스는 0 부터 시작하여 n-1 까지 유효하다. 교재 알고리즘의 의사코드와 다르게 검색 결과 존재하지 않으면 -1을 리턴 num 변수 값을 키워가며 각 함수에 대한 수행 시간을 비교한다. num 값이 1000, 10000, 100000, 1000000 일 때의 각 함수에 대한 수행시간은?

[실습 2-2] 피보나치 수열 피보나치 수열에 대한 재귀 알고리즘과 반복 알고리즘을 Java 프로그램으로 작성해보자. FibonacciMain.java 를 분석하기 완성되지 않은 다음 두 함수를 작성한다. public static long iterativeFibonacci(int num) public static long recursiveFibonacci(int num) num 값을 키워가며 각 함수에 대한 수행 시간을 비교한다. 최대한 큰 num 값을 할당해보자. Iterative 방법에서는 Fibonacci 값에 대한 long 의 제한 범위 내의 가장 큰 num 값이 무엇인지 확인해보자. Recursive 방법에서는 참을 수 있는 시간 한도 내에서 가장 큰 num 값이 무엇인지 확인해보자.