Data Structure & Algorithms SANGJI University KO Kwangman (kkman@sangji.ac.kr)

1. 자료와 정보 자료(data) 정보(information) 현실 세계로부터의 단순한 관찰이나 측정을 통하여 수집한 사실이나 개념의 값들 또는 값들의 집합. 정보(information) 의사 결정에 도움을 주기 위해 유용한 형태로 다시 작성된(=가공) 자료.

자료구조 정의 ? 일상생활에서의 사물의 조직화 조직도 해야할일 리스트 Ticket Box

해야할일 리스트 a b c NULL C B A Ticket Box 전단(front) 후단(rear)

자료구조(data structure) 란 ? 다루고자 하는 자료 원소들(elements) 간 논리적 관계를 기술한 것 컴퓨터의 휘발성 또는 비 휘발성 메모리에 존재하는 자료의 집합 자료값에 대한 연산을 효율적으로 처리할 수 있도록 자료의 구성을 조직적이고 체계적으로 표현하는 것

자료구조의 선택 기준 자료의 양(자료가 차지하는 메모리 공간) 자료의 활용 빈도(저장 방식 결정) 사용 가능한 기억 용량(전체적인 메모리 공간) 자료의 갱신 정도 처리 시간의 제한성 프로그래밍의 용이성

자료구조의 목적 효율성(Efficiency) 추상화(Abstraction) 재사용성(Reusability) 좀 더 효율적인 알고리즘이 될 수 있도록 자료를 구조화. 추상화(Abstraction) 자료를 보다 쉽게 이해할 수 있는 방법인 추상화를 제공. 재사용성(Reusability) 모듈화되어 있고 문맥에 자유롭기(context-free) 때문에 재사용이 가능.

… 2. 알고리즘과 프로그램 최대값 탐색 프로그램 = 배열+ 순차탐색 프로그램 = 자료구조 + 알고리즘 자료구조 알고리즘 score[] 80 70 90 … 30 tmp←score[0]; for i ← 1 to n do if score[i]>tmp then tmp←score[i];

알고리즘(algorithm) 프로그램(program) 어떤 문제를 해결하기 위해 기술해 놓은 명확한 절차로, 일련의 명령(instruction 또는 step) 집합을 의미 프로그램(program) 컴퓨터가 수행할 수 있는 상세화된 명령어의 집합

알고리즘의 요건 입력(Input) 출력(Output) 명백성(Definiteness) 유한성(Finiteness) 제공되는 자료가 있을 수도 있고 없을 수도 있다. 출력(Output) 한 개 이상의 결과가 반드시 생성되어야 한다. 명백성(Definiteness) 문제 해결 단계에서 수행할 내용은 모호하지 않고 명백해야 한다. 유한성(Finiteness) 한정된 수의 단계 후에는 반드시 종료되어야 한다. 유효성(Effectiveness) 알고리즘의 모든 명령은 수행 가능한 것이어야 한다.

대표적인 알고리즘 삽입(insert) 검색/탐색(search) 삭제/제거(delete) 정렬(sorting) 반복, 순회, … 자료구조에서 새로운 자료를 삽입 검색/탐색(search) 자료구조에서 원하는 자료를 찾기 삭제/제거(delete) 자료구조에서 기존의 자료를 삭제 정렬(sorting) 자료구조에 있는 자료들을 특정 키 값에 의해서 순서대로 나열 반복, 순회, …

자료구조, 알고리즘, 프로그램 사이의 관계

알고리즘 기술 방법 영어나 한국어와 같은 자연어 흐름도(flow chart) 유사 코드(pseudo-code) C/C++/Java/…와 같은 프로그래밍 언어 1 2 3 4 5 6 7 8 9 10

자연어로 표기된 알고리즘 특징 (예) 배열에서 최대값 찾기 알고리즘 인간이 읽기가 쉽다. 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있다. (예) 배열에서 최대값 찾기 알고리즘 ArrayMax(A,n) 배열 A의 첫번쨰 요소를 변수 tmp에 복사 배열 A의 다음 요소들을 차례대로 tmp와 비교하면 더 크면 tmp로 복사 배열 A의 모든 요소를 비교했으면 tmp를 반환

흐름도로 표기된 알고리즘 특징 직관적이고 이해하기 쉬운 알고리즘 기술 방법 복잡한 알고리즘의 경우, 상당히 복잡해짐. tmp←A[0] i←1 i < n A[i]>tmp tmp←A[i] tmp no yes i++

유사코드로 표현된 알고리즘 특징 알고리즘의 고수준 기술 방법 자연어보다는 더 구조적인 표현 방법 프로그래밍 언어보다는 덜 구체적인 표현방법 알고리즘 기술에 가장 많이 사용 프로그램을 구현할 때의 여러가지 문제들을 감출 수 있다. 즉 알고리즘의 핵심적인 내용에만 집중할 수 있다.

C로 표현된 알고리즘 특징 알고리즘의 가장 정확한 기술이 가능 반면 실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있다. #define MAX_ELEMENTS 100 int score[MAX_ELEMENTS]; int find_max_score(int n) { int i, tmp; tmp=score[0]; for(i=1;i<n;i++){ if( score[i] > tmp ){ tmp = score[i]; } return tmp;

4. 자료구조의 분류