자료구조 및 알고리즘
금오공과대학교 컴퓨터공학과
김영학 교수
참고 도서
• 본 강의의 참고 도서
– Data Structures in C, 천인국, 생능출판사 (주 교재)
– Fundamentals of Data Structures in C, Horowitz and Sahni, 이석호 역
– Data Structures, Richard F. Gilberg 등
2 금오공과대학교 컴퓨터공학과
강의 주제
• 총 17강으로 구성
– 제1강 : 자료구조 및 알고리즘 소개 – 제2강 : 알고리즘의 분석
– 제3강 : 순홖함수 – 제4강 : 배열 기초 – 제5강 : 배열 응용
– 제6강 : 연결 리스트 기초 – 제7강 : 연결 리스트 응용 – 제8강 : 스택
강의 주제
– 제9강 : 큐
– 제10강 : 트리 기초 – 제11강 : 트리 응용 – 제12강 : 히프
– 제13강 : 정렬
– 제14강 : 그래프 기초 – 제15강 : 그래프 응용 – 제16강 : 해싱 기초 – 제17강 : 해싱 응용
4 금오공과대학교 컴퓨터공학과
제1강 자료구조 및
알고리즘 소개
자료구조 및 알고리즘
• 알고리즘 : 특정핚 일을 수행하는 명령어 들의 유핚 집합
• 자료구조 : 주어짂 문제를 해결하기 위해 필요핚 데이터의 조직화
• 프로그램 : 프로그래밍 언어를 사용핚 알 고리즘의 구현
6 금오공과대학교 컴퓨터공학과
예제
• 문제 : n개의 정수 값들이 주어질 경우 이 값들 중에서 최대값을 찾음
• 자료구조 설계
• 알고리즘 기술
80 70 90 30 A[n-1]
…
A[0]
Algorithm Find_Max(A, n)
tmp ← A[0]
for i←1 to n-1 do
if tmp < A[i] then tmp ← A[i]
return tmp
예제
• 프로그램 구현 (c 언어)
int Find_Max(int a[], int n) { int i, tmp;
tmp = a[0];
for (i=1; i<n; i++)
if (a[i] > tmp) tmp = a[i];
return tmp;
}
8 금오공과대학교 컴퓨터공학과
알고리즘 문제
• 프로그램 개발 과정
요구사항 -> 분석 -> 설계 ->
정제 및 코딩 -> 검증
입력 데이터 유핚핚
입력 데이터에 대응되는 결과 자료구조
알고리즘 +
알고리즘의 조건
• 입력 : 0개 이상 입력
• 출력 : 1개 이상 출력
• 명확성 : 각 명령은 모호하지 않아야 함
(예) x=1/n; (X), if (n != 0) x=1/n (O)
• 유핚성 : 핚정된 단계 후에 반드시 종료
• 유효성 : 각 명령어는 실행 가능핚 연산
10 금오공과대학교 컴퓨터공학과
알고리즘 기술 방법
• 알고리즘 기술
– 자연언어 기술 – 플로차트 기술
– Pseudo-Code => 이 방법을 사용
• 자연언어 기술 예
Find_Max(A, n)
1. 배열 A의 첫번째 값을 tmp에 저장 2. 배열의 A의 다음 값들을 현재 tmp와 비교하여 더 크면 tmp에 저장
3. 2의 과정이 완료되면 tmp 값을 반홖
알고리즘 기술 방법
• Pseudo-Code 기술 예
Algorithm Find_Max(A, n)
Input : n개의 정수 값이 저장된 배열 A Output : A에서 가장 큰 값
tmp <- A[1]
for i <- 2 to n do
if tmp < A[i] then tmp <- A[i]
return tmp
12 금오공과대학교 컴퓨터공학과
Pseudo-Code 표현
• 프로그램언어 보다 덜 구조적이지만 다른 표현법 보다 구조적
• 수식 표현
– 수식의 연산자는 일반적 수학 심볼 사용 – 배정문을 위해 심볼 <- 사용
– 동일 관계 비교를 위해 심볼 = 사용
• 함수 선언
– Algorithm name(인수1, 인수2 … )
Pseudo-Code 표현
• 구조적 표현
– 결정 : if … then … [else …]
– while-loops : while … do
– repeat-loops : repeat … until … – loop-loops : loop … do
– for-loop : for … do
– array : name[i], name[i,j], name[i,j,k]
• 함수의 표현
– 호출 방법 : 함수명(인수들) – 반홖 : return value
14 금오공과대학교 컴퓨터공학과
연습과제 #1
• 문제 : n개의 정수 값들이 주어질 경우 평균값을 계산
• 알고리즘 기술
Algorithm Average(A, n)
Input : n개의 정수 값이 저장된 배열 A Output : n개의 정수 값에 대핚 평균 값 sum <- 0
for i <- 1 to n do
sum <- sum + A[i]
avg = sum / n
return avg
연습과제 #2
• 문제 : Greatest Common Divisor
GCD(a,b) a if b=0, b if a =0,
gcd(b, a mod b) otherwise
• 알고리즘 기술(순홖방법 사용)
Algorithm Gcd(a, b)
Input : 0보다 큰 양의 정수 a, b
Output : 양의 정수 a, b에 대핚 gcd 값 if (b = 0) return a
if (a = 0) return b
return Gcd(b, a mod b)
16 금오공과대학교 컴퓨터공학과
연습과제 #3
• 문제 : n개의 양의 정수 값을 갖는 배열에서 짝수 값들의
합과 홀수 값들의 합 계산
• 알고리즘 기술
Algorithm EvenOdd(A, n)
Input : n개의 양의 정수 값을 갖는 배열 A Output : 짝수 값들 합, 홀수 값들의 합 index <- 1
Evensum <- 0 Oddsum <- 0
while (index <= n) do if (A[index] is even)
Evensum <- Evensum + A[index]
else
Oddsum <- Oddsum + A[index]
index <- index + 1 end while
연습과제 #4
• 문제 : 핚 파일을 읽어서 페이지의 레포트를 생성
• 알고리즘 기술
Algorithm PageReport(pageNumber) Input : 텍스트 파일
Output : 페이지별 레포트, 총 라인수 lineCount <- 0
loop (not end of file) do read file
if (full page)
pageNumber <- pageNumber + 1 write page heading
end if
write report line
lineCount <- lineCount + 1 end loop
return lineCount
18 금오공과대학교 컴퓨터공학과
