-
자료구조와 알고리즘 중에서 자주 사용되는 것들
자료구조
Array(배열)
배열이란 연속된 메모리 공간에 순차적으로 저장하는 자료구조이다.
또한 크기가 정해진(정적) 데이터의 공간이므로 크기를 변화시키려면 메모리를 재할당 해주어야한다.
배열을 구성하는 각각의 값을 요소(element) 라고 부르고, 위치를 가리키는 인덱스(index) 라고 지칭한다.
배열의 장점으로는 인덱스를 이용해 요소에 빠르게 접근할 수 있고, 메모리가 연속적으로 할당되므로 캐시 메모리 활용이 용이하며, 요소의 크기가 동일하기 때문에 메모리 사용이 효율적이다.
배열의 단점으로는 크기가 정적으로 정해지기 때문에 크기를 변화시키려면 메모리를 다시 할당해주어야 하고, 삽입과 삭제가 발생하는 상황에서 적절한 배열의 크기를 미리 결정하기 어렵다.
Linked List(연결 리스트)
연결 리스트란 각 노드가 데이터와 포인터를 가지고 기차와 같이 한줄로 연결되어 있는 자료구조이다.
배열과 다르게 데이터 요소들이 불연속한 메모리 공간에 할당되어 있다.
연결 리스트는 데이터를 구성하는 각각의 값을 노드(Node) 라고 부르고 각각의 노드는 포인터(Pointer) 를 가지고 있어 다음 노드의 위치를 가리키고 있다.
연결 리스트의 장점으로는 동적으로 크기를 조정할 수 있고, 자료의 삽입 삭제가 쉬운 이점이 있으며, 메모리를 동적으로 사용하여 메모리낭비가 적다.
연결 리스트의 단점으로는 인덱스를 이용해 요소에 직접 접근할 수 없어 시간이 오래 걸리고, 포인터를 유지하기 위해 추가적인 메모리가 필요하다.
Stack(스택)
스택이란 종이컵을 쌓고 사용할때와 같이 가장 마지막에 들어온 데이터가 가장 먼저 빠져나가는 LIFO 자료구조이다.
또한 스택은 함수 호출과 관련된 데이터를 저장하는 메모리 영역으로써 매개변수, 지역변수, 반환값 등의 정보가 저장되는 공간이다.
하지만 스택 영역은 크기가 정해져 있어 무한히 할당 할 수 없고, 재귀함수가 너무 깊게 호출되는것과 같이 스택 영역을 초과했을 경우 Stack Overflow 가 발생한다.
Queue(큐)
큐란 놀이기구 탑승시 줄을 서고 나가는 길이 있는 것과 같이 가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO 자료구조이다.
큐의 종류에는 원형 큐, 우선순위 큐 등이 있다.
원형 큐 란 큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게 된다는 점을 활용해 배열의 마지막 부분을 사용했을 경우 다시 배열의 처음부터 데이터를 채우는 구조이다. 원형 큐 또한 FIFO 구조이다.
우선순위 큐 란 데이터를 넣을 때와 달리 뺄 때에는 우선순위가 높은 데이터 부터 빠지는 구조이다. 우선순위 큐는 보통 힙힙(Heap) 자료구조를 이용해 구현한다.
알고리즘
버블 정렬
버블정렬이란 첫번째와 두번째 자료를, 두번째와 세번째자료를, ... 처럼 비교하는것이다.
예를 들어 a = [3, 6, 2, 7, 1, 8] 이란 배열이 있을 때 3과6을, 6과2를, 2와7 이런식인 것이다.
이것을 간단한 이미지로 예를 들면 다음과 같다.
이처럼 버블정렬은 n-1 번째와 n번째 자료를 비교해 가면서 작은숫자를 앞으로 바꿔가는 것이다.
버블정렬은 구현이 간단하다는 장점이 있지만 데이터가 많을경우 성능이 저하된다는 단점이 있다.
선택 정렬
선택정렬은 말 그대로 선택을 해서 정렬하는 것이다. 예를 들면
a = [3, 6, 2, 7, 1, 8] 이란 배열이 있을 때 3부터 8까지 쭉 둘러보면서 가장 작은 값을 찾고 그것을 첫번째와 교환 하는 방식이다.
선택정렬의 이미지는 다음과 같다.
이처럼 5와 1의 위치를 바꾸고 3과 2의 위치를 바꾸는 것처럼 작은 순서대로 앞쪽에 배치하는 것이다.
힙 정렬
힙 정렬이란 힙 자료구조를 이용한 정렬 알고리즘으로써 완전이진 트리를 기반으로 하는 특별한 자료구조이다.
따라서 부모 노드와 자식노드의 관계가 일정해 최대 혹은 최소값 정렬을 위해 사용되는 알고리즘이다.
트리 정렬
트리 정렬이란 이진 탐색 트리를 이용하여 정렬하는 알고리즘으로써 힙 정렬과 비슷해 보이지만 정렬될 자료의 각 원소 크기에 따라 부모 노드의 왼쪽 혹은 오른쪽 자식이 되느냐의 차이점이 있다.