[개요]
자료구조는 데이터를 조직화하고 저장하는 방법을 정의하는 것이다.
CS에서의 자료구조는 데이터요소의 관계, 연산, 접근 방법을 포합합니다.
컴퓨터 프로그래밍에서 유용하게 사용되며 데이터를 보다 효과적으로 조작하고 처리하는데 쓰입니다.
자료구조는 크게 두가지로 나눌 수 있습니다.
첫째는 선형자료구조입니다.
선형자료구조는 데이터 요소가 일렬로 배치되는 자료구조로
배열,스택,큐, 등이 있습니다.
둘째는 비선형 자료구조입니다.
데이터요소가 계층적으로 구성된다고 표현하며,
트리,그래프 등이 있습니다.
자료구조는 데이터 처리의 효율성과 안정성을 높이기 위해서사용됩니다.
이를 풀어서 설명하면,
검색을 수행할때, 선형 자료구조의 속도는 배열이 가장 빠르지만,
정렬된 데이터에서는 이진검색이 더 효율적입니다.
이런식으로 데이터에 따라 적절한 자료구조를 선택해서 데이터 처리 효율성을 높이는것입니다.
자료구조는 컴퓨터 프로그래밍에서 프로그램 성능과 메모리 사용량에 영향을 미치기 때문에
상황에 맞게 적절한 자료구조를 사용하면 메모리 사용량을 최소화하고
데이터 처리속도를 최적화 할 수 있습니다.
위에서 언급한거는 익숙하실거라 생각하고
생소한것들 위주로 가져왔습니다.
[연결리스트]
연결리스트는 선형자료구조 중 하나입니다.
데이터 요소들이 일렬로 연결되어있는 구조로,
각각의 데이터 요소들은 다음요소에 대한 포인터를 가지고 있다.
이를 이용하여 리스트 내에서 데이터를 탐색하고나 삽입,삭제를 할 수 있습니다.
1 -> 2 -> 3 -> 4 -> 5 -> NULL여기서 화살표는 각 요소가 다음 요소를 가리키는 포인터를 나타낸다.
마지막 요소는 더이상 다음요소가 없으므로 NULL을 가리키게 된다.
데이터삽입 : 삽입할 위치의 이전 요소가 가리키는 포인터를 새로운 요소에 연결하고
새로운 요소가 다음 요소를 가리키도록 포인터를 설정한다.
데이터 삭제: 삭제할 요소의 이전요소가 가리키는 포인터를 삭제할 요소의 다음요소에 연결하고
삭제할 요소를 해제합니다.
배열과 다리 데이터 요소들이 메모리상에 연속적으로 배치되지 않기 때문에
데이터를 삽입하거나 삭제할때 메모리를 복사할 필요가 없어서 삽입,삭제 연산이 빠릅니다.
하지만, 인덱스로 데이터에 접근할 수 없어서 데이터를 탐색하려면
처음부터 무조건 순회해야한다는 단점이 있습니다.
위 그림에서는 1,2,3,4,5이지만 이것들이 실제로는 리스트일수도 있습니다.
[우선순위 큐]
큐와 유사하지만, 이름 그대로 각각의 데이터가 우선순위를 갖고 있어서
우선순위가 높은 데이터를 먼저 삭제합니다.
우선순위 큐는 대표적으로 Heap 자료구조를 이용하여 구현합니다
아주 간단한 예시를 들어보겠습니다.
A B C D E라는 학생이 있을때, 시험성적을 우선순위 큐에 저장한다고 저장하면,
그림 1과 같이 저장이 됩니다.
성적이 가장 높은학생인 E를 삭제한 우선순위 큐
그 다음으로 성적이 높은 학생인 A 학생을 삭제하면 우선순위 큐는 다음과 같이 됩니다.
그러면 더 자세한 설명을 위해 우선순위 큐를 구성하는 힙에 대해서 설명 드리겠습니다.
[힙 자료구조]
힙은 우선순위 큐를 위해 고안된 완전이진트리 형태로 구성된 자료 구조이다.
[잠깐 ,완전 이진트리란??]
완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서
마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 합니다.
또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 합니다
[다시 힙 자료구조로]
힙 자료구조는 부모노드와 서브트리간 대소관계가 성립됩니다.
이진 탐색 트리와 달리 중복된값이 허락됩니다!
[힙의 종류]
최대힙
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진트리이다.
부모노드 >= 자식노드
최소 힙
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진트리이다.
부모노드 >= 자식노드
[우선순위 큐 구현방법 비교]
우선순위 큐를 힙이 아니라 배열 또는 연결리스트를 이용하여 구현 할 수도 있다.
힙은 일반적으로 배열을 이용하여 구현한다
자식 노드를 구하고 싶을 때
- 왼쪽 자식노드 index = (부모 노드 index) * 2
- 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1
부모 노드를 구하고 싶을 때
- 부모 노드 index = (자식노드 index) / 2
[삽입 연산]
힙에 삽입을 하기 위해서는 힙 트리의 성질을 만족시키면서 새로운 요소를 추가해야 한다.
삽입 방법
- 우선 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가한다.
- 추가된 새로운 노드를 부모의 노드와 비교하여 교환한다.
- 정상적인 힙트리가 될 때 까지 (더이상 부모노드와 교환할 필요가 없을 때까지) 2번을 반복한다.
최악의 경우 새로 추가된 노드가 루트노트까지 비교하며 올라가야 하므로 시간복잡도가 O(log₂n)이다.
[ 삭제 연산]
힙 트리에서 루트노드가 가장 우선순위가 높으므로 루트 노드를 삭제해야 한다.
삭제가 이뤄진 후 힙 트리의 성질이 유지돼야 하므로 아래와 같은 방법으로 삭제를 진행한다.
삭제 방법
- 루트 노드를 삭제한다.
- 루트 노드가 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.
- 루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환한다.
이때 최대 힙인 경우 자식노드 중 더 큰 값과 교환을 하며, 최소 힙인 경우 더 작은 값과 교환을 한다. - 정상적인 힙트리가 될 때까지 (더 이상 자식노드와 교환할 필요가 없을 때까지) 3번을 반복한다.