1. 왜 자료구조를 공부해야 하는가?
대량의 데이터를 입력하고 처리한 후, 그 결과를 출력하는 알고리즘에는 대량의 데이터 입출력 처리에 보다 효율적인 대량 데이터의 유지관리 방법이 필요합니다.
2. 자료구조
2-1. 대표적인 자료구조의 종류
- 배열 : 인덱스로 데이터를 빈틈없이 나열한 자료구조 (정적표현)
- 연속된 메모리공간으로 이루어져 있다.
- 리스트 : 포인터로 데이터를 순서대로 나열한 자료구조 (동적표현)
- 불연속적으로 메모리 공간을 차지한다.
- 스택 : 책상 위에 책을 쌓듯 데이터를 관리하는 자료구조
- 데이터를 쌓는 작업을 PUSH, 데이터를 꺼내는 작업을 POP
- LIFO(Last In, First Out), FILO(First In, Last Out)
- 큐 : 데이터를 넣은 순서대로 데이터를 꺼내는 데이터 관리방법
- FIFO(First In, First Out), LILO(Last In, Last Out)
- 트리 : 나무가지가 2개, 3개로 갈라지고 또 나뉘듯 퍼져나가는 자료구조
2-1. 배열 vs 리스트
상세 내용
- 1차원 배열 : 데이터들을 차례대로 빈틈없이 나열한다.
- 리스트: 데이터들은 모두 떨어져 있지만, 끈으로 묶여있다.
배열은 데이터의 순서가 인덱스로 고정되어 있는 방식으로 데이터의 순서를 파악할 수 있다. 그런데 만약 배열의 각 요소들이 이곳저곳으로 이동해 버린다면, 배열에 저장되어있는 데이터의 순서를 파악할 수 없게 된다.
반면 리스트는 데이터의 위치에 구애받지 않는다. 데이터들이 자유롭게 이동해도 괜찮다. 끈(포인터)를 추적하면 다음 데이터가 어디에 있는가 파악할 수 있기 때문이다.
또한 유효한 데이터의 개수를 관리하는 방법에도 배열과 리스트는 차이가 있다. 배열에서는 유효한 데이터 개수를 관리할 때 다른 변수를 사용하지만, 리스트에서는 '다음 데이터에 연결된 포인터의 유무'로 데이터의 끝을 파악한다.
그렇다면 장점과 단점을 정리해보자.
배열의 장점
- 인덱스를 통한 검색이 용이
- 연속적인 메모리 관리가 편하다.
배열의 단점
- 데이터의 삽입, 삭제가 리스트보다 느리다. (N번의 이동 작업)
- 한 데이터를 삭제하더라도, 배열은 연속해야하므로 공간이 남는다. (메모리 낭비)
- 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
- 컴파일 이후 배열의 크기를 변동할 수 없다.
리스트의 장점
- 포인터가 다음 데이터의 위치를 가르키고 있어, 삽입 삭제가 용이하다.
- 동적이므로 크기가 정해져있지 않다.
- 메모리의 재사용 편리
- 불연속적이므로 메모리 관리의 편리
리스트의 단점
- 검색 성능이 좋지 않다.
- 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간 발생
정리하면, 배열은 데이터의 크기가 정해져있고 추가적인 삽입, 삭제가 일어나지 않으며 검색을 필요로 할 때 유리하다. 리스트는 데이터의 크기가 정해져있지 않고, 삽입 삭제가 많이 일어나며 검색이 적은 경우 유리하다.
검색 성능이 차이가 나는 이유는, 배열은 메모리가 연속적으로 잡히게 되는데 리스트는 주소가 연속적이지 않기 때문에 예측을 할 수 없기 때문이다.
2-2. 단방향 리스트, 양방향 리스트
상세 내용단방향 리스트: 한쪽 방향에서 데이터를 찾아간다.
- Head 포인터, Next 포인터
- 마지막 요소에는 '다음 요소가 없음' 가 저장됨
- 리스트에 정보가 하나도 없을 때는 Head 포인터에 '종료 정보'가 저장됨.
양방향 리스트: 양쪽 방향에서 데이터를 찾아간다.
- Head 포인터, Next 포인터, Prev 포인터, Tail 포인터(마지막 요소의 위치를 가리킨다)
- 리스트에 정보가 하나도 없을 때는 Head, Tail 포인터에 '종료 정보'가 저장됨.
2-3. 링 버퍼
배열의 마지막 요소와 1번째 요소를 연결시킨 자료구조.
마지막 요소의 다음 요소는 배열의 1번째 요소가 된다.
링 버퍼는 가장 오래된 데이터를 버리는 FIFO의 큐 구조를 구현할 때 유용하다.
예를 들면 최근 발생한 수십건의 정보를 유지해야 하는 휴대전화의 통화 이력 구현에 활용 가능하다.
2-4. 이진 트리
단방향 리스트의 일종이라고 볼 수 있다.
데이터 X의 다음 요소로 L과 R, 2개의 데이터가 존재하는 자료구조.
- 이진트리의 기본 단위는 부모 노드 1개, 자식노드 2개 (자식노드가 한쪽만 있을 수도 있다.)
- 부모 없는 노드를 '뿌리', 자식 없는 노드를 '잎'이라고 부른다.
- '뿌리'에서 특정 노드에 도달하기까지의 경로의 길이를 '깊이'라고 부른다.
부모의 노드값이 자식의 노드 값보다 항상 적은 이진트리는 힙
- 최소 값(or 최대 값)은 항상 배열의 1번째 요소에 저장되므로 쉽게 최소 값(or 최대 값)을 검색할 수 있다.
2-5. 해시테이블
- N개의 요소를 가진 루트배열이라는 이름의 배열
- 루트 배열의 각 요소들이 가리키는 리스트
위 2개의 자료구조가 조합된 것.
- 해시 함수에 데이터를 입력해서 구한 값이 루트 배열의 요소 번호가 된다.
- Key, Value로 데이터를 저장하는 자료구조
2-6. 그래프
정점(Node)과 간선(Edge)으로 항목들의 관계를 그림으로 표현한 것이 그래프
3. 참고자료
- 그림으로 배우는 알고리즘 (3장)
- 배열(Array)과 리스트(List) (https://wayhome25.github.io/cs/2017/04/17/cs-18-1/)4. 내 생각
기초적인 자료구조의 개념을 정리해 보았다.
더 깊게 공부하고, 이 글을 수정하거나 새로 업로드 할 수 있도록 공부해 나갈 것이다. (2021.09.14) 