자료구조와 알고리즘
안녕하세요 지토우에요.
오늘은 자료구조에 대해서 처음으로 들어가는 시간이에요.
가장 기본적으로 자료구조와 알고리즘에 대해 배워봅시다.
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가 주로 쓰이는데,
유사코드는 자연어보다는 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘의 표현에 사용되는 코드를 말합니다.
흔히 알고리즘을 기술하는데에 선호되지요.
'IT > 자료구조' 카테고리의 다른 글
원형 연결리스트 코드 (0) | 2017.11.23 |
---|---|
[자료구조] malloc을 이용한 더블포인터와 주소 (0) | 2017.09.25 |
[자료구조] 배열 (0) | 2017.08.03 |
[자료구조] 추상 데이터 타입 (0) | 2017.08.01 |