[data structure] 자료 구조와 알고리즘

데이터(Data)?

데이터들은 기본적인 것, 복수형이다.

데이터라는 것은 단위 여러 개의 원소들이 여러 개 있는 것이다.

정보는 데이터 중에서 나에게 필요하고, 포맷이 갖춰지고, 출처가 밝혀진 데이터이다.

 

 

 

구조(Structure, Organization)?

데이터를 쌓은 것을 '구조'라고 한다.

구조를 형성할 때는 무엇을, 어떻게 만들 것인지에 대한 사람의 생각이 들어가게 되어있다.

 

 

 

 

 

 

Organization of Data = Structural Construction

 결국 타겟팅하는 것을 만들고자 할 때 구조를 쌓게 된다.

 

 

 

 

 

우리가 배울 방법론을 가지고 데이터를 어떻게 구조화하고, 그 구조화된 것을 다양한 목표에 따라 어떻게 최종 타깃으로 만들 것인가에 대해 배운다. 여러 개의 구조를 많이 만들다 보면 우리가 원하는 타깃을 만들 수 있다.

 

 

 

자료 구조와 알고리즘

자료 구조(Data Structure)란?

 흩어져 있는 다양한 형태의 "데이터(자료)"들을 모으거나 연결하여 구조를 형성하는 체계적인 방법론

-> "Systematic Organization of Data"

일상생활에서의 예	해당하는 자료 구조
물건을 쌓아놓는 것	스택
영화관 매표소의 줄	큐
할 일 리스트	리스트
영어사전	사전, 탐색구조
지도	그래프
조직도	트리

 대부분의 프로그램에서 자료(data)를 처리하고 있고 이들 자료는 자료 구조(data structure)를 사용하여 표현되고 저장된다. 또한 주어진 문제를 처리하는 절차가 필요하다. 이것을 알고리즘(algorithm)이라고 불린다. 따라서 일반적인 프로그램은 논리적으로 따져보면 자료 구조와 알고리즘으로 구성되어 있다고 할 수 있다.

 

(1) 다양한 형태의 "자료(data)"들을 모으거나, 연결하여 구조를 만들고,

+

(2) 그 구조를 단계적으로 운영하는 방법(알고리즘)

=

목적 : 효율적인 프로그램 산출 기획

알고리즘(Algorithm)이란?

- 데이터 구조를 사용하는 순서 있는 행동

- 컴퓨터로 문제를 풀기 위한 단계적인 절차

- 어떤 문제를 해결하기 위한 명령어들의 유한 집합

 

정의 1.1 알고리즘의 조건

(1) 입력 : 0개 이상의 입력이 존재하여야 한다 (입력이 0 이어도 결과가 있을 수 있음)

(2) 출력 : 1개 이상의 출력이 존재하여야 한다 (프로그램이 돌아갔기 때문에 출력은 필요)

(3) 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다

(4) 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다

(5) 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다 (null statement면 안된다)

 따라서 알고리즘에는 (1)입력은 없어도 되지만 (2)출력은 반드시 하나 이상 있어야 하고 (3)모호하지 않고 명확한 방법으로 기술된 명령어들의 집합이다. 또한 (4)한정된 수의 단계 후에는 반드시 종료되어야 한다. 또한 (5)실행할 수 없는 명령어(예를 들면 0으로 나누는 연산)를 사용하면 안 된다.

 

알고리즘을 기술하는 방법

(1) 영어나 한국어 같은 자연어

- 자연어를 사용하기 때문에 모호성을 제거하기 위하여 명령어로 쓰이는 단어들을 명백하게 정의해야만 알고리즘이 될 수 있다

(2) 흐름도(flowchart)

- 좋은 방법이지만 알고리즘이 복잡해질수록 기술하기 힘들게 될 것이다

(3) 유사 코드(pseudo-code) : 자연어보다는 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘의 표현에 사용되는 언어

- 흔히 알고리즘을 기술하는데 선호되는 표기법이다.

최댓값을 구하는 유사 코드 예제

(4) 프로그래밍 언어

 

프로그램(Program)이란?

프로그램 = 자료 구조 + 알고리즘

 

# 프로그램은 단계적 기획이다

# 데이터 구조는 프로그램의 구조와 연산 방법(알고리즘)을 배우는 과목이다