자료구조란 ?
정의
- 자료(Data)의 정의된 규칙에 의해 나열된 집합을 의미한다.
- 대량의 자료(Data)를 효율적으로 관리하는 매커니즘이다.
Ex ) 우편번호를 활용한 주소, 출석 번호를 활용한 학생부 등 - 자료(Data)에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.
목적
- 자료를 더 효율적으로 저장하고 관리하기 위해 사용한다.
- 잘 선택된 자료구조는 더 빠르고 적은 메모리를 사용하여 작업을 처리한다.
자료구조의 종류
배열 (Array)
- 데이터를 빈틈없이 나열한 자료구조
- 데이터에 인덱스를 부여하여 인덱스로 데이터에 접근할 수 있도록 구성된 자료구조
- 1차원 배열 : 일직선으로 빈틈없이 데이터를 나열
- 2 차원 배열 : 사각형처럼 가로세로로 빈틈없이 데이터를 나열 ( Ex : 엑셀시트 )
- 3차원 배열 : 직육면체처럼 가로,세로,높이 빈틈없이 데이터를 나열
- 파이썬의 경우 리스트 타입이 배열 기능을 제공함
배열의 장점:
- 인덱스로 인한 빠른 접근 가능
배열의 단점:
- 미리 배열의 크기를 설정해줘야 하므로, 데이터를 추가하는 것이 어렵다
데이터를 삭제 할 경우, 뒤에 있는 데이터를 앞으로 당겨와야 하는 어려움이 있다
리스트 (List)
- 정해진 크기의 공간에 데이터를 나열해야만 하는 배열의 단점을 극복한 자료구조다.
- 리스트는 정해진 크기의 공간 없이, 필요할때마다 데이터를 추가하고 삭제가 가능한 자료구조다.
- 리스트는 떨어진 곳에 존재하는 데이터를 화살표(포인터)로 연결해서 관리하는 자료구조다.
리스트의 장점:
- 미리 데이터 공간을 미리 할당하지 않아도 됨. 배열은 미리 데이터 공간을 할당 해야 함.
리스트의 단점:
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
단방향 리스트
- 포인터가 한방향으로 가르키고 있어서 한 쪽 방향으로만 탐색이 가능한 자료구조다.
양방향 리스트
- 포인터가 양방향으로 가르키고 있어서 양 쪽 방향으로 탐색이 가능한 자료구조다.
스택 (Stack)
- 책상 위에 책을 쌓듯 데이터를 관리하는 자료구조
- 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
- First in Last out(FILO) 형식으로 데이터를 관리하는 방법
스택의 장점:
- 구조가 단순해서, 구현이 쉽다
- 데이터 저장/읽기 속도가 빠르다
스택의 단점:
- 데이터 최대 갯수를 미리 정해야 한다
- 저장 공간의 낭비가 발생할 수 있음
- 미리 최대 갯수만큼 저장 공간을 확보해야 함
큐 (Queue)
- 입장을 위해 줄 서있는 사람처럼 데이터를 관리하는 자료구조
- First in First out(FIFO) 형식으로 데이터를 관리하는 방법
- 큐에 데이터를 넣는 작업을 인큐(enqueue)라고 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.
- 데이터를 꺼내는 쪽으로 프런트(front)라고 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다.
큐의 장점:
- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 유리하다.
큐의 단점:
- 큐의 앞 부분이 비어도 데이터를 삽입할 수 없다.
- 데이터를 꺼낼 때 맨 앞의 데이터를 꺼내고 모든 데이터를 한 칸씩 앞으로 옮겨야 하기 때문에 작업이 느리다.
원형 큐 (링버퍼)
- 배열 요소를 앞쪽으로 옮기지 않는 큐를 구현한 자료구조다.
- 배열의 처음과 끝이 연결되어 있다고 보는 자료구조다.
- 논리적으로 어떤 요소가 첫번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트(front)와 리어(rear)이다.
- 이렇게 큐를 구현하면 프런트와 리어 값을 업데이트하면서 인큐와 디큐를 수행하기 때문에 앞의 큐에서 발생했던 요소 이동 문제를 해결할 수 있다.
디큐할 경우:
- 36(que[0])을 디큐한 후 front값을 que[1]로 없데이트해준다.
인큐할 경우:
- que[5]의 자리에 64를 저장한다.
- rear값을 que[0]으로 업데이트해준다.(저장공간이 6이기 때문에 index 5에서 0으로 업데이트된다. 만약 저장공간이 6보다 컸다면, 인덱스 값을 1만큼 증가시켜서 다음 인큐할 데이터는 que[6]에 저장될 것이다.)
트리 (Tree)
- 나무에서 나뭇가지가 갈라지듯이 퍼져나가는 자료구조
- 뿌리에서 잎으로 퍼져나가는 단방향의 구조이다.
이진트리
- 자식노드의 최대 갯수가 2개인 트리
- 자식의 값은 상관이 없다.
이진탐색트리 (완전이진트리)
- 왼쪽 자식 노드가 부모 노드보다 작은 값, 오른쪽 자식 노드가 부모 노드보다 큰 값을 가지고 있는 트리
힙
-
최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)
-
최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)
이진탐색트리와 힙(Heap)
공통점:
- 힙과 이진 탐색 트리는 모두 이진 트리임
차이점:
- 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
- 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
- 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
- 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
