선형 자료구조에는 앞서 정리했던 배열, 연결 리스트, 스택 그리고 큐가 있다. 이번에는 큐(Queue)에 대해 정리해보자. 큐 큐는 스택과 비슷하지만 조금은 다르다. 스택은 위에서부터 수직으로 쌓는 느낌이였다면, 큐는 수평으로 넣는 느낌이다. 즉, LILO(Last in Last out), FIFO(First in First out)의 순서를 따라간다. 특징 데이터를 받는 순서대로 정렬해서 저장한다. 가장 앞부분을 Front / Head, 뒷부분을 Rear / Tail라고 한다. 한쪽 끝에서는 삽입, 다른 한쪽에서는 삭제만 수행한다. 시간복잡도 접근(Access) : 들어간 순서에 따라서 접근할 수 있기 때문에 O(n)의 시간 복잡도를 가진다. 삽입(insert) 및 삭제(delete) : 앞쪽에 삽입하..

자료구조의 스택에 대해 알아보자. 스택 스택은 쌓아놓은 더미를 뜻한다. 쌓여져 있는 데이터를 한 쪽에서만 넣고 뺄 수 있는 선형 구조로 되어 있다. LIFO(Last in First out), FILO(First in Last out)의 순서를 따라간다. 특징 데이터를 받는 순서대로 정렬해서 저장한다. LIFO는 맨 위, 즉 마지막으로 삽입된 데이터를 먼저 사용한다. FIFO는 맨 아래, 즉 먼저 삽입된 순서대로 데이터를 사용한다. 시간복잡도 접근(Access) : 쌓여져있는 순서대로 접근할 수 있기 때문에 O(n)의 시간 복잡도를 가진다. 삽입(insert) 및 삭제(delete) : 가장 위에 삽입하거나 삭제할 수 밖에 없기 때문에 O(1)의 시간 복잡도가 발생한다. 검색(search) : 접근과 마..

자료구조의 연결리스트는 배열과 비슷하면서도 다른 구조를 보여준다. 연결리스트에 대해 알아보자. 연결 리스트 연결 리스트는 배열의 삽입 및 삭제에 발생하는 비용이나 정적 크기 등의 단점을 보완하기 위해 만들어졌다. 정보는 하나의 노드에 저장되고, 그 노드에는 데이터와 다음 노드에 대한 정보를 담은 포인터가 저장된다. 종류에는 단일 연결 리스트(Singly linked linear list), 이중 연결 리스트(Doubly linked linear list), 원형 연결 리스트(Circularly linked linear list)가 있다. 각 연결 리스트의 구분 - 단일 연결 리스트(Singly linked linear list) 각 노드에 데이터와 한 개의 포인터 공간이 존재하고, 각 포인터는 다음 노드..

게임 개발에 있어서 자료구조와 알고리즘은 가장 기본적으로 알아야 할 지식이다. 이 중 자료구조의 가장 처음이자 기초적인 배열에 대해 알아보자. 배열 배열은 연속된 메모리 공간에 순차적으로 저장되는 데이터들을 말한다. 이는 각각의 값을 구성하는 요소(element)와 그 위치를 가리키는 인덱스(index)로 구성된다. 특징 동일한 데이터유형을 가진다. 연속된 메모리를 사용하여 저장하기 때문에 낭비되는 공간이 거의 없다. 데이터의 순서가 있고, 인덱스를 통해 각 요소에 바로 접근할 수 있다. 시간복잡도 읽기(read) : 각 요소에 대해 인덱스를 통해서 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가진다. 삽입(insert) 및 삭제(delete) : 길이가 한정적이기 때문에 삽입을 하려면 뒤에 한..