제 1 장. 자료구조와 알고리즘

0. 선행학습

0. 기본 개념_1 정의 : 자료간의 상호 관계를 파악하여, 기억장치 공간에 자료 표현 방법과 저장 방법을 연구하고, 이를 통한 여러 가지 작업을 수행하기 위한 알고리즘을 연구 하는 것. 목적: 컴퓨터 처리 시간과 기억공간을 줄이는 것. (decrease the computer time & storage) 좋은 자료구조 ⇒ 좋은(효율적인) 프로그램. ☞ 즉, 취급하려는 자료 항목간의 관계

0. 기본 개념_2 관련 용어 。순차 메모리(sequential(ordered)memory) 구조: ⇒ 순차 위치(sequence of locations) 。구조(structure): 집합 요소간의 관계성(relationship between the individual elements of a group) 。리스트(list) : 항목 순으로 형성된 가장 간단한 형태, 메모리 저장 용이. 。테이블(table(matrix)) : 。자료 요소들간의 구조적 관계성. 。노드의 집합(set of nodes) <참고> 노드(nodes) : records, entity, bead, item, elements

0. 기본 개념_3 。파일(file) : 보조기억장치에 저장된 레코드의 집합체 <참고> 레코드(record) : 필드의 집합체 。트리(tree) 구조 : 계층적 구조를 표현한 자료구조

컴퓨터 내에 쉽게 구현(컴퓨터가 이해하게)되어야 함. (2) DS를 저장할 때는 처리에 대하여, 0. 자료 구조의 특징 (1) 구조가 명확해야 하고, 컴퓨터 내에 쉽게 구현(컴퓨터가 이해하게)되어야 함. (2) DS를 저장할 때는 처리에 대하여, 가장 효율이 좋은 저장 방법을 취한다. 。 기억 용량 적게 。 처리 속도 빠르게 。 범용성 。 프로그래밍이 용이하게

(1) 폰 노이만(Von Neumann)방식 구조의 이해 : 0. Why Data Structures? (1) 폰 노이만(Von Neumann)방식 구조의 이해 : 。저장 프로그램방식(stored program method) ⇒ 직렬 처리(serial processing) 。저장 구조(storage structure) : 제어장치의 제어에 의한 직렬 처리 ⇒ 디지털 컴퓨터 <참고> 비 폰 노이만(non-Von Neumann) 구조 : 병렬 처리(parallel processing) 방식

0 연산(operation) : 순차(직렬, serial)연산 ⇒ 연산자 순차연산(sequenctial operation) : 순차적인 주소 공급 방식 ⇒고속 요구됨 cf. IR(instruction register)/ PC(program counter) 0 표현 단위 : 정보 단위 ⇒ bit →byte(word) →item(field) → record(array) →file ⇒ DB

(2) 저장 매체별, 통신에 의한 정보 단위 변형 : 레코드 : 사용자(프로그램) 관점 : (논리 (레코드)) : 기계(통신) 관점 : block(물리 레코드) o 블록킹 VS. 비블록킹 논리 레코드 ◀============▶ 물리 레코드 비블로킹(deblocking) ← | → 블로킹(blocking) ↓ 블로킹 요인(blocking factor)

1.1 자료구조의 개념

1.1 자료구조의 개념 Data : values, Facts Information(정보) : Data ⇒ Processing(computer) ⇒ Information 컴퓨터(프로그램)의 효율성 요인 : 좋은 알고리즘, 자료구조 선택 알고리즘(algorithm) : 입력 자료 ⇒ 유한 시간내 (finiteness) ⇒ 결과 생성 과정을 제어하는 일련의 명령어 ▶ Program : 무한성(infiniteness)도 가짐 DS : 저장공간에 자료의 표현방식, 그들의 관계성 표현 방법의 정의하는 방법 ▶ cf. Algorithms + DS = Programs by Niklaus Wirth

1.1.1 자료형(1/5) ￭ 자료형(Data Types) p14 ⇒ 여러 방 법을 통해 조직화되어 자료구조를 형성 ⇒ 여러 방 법을 통해 조직화되어 자료구조를 형성 원시 자료형 (Primitive data type) 복합 자료형 (Compound data type) 정수(Integer) 타입 문자열(String) 타입 논리형(Boolean) 타입 문자(Character) 타입 <자료형 종류>

1.1.1 자료형(2/5) ￭ 정수형 (Integer) 이진 연산자와 단일 연산자에 의해 연산을 수행 ※ 이진 연산자 : 덧셈, 뺄셈, 곱셈, 나눗셈, 지수승과 같이 두 개의 피연산자(operand)를 이용해서 연산을 수행 ※ 단일(항) 연산자 : 숫자의 부호를 바꾸는 부정(Negation)과 같이 하나의 피연산자만을 이용해서 연산을 수행 {…, -(n-1), -n, …, -2, -1, 0, 1, 2, …, n, n+1, …}

1.1.1 자료형(3/5) ￭ 논리형(Boolean) p15 연산을 통해 참(true) 또는 거짓(false)의 값을 갖고, 연산자는 크게 논리 연산자와 관계 연산자로 나뉘어짐 ※ 논리 연산자 : not, and, or ※ 관계 연산자 : <, >, ≤, ≥, ≠, = 등

1.1.1 자료형(4/5) ￭ 블리언 자료형의 연산 T : 참 값(true), F : 거짓 값(false), not : 첫 번째 값에 대한 연산수행 연산 결과 첫 번째 값 두 번째 값 not and or T F

1.1.1 자료형(5/5) ￭ 문자(Character)와 문자열(String) ※ 문자(Character) 가장 원시적인 데이터 구조로부터 얻어지는 자료형. 숫자, 영문자, 일부 특수 문자가 포함되어 이들 문자들을 이용해 복합 자료형을 얻을 수 있는데, 이는 하나 이상의 문자들을 나열 함으로서 복합 자료형인 문자열을 얻을 수 있음을 말한다. ※ 문자열(String) 문자열을 만들기 위해 사용되는 문자 집합을 알파벳이라 하며, 문자열의 처음과 끝은 인용부호로서 표시 프로그래머는 프로그래밍 언어를 이용해서 여러 가지 방법으로 이러한 자료형을 변수에 할당한다

1.1.2 자료의 표현 ￭ 보수(Complement) 컴퓨터 내에서 자료에 대한 음수 표현 기법으로 주로 사용 정수 이진수 1의 보수 2의 보수 -3 -2 -1 +1 +2 +3 -011 -010 -001 +000 +001 +010 +011 1100 1101 1110 0000 0001 0010 0011 1111 <정수의 표현>

1.2 알고리즘(Algorithm)

1.2 알고리즘(1/4) 정의 : 어떤 문제를 해결하기 위해 모호함이 없는 간단한 명령들로 구성된 일련의 순서적 과정 <자료구조와 알고리즘>

1.2 알고리즘(2/4) ￭ 알고리즘이 적용할 수 있는 최소(요구)조건 조건 1. 외부에서 0개 이상의 입력을 받아들여, 하나 이상의 출력을 생성한다. (입력, 출력) 조건 2. 각 단계가 단순하고 모호하지 않아야 한다. (명확성, definiteness) : 명령의 명확성, 모호성 배제 조건 3. 한정된 수의 작업 후에는 반드시 끝나야 한다. (유한성, finiteness) : 반드시 종료 cf. 프로그램은 무한성(infinite looping)도 가짐 조건 4. 모든 명령이 수행 가능해야 한다. 효과성(effectiveness) 조건 5. 효율적이어야 한다.

1.2 알고리즘(3/4) ￭ 알고리즘 기술 방법(도구) p18 기술법 1. 사람들이 사용하는 자연어(Nature Language) 기술법 2. 플로차트(Flowchart) 기술법 3. 의사코드(Pseudo-code) 기술법 4. 프로그래밍 언어(Programming Language) ◎ 알고리즘 언어의 종류 ① 일반 언어 : ALGOL, ALGOL-W, APL, COBOL, FORTRAN, LISP, PASCAL, PL/I, SNOBOL, C, Java ○ 선택이 어려운 이유 : 。알고리즘은 특정 언어의 특성 반영없이 작성 가능해야 함. 。기존 언어의 기법 의존 。특정 언어의 사용 가능 인원의 제약 ② 전용(문) 언어 SPARKS(Structured Programming : A Reasonably Komplete Set, Smart Programmers Are Required to Know)

1.2 알고리즘(4/4) ￭ 알고리즘 기술 방법 (예 - 최대값 찾기)

1.3 알고리즘 성능분석 p19

1.3 알고리즘 성능분석(1/2) ￭ 알고리즘 성능 측정 방법 - 성능 요인 : 실행시간, 사용공간 크기 ➀ 시간 복잡도(time complexity) : 명령의 개수(T(n)) ➁ 공간 복잡도(space complexity) : 메모리 크기 ￭ 알고리즘 성능분석 예 (- 최대값 찾기) p19 - 자료가 5개가 있는 경우 1. temp에 score 배열의 0번째 값을 저장한다. 2. temp에 저장된 값과 score 배열의 1번째 값 중 큰 것을 temp에 저장한다. 3. temp에 저장된 값과 score 배열의 2번째 값 중 큰 것을 4. temp에 저장된 값과 score 배열의 3번째 값 중 큰 것을 5. temp에 저장된 값과 score 배열의 4번째 값 중 큰 것을 6. temp를 반환한다.

1.3 알고리즘 성능분석(2/2) ￭ 알고리즘 성능분석 (예 - 최대값 찾기) ※ 알고리즘 종류 ※ 알고리즘별 연산 횟수 ①번 방법 ②번 방법 ③번 방법 대입연산 1 n+1 n*n+1 덧셈연산 n n*n 곱셈연산 전체 연산 수 2 2n+1 2n2+1

1.4 알고리즘 성능 표기법 ￭ 알고리즘의 차수(알고리즘의 복잡도) ⇒ 시․공간 복잡도(complexity) ① 시간 복잡도(time complexity) : 문제 해결위한 알고리즘 실행시 사용되는 기본 연산의 빈도수를 차수(degree)로 표현. ㉠ O(big oh)-표시법 : 연산 차수가 가장 높은 것 선택, 알고리즘 차수로 사용. ⓐ 다항 시간(polynomial time) : 복잡도가 n2, nlog2n, n, log2n과 같이 n상수 다항식 표현. ☞ n이 대단히 크지 않은 경우 쉽게 해결 가능 ⓑ 지수 시간(exponential time) : 복잡도 차수가 2n , nn, n!과 같이 n 지수로 표현. ☞ n이 작은 값인 경우 해결 가능 ㉡ Ω(big omega)-표기법 : 연산 차수가 가장 낮은 것 선택, 계산/차수로 사용. (예) 명령어 실행 시간과 실행 빈도수 곱, 계산 차수가 다수인 경우엔 가장 높은 항 선택

1.4.1 빅오(Big O) 표기법 (1) 빅오(Big O) 표기법 예 ② 공간 복잡도(space complexity) : 문제 해결 알고리즘 실행시의 기억 공간 의 양을 문제의 크기에 대한 함수로 표현 (예) O(1) : 입력 크기 불변 O (n) : 입력 크기 n에 비례 O(nn) : 입력 크기 n2에 비례 -------------------------------------------------------------------------------------------------- (1) 빅오(Big O) 표기법 예 T(n) = n+1 → O(n) T(n) = n → O(n)< T(n) = n2+n → O(n2) T(n) = 2n + 1 → O(n) T(n) = 2n + n2 → O(2n) ￭ 정의 : 함수 f(n), g(n)에서 n >= n0인 모든 n에 대하여 |f(n)| <= |g(n)|을 만족하는 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.

1.4.2 빅오메가(Big Ω) 표기법 ￭ 빅오(Big O) 표기법의 문제 (2) 빅오메가(Big Ω) 표기법 O(n)으로 표기할 수 있는 함수는 O(n2), O(n3) 등으로도 표기할 수 있음 – 간단한 함수 표기에 유용 (2) 빅오메가(Big Ω) 표기법 - 복잡한 함수 표기에 유용 정의 : 함수 f(n), g(n)에서 n >= n0인 모든 n에 대하여 |f(n)| >= |g(n)|을 만족하는 상수 c와 n0가 존재하면 f(n) = Ω(g(n))이다. - 연산 차수가 가장 낮은 것 선택, 계산/차수로 사용. ￭ 빅오/빅오메가 표기법 : 조건 만족범위가 서로 반대 ￭ 시간함수 O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(2n) < O(n!) < O(nn)

|g(n)| <= |f(n)| <= |g(n)| "위의 부등식을 만족하는 상수 c1, c2, n0가 존재하면 1.4.3. 빅세타(Big Θ) 표기법 ￭ 빅세타(Big Θ) 표기법 - 조건의 만족 범위가 일치함. - 빅오메가 표기법의 등식을 반대로 쓴 다음, 빅오 표기법과 겹치면 다음식이 됨. |g(n)| <= |f(n)| <= |g(n)| "위의 부등식을 만족하는 상수 c1, c2, n0가 존재하면 f(n) = Θ(g(n))이다.”

1.4.4 최선, 최악, 평균 p23 ￭ 최선, 최악, 평균 예 n개의 정수가 있는 array 배열에서 value라는 정수를 찾는다. 있으면 그 정수가 있는 위치를, 없으면 -1을 반환한다. 1. for(int i = 0; i < n; i++){ 2. if( value == array[i] ) 3. return i; 4. } 5. return -1; ※ 최선의 경우 배열의 크기에 상관없이 연산은 딱 한 번만 하므로 T(n) = 1, 즉 O(n) = 1 ※ 최악의 경우 T(n) = n, 즉 O(n) = n이다. ※ 평균적인 경우 최선의 경우가 될 확률 : 1/n이다. (1+2+...+n)*(1/n) = (n+1)/2 = T(n) 평균적인 경우는 O(n)이다.