자료구조와 알고리즘

자료구조와 알고리즘

안녕하세요 지토우에요.

오늘은 자료구조에 대해서 처음으로 들어가는 시간이에요.

가장 기본적으로 자료구조와 알고리즘에 대해 배워봅시다.

1. 자료구조란

 자료구조는 영어로 data structure이라고 합니다.

말 그래도 자료 구조입니다.

들어가기에 앞서, 왜 자료구조에 대해 쉽게 설명해볼게요.

일상 생활에서 일어나는 일들을 예로 들자면 ,

우리는 살면서 할 일들을 시간별로 기록해두거나 책상에 책을 쌓아두기도 하고 버스를 타려고 줄을 서 있기도 하지요.

또 영어 사전은 알파벳순으로 정렬되어 있고, 지도는 도시들의 연결 상태를 알아보기 쉽게 표시되어 있으며

회사에는 계층적 조직을 나타내는 조직도가 존재하지요.

이런 것들이 넓은 의미에서는 일종의 정리라고 할 수 있고, 컴퓨터도 마찬가지로

프로그램에서도 자료들을 정리하는 여러 구조들이 있습니다.

이것들을 바로 자료 구조라고 부르는데요.

책상에 책을 쌓는 것은 '스택',

버스의 줄에 해당하는 자료 구조는 '큐',

할 일을 적어 두는 것은 '리스트',

영어 사전은 '사전, 탐색구조',

지도는 '그래프',

조직도는 '트리'

그렇다면 컴퓨터 프로그램은 무엇으로 이루어졌을까요?

대부분은 자료(data)를 처리하고 이 자료들은 자료 구조(data structure)를 사용해 표현되고 저장됩니다.

또, 주어진 문제를 처리하는 절차가 있어야 우리가 사용할 수 있을텐데요.

이것은 알고리즘(algorithm)이라고 불립니다.

따라서 일반적인 프로그램은 논리적으로 따졌을 때

자료 구조와 알고리즘으로 구성되어 있다고 할 수 있겠네요.

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

2. 알고리즘이란?

알고리즘이란 무엇일까요?

알고리즘의 사전적 정의는

어떤 문제를 해결하기 위해 명확히 정의된(well-defined) 유한 개의 규칙과 절차의 모임. 명확히 정의된 한정된 개수의 규제나 명령의 집합이며, 한정된 규칙을 적용함으로써 문제를 해결하는 것. 

입니다.

쉽게 말해 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합이라고 할 수 있는데요.

알고리즘은 다음과 같은 조건들을 만족해야 합니다.

입력	0개 이상의 입력이 존재해야 한다 ▶입력이 없어도 된다
출력	1개 이상의 출력이 존재해야 한다 ▶반드시 1개 이상
명백성	각 명령어의 의미는 모호하지 않고 명확해야 한다
유한성	한정된 수의 단계 후에는 반드시 종료되어야 한다
유효성	각 명령어들은 실행 가능한 연산이어야 한다

알고리즘은 어떻게 기술할 수 있을까요?

1. 우리가 일상에서 쓰는 자연어

2. 흐름도(flowchart)

3. 유사 코드(pseudo-cod)

4. C와 같은 프로그래밍 언어

1과 같은 자연어는 모호성을 제거하기 위해 명령어로 쓰여지는 단어들을 명백히 정의해야만 합니다.

2는 알고리즘이 복잡해질수록 기술하기 힘들겠죠.

따라서 보통은 3,4가 주로 쓰이는데,

유사코드는 자연어보다는 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘의 표현에 사용되는 코드를 말합니다.

흔히 알고리즘을 기술하는데에 선호되지요.