[자료구조] 1강 1장 기본 개념 - 1절 자료구조와 알고리즘

Data : 어떠한 사실이나 값

수치값 : 진수로 표현

 

* 스트링 : 연속적인 저장 공간에 저장된 문자열을 의미하며 문자 사이의 공백을 포함하여 문자열의 길이를 표현

 

* 정보 : Data값을 처리하여 발생되는 결과

 

* 자료구조란?

- 자료 사이에 존재하는 관계를 개념적으로 정의

- 자료를 효율적으로 이용할 수 있도록 자료의 특성에 따라 분류하여 구성하고 저장 및 처리하는 모든 작업

 

* 자료 구조를 기억 공간 내에서 실현하는 방법

- 기억 공간 내에 앞에서부터 차례로 데이터를 기억시키는 방법 (배열)

- 자료 사이의 관계가 기억 공간 내의 위치와 독립하여 포인터에 의한 접속으로 얻게 되는 방법 (리스트)

 

* 배열과 리스트의 차이점

- 배열 : 메모리 공간 내에 연속적인 공간이 있어야한다

- 리스트 : 메모리 공간 내에 연속적인 공간이 없어도 메모리 공간 어디에도 저장가능

 

* 자료 구조의 형태에 따른 분류

- 단순 구조 : 정수, 실수, 문자, 문자열 등의 기본 자료형

- 선형 구조 : 순서 리스트, 연결 리스트, 스택, 큐, 덱

- 비선형 구조 : 트리, 그래프

- 파일 구조 : 순차파일, 색인파일, 직접파일 (속도면에서 순차파일<색인파일)

 

* 자료구조를 선택하기 위한 요인

- 데이터의 양

- 데이터를 사용하는 방법과 횟수

- 데이터의 정적 혹은 동적인 특성

- 데이터 구조에 의해 요구되는 기억 장치의 양

 

* 알고리즘

- 특정한 일을 수행하는 명령어들의 유한집합 (문제를 해결하기 위한 수행과정)

 

* 알고리즘의 요구조건

- 입력 : 외부로부터의 자료 입력이 0개 이상있어야한다.

- 출력 : 최소 한 가지 이상의 출력이 있어야한다.

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

- 유한성 : 언젠가는 반드시 종료해야한다.

- 유효성 : 알고리즘을 구성하는 명령문들은 하드웨어에서 실행 가능해야한다.

 

* 알고리즘을 기술하는 방법

- 자연어를 사용하는 방법(잘 안쓰임)

- 흐름도를 사용하는 방법(가시적으로는 좋으나 복잡해지면 표현하기가 어렵다)

- 의사 코드(pseudo-code)를 사용하는 방법(가장 일반적인 방법)

 

* 흐름도를 사용하는 방법

(복잡해지면 흐름도 사용X) -> 의사코드 사용

 

* 자료 추상화

- 데이터 타입 : 데이터의 집합과 연산의 집합

- 추상화 : 필수적이고 중요한 속성만을 골라서 일반화시키는 과정

- 추상 데이터 타입 (Abstract Data Type : ADT) :

데이터 타입의 일반화로 정의

데이터가 무엇이고 무슨 기능을 수행하는가만을 정의

데이터 구조 및 연산의 구현 방법은 불포함 (이유 : 프로그램언어마다 구현방법이 다름)

객체와 연산을 정의

 

* SPARKS (Structured Programming : AReasonably Komplete Set)

- 알고리즘을 기술하는 언어

- 선언문, 지정문, 조건문, 입출력문등

 

* 선언문

- 여러 가지 형태의 변수를 선언하여 자료형(Data Type)을 사용

 

* 지정문

- 상수나 변수 또는 연산식의 결과를 변수에 지정하는 문장

P←X; q←0 : 여러문장은 세미콜론(;)으로 구분하여 한줄에 표현가능

LINK(p)←Y

q←q+1 : 산술식, 논리연산자, 관계연산자, 부울식, 문자식 표현가능

 

* 조건문

- 조건 결과에 따라 참이나 거짓으ㄹ 조건의 수행여부를 결정

- if, while~do, repeat~until 문

- 조건에 따라 실행되는 명령문이 여러 개인경우에는 대괄호[]로 묶어 표현

 

* if문

- 참이나 거짓을 판별할수 있는 조건식을 표현하고 조건이 참인 경우에는 실행하는 문장과 거짓인 경우에 실행하는 문장을 기술

 

형식 1

if (조건식) then 명령문1 : if 조건식이 참이라면 명령문 1을 수행 거짓이라면 명령문2 수행

else 명령문2

 

형식 2

if (조건식) then 명령문1 : if 조건식이 참이라면 명령문 1을 수행 거짓이라면 수행X

 

* while~do 문

- 조건식이 참인 동안에는 해당 명령문을 반복 수행하는 구문

while (조건식) do

명령문

end

 

* repeat~until 문

- 조건문에서 명령문을 먼저 실행한 다음 조건식을 판별하고 조건식이 참이 될 때까지 해당 명령문을 반복 수행

repeat

명령문

until 조건식

 

* CASE 문

- 여러 조건식 중에서 해당 조건을 찾아서 그에 해당되는 명령문을 수행하는 구문

- 여러 개의 if문이 쓰이는 블록을 대체

- 반복적인 내포 관계에서는 if문보다는 case문으로 표현하면 가독성이 높아짐

case

:조건식1:명령문1

:조건식2:명령문2

:

:

:조건식n:명령문n

:else:명령문n+1

end

 

* 반복문 for 문

- 조건식이 초기 값부터 시작하여 증분 값에 따라 최종 값에 해당될 때까지 해당 문장을 반복 수행하는 문장

 

for 변수 ← 초기값 to 최종값 by 증분값 do

명령문

end

 

* Procedure 문

- 일련의 반복적인 명령을 수행하는 블록을 별도의 블록으로 표현한 것

- 알고리즘은 하나 이상의 procedure로 구성

- 프로시저간 연락은 매개변수를 사용

- 실행한 후 다시 제어권만을 회수(서브루틴)

- 실행한 후 결과값을 변환(함수)

 

procedure NAME(parameter list)

명령문

end

 

* 프로시저간의 자료 전달 방법 (value, reference 가 많이 쓰인다)

- call by value : 실 매개변수 값을 계산하여 서브 프로시저의 형식 매개변수에게 전달하는 방법

- call by reference : 실 매개변수 값이 저장된 기억장소를 가리키는 포인터나 실제주소를 형식 매개변수에 전달하는 방법

- call by name : 서브 프로시저에서 매개 변수가 사용되기 전까지 실매개변수를 계산하지 않고 전달하여 실 매개 변수의 값을 계산하는 시기를 서브 프로시저에서 결정하는 방법

 

* 입출력문

- Read문 : data값을 입력받을 때 사용

- Print문 : 변수의 내용이나 계산 결과를 출력할 때 사용

read(argument list)

print(argument list)

 

* 주석

- 두 개의 슬래쉬(//)를 사용하여 알고리즘의 어떠한 위치에서도 사용이 가능

- /* 와 */ 는 주석의 시작과 끝을 표시

- 여러 문장에 대해 기술 가능

 

* stop문

- 현재 진행 중인 알고리즘을 중단하는 구문

 

* SPARKS언어의 사용 규칙

- 모든 프로시저의 입출력 변수를 명확히 명세

- 변수의 의미를 알 수 있게 정의

- 알고리즘의 제어 흐름은 되도록 순차적으로 표현

- 가독성을 위해 각 문장들은 들여쓰기(indentation)을 사용

- 주석은 짧으면서 의미는 명확히 기술

- 함수를 적절히 사용