제1장 자료구조를 배우기 위한 준비.

Presentation on theme: "제1장 자료구조를 배우기 위한 준비."— Presentation transcript:

1 제1장 자료구조를 배우기 위한 준비

2 자료구조 자료구조(Data Structure): 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체
데이터를 정돈하는 목적: 프로그램에서 저장하는 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서 자료구조를 설계할 때에는 데이터와 데이터에 관련된 연산들을 함께 고려해야 한다.

3 추상데이터타입 추상데이터타입(Abstract Data Type)은 데이터와 그 데이터에 대한 추상적인 연산들로써 구성
‘추상’의 의미: 연산을 구체적으로 어떻게 구현하여야 한다는 세부 명세를 포함하고 있지 않다는 의미 자료구조는 추상데이터타입을 구체적(실제 프로그램)으로 구현한 것

4 추상데이터타입과 자료구조 관계 추상데이터타입 (ADT) 자료구조 구체화된 관련 연산 관련 연산 구현 데이터 + 데이터 +

5 ADT, 자바 인터페이스, 자료구조와 클래스와의 관계
추상데이터타입 (ADT) 자료구조 자바 Interface 자바 Class public interface intf{ 관련 연산들의 메소드 헤더 선언 } public class ds implements intf{ 생성자 인터페이스의 각 메소드 내부(body) 구현 구현

6 1-2 수행시간의 분석 자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행시간으로 측정
자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행시간으로 측정 자료구조에 대한 연산 수행시간 측정 방식은 알고리즘의 성능을 측정하는 방식과 동일 알고리즘의 성능: 수행시간을 나타내는 시간복잡도(Time Complexity)와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간복잡도(Space Complexity)에 기반하여 분석

7 대부분의 경우 시간복잡도만을 사용하여 알고리즘의 성능을 분석, 주어진 문제를 해결하기 위한 대부분의 알고리즘들이 비슷한 크기의 메모리 공간을 사용하므로
알고리즘의 성능은 알고리즘을 구현한 프로그램을 실제로 컴퓨터에서 실행시킨 후 실행 완료까지 소요된 시간으로 측정할 수도 있다. 실제 측정된 시간으로 알고리즘의 성능을 객관적으로 평가하는 데는 한계가 존재한다. 프로그래머의 숙련도, 구현에 사용된 프로그래밍 언어의 종류 그리고 알고리즘을 실행한 컴퓨터의 성능에 따라서 수행시간은 얼마든지 달라질 수 있기 때문

8 시간복잡도 시간복잡도는 알고리즘(연산)이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다.
시간복잡도는 알고리즘(연산)이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다. 기본 연산(Elementary Operation)이란 탐색, 삽입이나 삭제와 같은 연산이 아닌, 데이터 간 크기 비교, 데이터 읽기 및 갱신, 숫자 계산 등과 같은 단순한 연산을 의미

9 4 종류의 분석 최악경우 분석(Worst-case Analysis) 평균경우 분석(Average-case Analysis)
최선경우 분석(Best-case Analysis) 상각분석(Amortized Analysis) amortize는 “분할 상환하다”라는 뜻을 가지고 있다. 그리고 상각(償却)은 “보상하여 갚아주다”라는 뜻

10 일반적으로 알고리즘의 수행시간은 최악경우 분석으로 표현
일반적으로 알고리즘의 수행시간은 최악경우 분석으로 표현 최악경우 분석: ‘어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다’라는 상한(Upper Bound)의 의미 평균경우 분석: 입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등분포(Uniform Distribution)를 가정 최선경우 분석: 가장 빠른 수행시간을 분석 - 최적(Optimal) 알고리즘을 찾는데 활용 상각분석: 일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산 횟수로 나누어 수행시간을 분석

11 등교 시간 분석 집을 나와서 지하철역까지는 5분, 지하철을 타면 학교까지 30분, 강의실까지는 걸어서 10분 걸린다
집을 나와서 지하철역까지는 5분, 지하철을 타면 학교까지 30분, 강의실까지는 걸어서 10분 걸린다 최선경우: 집을 나와서 5분 후 지하철역에 도착하고, 운이 좋게 바로 열차를 탄 경우를 의미한다. 따라서 최선경우 시간은 = 35분 최악경우: 열차에 승차하려는 순간, 열차의 문이 닫혀서 다음 열차를 기다려야 하고 다음 열차가 10분 후에 도착한다면, 최악경우는 = 45분

12 평균 시간: 대략 최악과 최선의 중간이라고 가정했을 때, 40분이 된다.
평균 시간: 대략 최악과 최선의 중간이라고 가정했을 때, 40분이 된다. (a) 최선 경우 (b) 최악 경우 (c) 평균 경우

13 상각분석: 단순히 한 번의 등교시간을 분석하는 것이 아니라, 예를 들어, 한 학기 동안의 등교시간을 분석해본다는 점에서 그 의미를 갖는다.
한 학기 동안 100번 학교에 간다고 하면, 최악경우는 x 45 = 4,500분 한 학기 동안에 항상 지하철만 타고 또 최악경우인 45분만 걸린다고 가정하여 계산된 4,500분은 실제 등교 시간보다 지나치게 긴 시간 실제로 어떤 날은 택시를 타고도 학교에 갈 수 있으며, 지하철이나 버스를 타고 학교에 갈 수도 있기 때문 상각분석은 한 학기 동안 학교에 가는데 소요된 시간을 모두 합해서 학교에 간 횟수인100으로 나눈 값을 1회 등교 시간으로 분석

14 학교에 가는 여러 가지 방법

15 상각분석은 일련의 연산, 즉, N회의 연산을 수행한 총 시간을 N으로 나누어 1회 연산의 평균 수행시간을 계산
상각분석은 입력의 확률분포에 대한 가정이 필요 없으며, 최악경우 분석보다 매우 정확한 분석이 가능하다. 단, 상각분석이 가능한 알고리즘들은 시간이 아주 오래 걸리는 연산과 짧은 시간이 걸리는 연산들이 뒤섞여서 수행되는 공통점을 가진다.

16 1-3 수행시간의 점근표기법 수행시간은 알고리즘이 수행하는 기본 연산 횟수를 입력 크기에 대한 함수로 표현
수행시간은 알고리즘이 수행하는 기본 연산 횟수를 입력 크기에 대한 함수로 표현 이러한 함수는 다항식으로 표현되며 이를 입력의 크기에 대한 함수로 표현하기 위해 점근표기법(Asymptotic Notation)이 사용 O (Big-Oh)-표기법 Ω (Big-Omega)-표기법 Θ (Theta)-표기법

17 O (Big-Oh)-표기법 [O-표기의 정의]
모든 N ≥ N0에 대해서 f(N) ≤ cg(N)이 성립하는 양의 상수 c와N0가 존재하면, f(N) = O(g(N))이다. O-표기의 의미: N0과 같거나 큰 모든 N (즉, N0 이후의 모든 N) 대해서 f(N)이 cg(N)보다 크지 않다는 것 f(N) = O(g(N))은 N0 보다 큰 모든 N 대해서 f(N)이 양의 상수를 곱한 g(N)에 미치지 못한다는 뜻 g(N)을 f(N)의 상한(Upper Bound)이라고 한다.

18 f(N) = O(g(N))

19 [예제] f(N) = 2N2 + 3N + 5이면, 양의 상수 c 값을 최고 차항의 계수인 2보다 큰 4를 택하고 g(N) = N2으로 정하면, 3보다 큰 모든 N에 대해 2N2 + 3N + 5 < 4N2이 성립한다. 즉, f(N) = O(N2)이다. 물론 2N2 + 3N + 5 = O(N3)도 성립하고, 2N2 + 3N + 5 = O(2N)도 성립한다. 그러나g(N)을 선택할 때에는 정의를 만족하는 가장 차수가 낮은 함수를 선택하는 것이 바람직하다. f(N) ≤ cg(N)을 만족하는 가장 작은 c값을 찾지 않아도 된다. 왜냐하면 f(N) ≤ cg(N)을 만족하는 양의 상수 c와 N0가 존재하기만 하면 되기 때문이다.

20 주어진 수행시간의 다항식에 대해 O-표기를 찾기 위해 간단한 방법은 다항식에서 최고 차수 항만을 취한 뒤, 그 항의 계수를 제거하여 g(N)을 정한다.
예를 들어, 2N2 + 3N + 5에서 최고 차수항은 2N2이고, 여기서 계수인 2를 제거하면 N2이다. 따라서 2N N + 5 = O(N2)이다.

21 자주 사용되는 함수의 O-표기와 이름 O(1) 상수시간(Constant Time)
O(logN) 로그(대수)시간(Logarithmic Time) O(N) 선형시간(Linear Time) O(NlogN) 로그선형시간(Log-linear Time) O(N2) 제곱시간(Quadratic Time) O(N3) 세제곱시간(Cubic Time) O(2N) 지수시간(Exponential Time)

22 O-표기의 포함 관계 5, 100 O(1) O(logN) 2logN O(N) O(N2) 4N+8 O(N3), O(Nk)
5, 100 O(1) O(logN) 2logN O(N) O(N2) 4N+8 O(N3), O(Nk) O(2N) NlogN + N 3N2+5N+4 2N3+3N2-N+1 2N O-표기의 포함 관계

23 함수의 증가율 비교

24 1-4 자바 언어에 대한 기본적인 지식 자바 언어는 객체지향 프로그래밍 언어로서 클래스를 선언하여 데이터를 저장하고 메소드(Method)를 선언하여 객체들에 대한 연산을 구현한다. 인스턴스 변수: 객체에 정보를 저장 객체 생성자(Constructor): 객체를 생성 메소드: 객체 혹은 객체 내부 인스턴스 변수에 대한 연산 수행

25 [예제] 학생을 객체로 표현하기 위해 Student 클래스
각 Student 객체는 이름과 학번을 각각 저장하는 인스턴스 변수 name과 id를 가짐

26 데이터를 저장하고 있는 객체들을 위한 자료구조는 별도의 클래스로 구현
자료구조 객체 내부에 저장되어있는 객체를 탐색하고, 삭제하며, 새 객체를 삽입하는 등의 연산을 수행하는 메소드들도 자료구조의 클래스 내에 정의

27 배열(Array): 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 있는 기초적인 자료구조
각 항목이 하나의 원소에 저장

28 if-문: 조건문으로서 하나 또는 여러가지 조건을 검사하도록 선언
조건식이 true이면 해당 명령문을 수행하고, false이면 else의 명령문을 수행

29 반복문: for-문은 두 가지 방식으로 사용가능한데, 초기화식, 조건식, 증감식을 통해 반복문을 제어하는 방식과 배열의 모든 원소들을 차례로 읽으며 명령문을 처리하는 방식 while -문은 조건식이 만족된 동안에만 반복 수행

30 Comparable 은 java.lang에 선언된 인터페이스
객체의 하나의 멤버만을 기준으로 객체들을 정렬할 때 사용 compareTo 메소드 x.compareTo(y)는 • x < y이면 음수 • x = y이면 0 • x > y이면 양수 리턴

31 Comparable 인터페이스는 각각 다른 클래스를 선언할 때마다 객체들을 정렬하기 위해 별도의 비교 메소드를 일일이 선언해야하는 불편을 덜어줌
이러한 정렬 메소드들은 거의 동일할 것이고 단지 객체의 멤버를 비교하는 부분만 다름

32 Comparable 인터페이스는 일반적으로 compareTo메소드를 재정의하여 두 개의 객체를 비교
String, Date와 Integer, Character, Double 등의 Wrapper 클래스에는 이미 Comparable 인터페이스가 구현되어 있으므로 compareTo 메소드를 재정의할 필요 없음 Comparable 인터페이스는 일반적으로 다음과 같이 선언하여 사용

33 Comparator: java.util 에 선언된 인터페이스
한 프로그램 내에서 동일한 타입의 객체들을 여러 개의 멤버를 기준으로 나열할 수 있게 해줌 compare 메소드를 가짐

34 Comparator 인터페이스는 일반적으로 비교에 기준이 되는 멤버를 위한 별도의(제3의) 클래스를 다음과 같이 선언하여 사용

35 Student Class

36

37 Main Class

38

39 수행 결과

40 import 문은 이미 정의되어 있는 클래스를 사용하기 위한 선언문
Java.lang은 기본적으로 자바에서 제공하는 패키지로서 import할 필요가 없음 유용한 유틸리티를 제공하는 패키지인 java.util의 클래스들 중에 사용되는 이 후에 클래스들 • import java.util.ArrayList; • import java.util.LinkedList; • import java.util.List; • import java.util.Queue; • import java.util.PriorityQueue; • import java.util.NoSuchElementException; • import java.util.EmptyStackException;

41 1-5 순환(Recursion) 순환(Recursion): 메소드의 실행 과정 중 스스로를 호출하는 것
순환은 팩토리얼, 조합을 계산하기 위한 식의 표현, 무한한 길이의 숫자 스트림을 만들기, 분기하여 자라나는 트리 자료구조, 프랙털(Fractal) 등의 기본 개념으로 사용

42 메소드가 자기 자신을 호출할 때 무한 호출을 방지해야 함
다음의 자바 프로그램을 실행시키면 StackOverflowError 발생 이는 스스로의 호출을 중단시킬 수 있는 조건문이 없기 때문

43 StackOverflowError 무한 호출을 방지하기 위해 메소드에 count 매개변수를 전달하고, 자신을 호출할 때마다 count를 1 감소시키며, 메소드 내부의 if-문으로 count가 0과 같거나 작은지 검사하도록 하여 count가 0보다 작아지는 경우 더 이상 메소드를 호출하지 않도록 제어

44

45 순환으로 구현된 메소드는 두 부분으로 구성 하나는
기본(Base) case: 스스로를 더 이상 호출하지 않는 부분 순환 case: 스스로를 호출하는 부분 무한 호출을 방지하기 위해 선언한 변수 또는 수식의 값이 호출이 일어날 때마다 순환 case에서 감소되어 최종적으로 if-문의 조건식에서 기본 case를 실행하도록 제어해야 함

46 팩토리얼 계산 자바 프로그램 Line 10에서 factorial(4)로 메소드를 호출
[그림]의 번호 순서대로 수행되어 24를 출력

47 반복문으로 팩토리얼을 계산하는 프로그램 반복문을 이용한 계산은 메소드 호출로 인해 시스템 스택을 사용 하지 않으므로 순환을 이용한 계산보다 매우 간단하며 메모리도 적게 사용

48 꼬리 순환(Tail Recursion): 메소드의 마지막 부분에서 순환하는 것
꼬리 순환은 반복문으로 변환하는 것이 수행 속도와 메모리 사용 측면에서 효율적임

49 일반적으로 순환은 프로그램(알고리즘)의 가독성을 높일 수 있는 장점을 갖지만 시스템 스택을 사용하기 때문에 메모리 사용 측면에서 비효율적임
반복문으로 변환하기 어려운 순환도 존재하며, 억지로 반복문으로 변환하는 경우 프로그래머가 시스템 스택의 수행을 처리해야 하므로 프로그램이 매우 복잡해질 수 밖에 없음 반복문으로 변환된 프로그램의 수행 속도가 순환으로 구현된 프로그램보다 항상 빠르다는 보장 없음

50 요약 자료구조는 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체이다.
자료구조는 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체이다. 추상데이터타입은 데이터와 그 데이터에 관련된 추상적인 연산들로서 구성된다. 추상적이란 연산을 구체적으로 어떻게 구현하여야 한다는 상세를 포함하고 있지 않다는 뜻이다. 자료구조는 추상데이터타입을 구체적(실제 프로그램)으로 구현한 것이다. 수행시간은 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.

51 알고리즘의 수행시간 분석 방법: 최악경우, 평균경우, 최선경우 분석, 상각분석
점근표기법: 입력 크기가 증가함에 따른 수행시간의 간단한 표기법 O(Big-Oh)-표기: 점근적 상한 Ω(Big-Omega)-표기: 점근적 하한 Θ(Theta)-표기: 동일한 증가율

52 • 자바 언어는 객체지향 프로그래밍 언어로서 클래스를 선언하여 데이터를 객체에 저장하고 메소드(Method)를 선언하여 객체들에 대한 연산 구현
• Comparable 인터페이스는 정렬이 가능한 객체를 비교하는데 사용. 인터페이스는 각각 다른 클래스를 선언할 때마다 객체들을 정렬하기 위해 별도의 비교 메소드를 일일이 선언해야하는 불편을 덜어 줌. 일반적으로 compareTo메소드를 재정의하여 2 개의 객체 비교 • Comparator는 한 프로그램 내에서 동일한 타입의 객체들을 여러 개의 멤버를 기준으로 나열할 수 있게 해줌

53 • 순환(Recursion): 메소드가 스스로를 호출하는 것
• 순환으로 구현된 메소드는 두 부분으로 구성 기본(Base) case: 스스로를 더 이상 호출하지 않는 부분 순환 case: 스스로를 호출하는 부분 무한 호출을 방지하기 위해 선언한 변수 또는 수식의 값이 호출이 일어날 때마다 순환 case에서 감소되어 최종적으로 if문의 조건식에서 기본 case를 실행하도록 제어해야 함 • 꼬리 순환(Tail Recursion): 메소드의 마지막 부분에서 순환하는 것. 꼬리 순환은 반복문으로 변환하는 것이 수행 순환은 프로그램(알고리즘)의 가독성을 높일 수 있다는 장점을 갖지만, 시스템 스택을 사용하기 때문에 메모리 사용 측면에서는 비효율적임