[자료구조] 자료구조 개요

* 알고리즘?

 : 특정한 일을 수행하는 명령어들의 유한 집합

* 자료구조

 : 주어진 문제를 해결하기 위해 필요한 데이터의 조직화

* 프로그램 : 프로그래밍 언어를 사용한 알고리즘의 구현

[예제로 보는 개발 과정]

문제 : n개의 정수 값들이 주어질 경우 이 값들 중에서 최대값을 찾기

-> 자료구조 설계

-> 알고리즘 기술

-> 프로그램 구현

[알고리즘 문제]

유한한 입력 데이터-> 자료구조+알고리즘-> 입력 데이터에 대응되는 결과

[프로그램 개발 과정]

-소프트웨어 공학에서 배움

- 자료구조/알고리즘이 해당되는 부분

 :요구사항->분석->설계->정제 및 코딩->검증

[알고리즘의 조건]

- 입력 : 0개 이상 입력

- 출력 : 1개 이상 출력

- 명확성 : 각 명령은 모호하지 않아야 한다.

- 유한성 : 한정된 단계 후에 반드시 종료

- 유효성 : 각 명령어는 실행 가능한 연산

[알고리즘 기술 방법]

- 알고리즘 기술 : 자연언어 기술, FlowChart기술, Pseudo-Code

 : 자연언어 기술 - 특정 서식없이 문장으로 설명하듯 기술

 : FlowChart 기술 - 그림으로 그리는 과정, 시간이 많이 소요됨

 : Pseudo-Code : 특정한 프로그램 언어에 의존하지 않지만 유사하게 기술 

EX > 

* Pseudo-Code 표현

 - 프로그램언어보다 덜 구조적이지만 표현법보다 구조적

 - 수식 표현 : 

: 수식의 연산자는 일반적 수학 심볼 사용

: 배정문을 위해 심볼 <- 사용

: 동일 관계 비교를 위해 심볼 = 사용

 - 함수 선언

: Algorithm name(인수1, 인수2 ..)

 - 구조적 표현

: 결정 : 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

 -> 이러한 틀 내에서 유연하게 사용할 수 있도록 연습하기

[연습과제 #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,   (b 0이면 a호출, a 0이면 b호출)

   gcd(b, a mod b) otherwise

Algorithm GCD(a,b)

Input : 0보다 큰 양의 정수 a, b

Output : 양의 정수 a, b에 대한 최대공약수

if (b=0) return a

if (a=0) return b

return Gcd(b, a mod b)

cf . 최대공약수

[연습과제 #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

print EvenSum, OddSum

[연습과제 #4]

문제 : 한 파일을 읽어서 페이지의 레포트를 생성

- 1. 라인 카운트를 0으로 설정한다.

- 2. 파일이 끝나지 않았다면 loop를 돈다.

- 3. 파일을 읽고 full page이면 pageNum을 증가 및 새로운 페이지에 head를 맞춘다.

- 4. 한 라인을 쓴다.

- 5. 라인 수를 증가시킨다.

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

[참고]

http://www.kocw.net/home/search/kemView.do?kemId=434106