이 포스팅은 kmooc의 인공지능을 위한 알고리즘과 자료구조 (성균관대학교 / 교수 허재필)를 듣고 정리했습니다.
자료구조
정의
자료 구조는
- 자료의 값
- 자료의 값간의 관계
- 자료에 가해질 수 있는 작업 (예를 들어 데이터 수정)
을 포함한다.
기초적인 자료구조
자료의 특징에 따라 적절한 자료 구조를 선택해야 한다.
알고리즘
정의
알고리즘은 입력값을 특정 출력값으로 변환하기 위한 컴퓨터가 수행할 수 있는 일련의 작업이다.
옳은 알고리즘은 다음의 2가지 조건을 만족한다.
- 모든 경우의 입력으로부터 옳은 결과값을 도출해야 한다.
- 알고리즘이 종료되어야 한다.
선형 자료구조
1. 배열 (Array)
배열은 번호(인덱스)와 번호에 대응하는 자료들로 이루어진 자료 구조를 나타낸다.
- 인덱스는 0부터 시작하며 배열의 인덱스 범위는
[0, size-1]로 표현할 수 있다. - 배열을 선언하면 물리적인 메모리상 연속적인 공간을 할당받는다.
- 자료의 논리적 순서와 메모리상의 물리적 순서가 일치한다.
score라는 이름의 길이가 3인 배열이 메모리에 할당됐다. 첫번째 요소인 score[0]가 메모리 공간의 첫번째 바이트에 할당됐다. 그 다음 요소가 순서대로 메모리 상에 할당되었음을 확인할 수 있다.
배열에 요소를 삽입하거나 삭제하기 위해서 많은 작업을 수반한다.
예를 들어, 그림 속 위 배열에서 3과 10 사이에 5를 삽입하기 위해서는 3 이후의 모든 자료를 한 칸씩 옮겨 5가 들어갈 빈 공간을 만들어야 한다.
리스트라는 자료 구조는 배열의 이런 문제점을 해결한다.
2. 리스트
(여기서 말하는 리스트는 linked list를 가리킨다.)
- 배열과 같이 선형적인 자료의 집합.
- 자료의 순서는 메모리 상의 물리적인 순서와 관계없다.
- 각 자료 요소는 다음 자료 요소를 가리킨다.
노드라고 부르는 자료 요소는 item(자료값)과 link(다음 자료값을 잇는 hook)으로 이루어진다.
리스트에 요소를 추가하기 위해서 배열과 같이 모든 요소를 옮길 필요없이 링크를 풀고 새로운 링크를 연결한다.
예를 들어, 리스트에서 20과 45사이에 5를 삽입하기 위해서 20과 45의 link를 풀고 20과 5의 링크, 5와 45의 링크를 연결한다. 배열보다 비교적 쉽게 자료 요소를 추가하거나 삭제할 수 있음을 알 수 있다.
head는 리스트의 첫번째 노드를 가리킨다. 각 노드는 다음 순서의 노드를 가리킨다. 만약 노드가 어떤 노드도 가리키고 있지 않다면 이 노드가 리스트의 마지막 노드가 된다.
위의 그림과 같이 리스트는 순차적으로 다음 노드를 가리키는 구조로 텅빈 리스트에 요소가 추가됨에 따라 어떻게 변하는 지 볼 수 있다.
3. 스택 (Stack)
선형자료구조의 하나로 LIFO순서에 의해 자료 요소가 추가되거나 삭제된다. LIFO는 last-in-first-out의 약자로 마지막으로 들어간 요소가 처음으로 나온다는 의미이다.
그림과 같이 데이터가 A부터 쌓여있다고 친다. 입력된 순서는 ABCD이지만 데이터를 하나씩 제거한다고 하면 DCBA의 순서로 즉, 입력된 순서와 반대로 나오게 되는 형태이다.
스택에서는 데이터를 추가하거나 삭제할 때 스택의 최상단(탑)에서만 작업이 이루어진다.
(스택의 용어)
- Top : 스택의 최상단
- Push : 스택의 top에 item을 삽입
- Pop : 스택의 top의 item을 제거
빈 스택에 5를 push하면 5가 top이 된다. 또다시 2를 push하면 2가 5위에 쌓이면서 top이 된다. pop을 하면 가장 위에 위치한 2가 제거된다.
스택을 이용해 괄호매칭을 검사할 수 있다.
- 여는 괄호를 스택에 추가한다.
- 보고 있는 괄호가 닫는 괄호면 스택의 top에 있는 여는 괄호와 매칭해준다.
- 최종적으로 스택이 비어있으면 모든 괄호가 매칭된 것이다.
4. 큐 (Queue)
선형자료구조의 하나로 FIFO순서에 의해 자료 요소가 추가되거나 삭제된다. FIFO는 first-in-first-out의 약자로 마지막으로 들어간 요소가 처음으로 나온다는 의미이다.
큐에서 데이터 삽입은 큐의 맨 뒤인 rear에서 발생하고 삭제는 큐의 맨 앞인 front에서 발생한다.
(큐의 용어)
- Front : 큐의 맨 앞으로 데이터의 삭제가 발생한다.
- Rear : 큐의 맨 뒤로 데이터의 삽입이 발생한다.
- Enqueue : rear에 item을 추가
- Dequeue : front의 item을 제거
빈 큐에 2를 넣고 또다시 7을 추가하면 rear에서 데이터의 삽입이 발생한다. 이 상태에서 큐의 데이터를 삭제하면 front에 있는 2가 삭제된다.
(Linear Queue VS Circular Queue)
위 사진의 마지막 부분에서 볼 수 있듯이 앞에 2개의 공간이 있음에도 불구하고 큐에 더이상의 데이터를 추가할 수 없는 상황이 발생한다. 이런 linear queue의 문제를 해결하기 위해 circular queue가 등장한다.
circular queue는 어느 시점이 되면 rear가 돌아 0인덱스로 돌아오는 형태로 공간을 최대한으로 활용할 수 있다.
스택과 큐를 이용해 회문체크를 할 수 있다.
(회문이란 rotator와 같이 문자열을 뒤집어도 동일한 문자열)
- 체크하고자 하는 문자열을 스택과 큐에 각각 넣는다.
- 각각 한번씩 스택에서 pop한 문자와, 큐에서 디큐를 실행했을 때의 문자를 비교한다.
- 매 회 문자가 일치하면 문자열이 회문임을 확인할 수 있다.