1 - (1,2) 자료구조와 알고리즘

1 - 1. 자료구조

자료구조란?

 물건을 찾을 때 찾기 쉽게 정리를 해야 찾기 쉽고, 스마트폰에서 사진들을 분류하고 컴퓨터에서 폴더별로 파일들을 잘 분류해야 찾기 쉬운 것처럼, 자료를 효율적으로 활용하기 위해서는 정리를 해야 한다. 또 그 정리에도 여러 방법이 있는데, 영어사전은 알파벳 순서대로, 사진은 날짜별로 분류하는 것이 효율적인 것처럼, 자료마다 효율적인 정리 규칙이 있다.

 자료구조(Data structure) = 사람들이 사물을 편리하고 효율적으로 사용하기 위해 정리하는 것과 마찬가지로 컴퓨터에서 자료들을 정리하고 조직화 하는 여러 가지 구조

 자료구조의 분류

 자료구조의 여러 가지 형태 - (1)정수와 실수, 문자와 같이 프로그래밍 언어에서 기본적으로 제공하는 단순 자료구조, (2)여러 가지 자료들이 복합적으로 구성된 복합 자료구조

 복합 자료구조 - (1)선형 구조 (2)비선형 구조

※앞으로의 포스팅에서는 다양한 복합 자료구조에 대해서 공부 할 예정입니다.

선형 자료구조(Linear Data Structure)

(기본적으로) 자료들이 순서적으로 나열된 자료구조이다. 데이터를 찾기 위해 자료에 접근하는 방법으로는

 1. 순서 접근(Sequential access)

 2. 직접 접근(Direct access)

으로 나눌 수 있다.

 이 중 배열에 대한 직접 접근 방식으로는 인덱스i를 이용하여 배열의 i번째 요소인 A[i]를 한 번만에 접근하는 방법이 있다. 또한 연결 리스트는 대표적인 순서 접근 방법으로, 시작 노드에서부터 하나씩 다음 노드로 이동하면서 원하는 자료를 찾아가는 방법이다.

비선형 자료구조(Non-Linear Data Structure)

 자료들 간에 선형적인 순서가 있는 것이 아니라 보다 복잡한 연결을 갖는 형태. ex)트리, 그래프 등

트리

 회사의 조직도나 컴퓨터의 디렉토리와 같은 계층 구조를 효현하기에 적합한 구조.

그래프

 지하철 노선도나 SNS의 인맥 지도, 인터넷 망 등을 표현할 수 있는 가장 복잡한 형태의 자료구조.

 정점을 연결하는 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 나눌 수 있으며, 간선이 가중치 가질 수 있으면 가중치 그래프라 부른다.

자료구조의 활용

 정렬 - 주어진 자료들을 어떤 기준을 바탕으로 순서대로 나열. 다소 알고리즘적인 측면이 강하지만 효율적인 정렬을 위해 다양한 자료구조의 활용이 필요.

 탐색 - 컴퓨터의 활용에서 가장 핵심이 되는 작업. 많은 경우 컴퓨터를 활용하면 자료를 찾는 일을 효율적으로 처리할 수 있겠지만, 적절한 자료구조와 그에 따른 알고리즘을 사용하는 경우 가장 효율적인 탐색이 가능할 것이다.

1 - 2. 알고리즘

알고리즘이란?

알고리즘(Algorithm) = 어떤 문제를 해결하는 절차. 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 정밀하게 기술한 것.

 ※어떠한 문제를 해결하는 절차는 보통 프로그래밍 스타일이나 프로그래밍 언어와는 무관하다. 즉, 알고리즘은 C언어를 사용하건, C++이나 Java를 사용하건, 사용되는 프로그래밍 언어에 상관없이 문제를 해결하는 절차를 말한다.

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

 대부분의 컴퓨터 프로그램은 데이터를 처리하고 있고 이들 자료는 자료구조를 사용하여 표현되고 저장된다. 또한 주어딘 문제를 처리하는 절차, 즉 알고리즘이 필요하다. 따라서 프로그램은 자료구조와 알고리즘으로 구성되어 있다고 볼 수 있다.

 위에서 말했듯이, 어떠한 자료를 정리할 때에는 자료에 따른 적절한 자료구조가 있다. 또 어떠한 자료구조에는 그에 따른 적절한 알고리즘이 따라오기 마련이다. 예를 들어, 성적 처리 프로그램을 작성한다고 생각해보자. 이 프로그램은 여러 학생들의 성적을 읽어 들여서 그 중 최고 성적을 찾고자 한다. 이때 가장 쉽게 사용할 수 있느 것이 배열(자료구조)이다. 자료를 정리할 적절한 자료구조를 찾았다. 이제 그 자료들 중 최고 성적을 찾는 알고리즘을 생각해야 한다. 이런 상황에 보통 사용하는 알고리즘은 다음과 같다.

 각 학생들의 성적을 모두 배열마다 저장을 한다. 먼저 따로 변수를 하나 만들 다음, 그 변수를 배열의 첫 번째 항목에 저장된 점수로 초기화한다. 그 후 배열의 두 번째, 세 번째, ..., n번째 항목에 저장된 점수와 따로 만든 변수에 저장된 값을 비교를 하며, 비교대상이 된 성적(x번째 항목)이 변수보다 더 크다면 변수의 값을 x번째 항목의 성적으로 바꾼다.

 이와 같이 문제를 해결하는 절차를 알고리즘이라고 하며, 어떠한 자료구조와 구하고자 하는 값이나 목적이 주어진다면 그에 걸맞는 알고리즘이 있다는 것을 알 수 있고, 그에 따라 컴퓨터가 복잡한 자료들을 빠르게 저장, 검색, 분석, 전송, 갱신하기 위해서는 자료구조가 효율적으로 조직화되어 있어야 한다는 것을 알 수 있다. 또한 응용프로그램을 작성할 때에는 가장 적합한 자료구조와 알고리즘을 선택해야 한다는 것 또한 알 수 있다.

 알고리즘은 특정한 일을 수행하는 명령어들의 집합이다. 여기서 명령어란 컴퓨터에서 수행되는 문장들을 의미한다. 그렇다고 모든 명령어들의 집합이 알고리즘이 되는 것은 아니다. 알고리즘은 다음과 같은 조건들을 만족해야 한다.

알고리즘의 조건

 ·입력 = 0개 이상의 입력이 존재하여야 한다.

 ·출력 = 1개 이상의 출력이 존재하여야 한다.

 ·명백성 = 각 명령어의 의미는 모호하지 않고 명확해야 한다.

 ·유한성 = 한정된 수의 단계 후에는 반드시 종료되어야 한다.

 ·유효성 = 각 명령어들은 실행 가능한 연산이어야 한다.

 알고리즘에는 입력은 없어도 되지만 출력은 반드시 하나 이상 있어야 한다. 모호한 방법으로 기술된 명령어들의 집합도 알고리즘이 될 수 없다. 또 컴퓨터가 실행할 수 없는 명령어를 사용하면 역시 알고리즘이 아니다. 무한히 반복되는 명령어들의 집합도 알고리즘이 아니다.

알고리즘 기술 방법

 알고리즘을 기술하는 방법은 다음과 같이 4가지가 있다.

1. 영어나 한국어와 같은 자연어

2. 흐름도(flowchart)

3. 유사 코드(pseudo-code)

4. 특정 프로그래밍 언어(C, C++, java 등)

 앞에서 살펴본 n개의 정수를 저장하고 있는 배열 A에서 최댓값을 찾는 문제를 이용하여 각 알고리즘의 기술 방법을 살펴보자.

영어나 한국어와 같은 자연어

 이 방법은 자연어를 서술하므로 기술이 편리하지만 모호성을 제거하기 위하여 명령어로 쓰이는 단어들을 명백하게 해야만 알고리즘이 될 수 있다.

ArrayMax(A,n)

1. 배열 A의 첫 번째 요소를 변수 tmp에 복사한다.

2. 배열 A의 다음 요소들을 차례대로 tmp와 비교하여, 더 크면 그 값을 tmp로 복사한다.

3. 배열 A의 모든 요소를 비교했으면 tmp를 반환한다.

흐름도(flowchart)

 흐름도는 명확하게 표현할 수 있다는 장점이 있어 특허 명세서 등에서 많이 사용된다. 그러나 알고리즘이 조금만 복잡해져도 흐름도가 매우 목잡하게 표시되는 단점이 있다.

유사 코드(pseudo-code)

 유사코드는 자연어보다는 더 체계적이지만 프로그래밍 언어보다는 덜 엄격한언어로서 알고리즘의 표현에 흔히 사용되는 방법이다. 유사 코드의 문법은 보통 C, C++, Java 등 실제 프로그래밍 언어와 비슷하여 쉽게 이해가 가능하면서도 특정 프로그래밍 언어로 구현할 때의 여러 가지 문제들을 감출 수 있고, 알고리즘의 핵심적인 내용에 대한 표현에만 집중할 수 있어 알고리즘의 기술에 많이 사용되고 있다. 유사코드는 알고리즘을 기술하는데 가장 선호되는 표기법이며, 앞으로의 포스팅에서도 유사 코드를 많이 사용할 것이다.

 또한, 앞으로 유사 코드를 볼 때 주의할 점으로는 대입 연산자가 =가 아닌 ←임을 유의해야 한다는 것이다. =는 대입이 아니라 비교 연산자로 사용된다.

ArrayMax(A,n)

tmp ← A[0];

for i←1 to n-1 do

if tmp < A[i] then

tmp←A[i];

return tmp;

특정한 프로그래밍 언어

이 방법은 특정한 프로그래밍 언어를 사용하여 알고리즘을 기술하는 방법이다. 이것은 알고리즘의 가장 정확한 표현이지만, 구현을 위한 많은 구체적인 사항들을 포함하고 있어 알고리즘의 핵심적인 내용 이해를 방해할 수 있다. 아래 프로그램은 C++로 기술한 알고리즘이다.

int ArrayMax(int score[], int n)    //자료구조 = 배열 array, n은 배열 길이

{

int tmp = score[0];

for(int i=1; i<n; i++)        //알고리즘

{

if(score[i] > tmp)

tmp = score[i];

}

return tmp;

}

※이 게시물은 생능출판사의 "C++로 쉽게 풀어쓴 자료구조"책을 바탕으로 작성되었습니다. 이 게시글에 자료로 들어간 사진이나 글의 대부분은 생능출판사의 소유이며, 문제가 될 시 삭제하겠습니다.※

태클은 언제나 환영입니다. 잘못된 내용이 있다면 알려주세요!