이 포스트는 FastCampus에 이 강의를 보고 포스팅되었습니다.
문제가 될 시 삭제될 예정입니다.
자료구조 종류는 뭐가 있는데?
전에 말했듯이 효율적인 자료구조를 찾아야 효율적인 알고리즘을 짤 수 있습니다.
자료구조는 크게 2가지 종류를 가지고 있습니다.
- 선형 자료구조
- 비선형 자료구조
이번 시간에는 선형 자료구조에 대해 알아보죠.
선형 자료구조 ( 한 줄로 관리하기 )
선형 자료구조는 앞뒤에 요소가 1:1에 관계하고 있습니다.
앞에 있는 요소와 뒤에 있는 요소가 1:1에 관계를 맺고 선처럼 이어져 있죠.
배열
배열은 사용할 메모리를 먼저 할당받고, 거기에 자료를 넣는 식입니다.
한 곳에 4 Byte 씩 할당됩니다.
배열에 특징은 중간이 비면 안 됩니다.
- 배열은 물리적 순서와 논리적 순서가 똑같기 때문이죠
- 그래서 중간에 빈다면 당겨오거나, 밀어야 합니다.
배열은 특정 위치에 있는 값을 꺼내는 연산이 빠릅니다.
- a[2]번째 요소를 꺼내고 싶다!
- 처음 주소가 10일 때 10 + 4(바이트 수) * 2(인덱스)
- = 18번째 주소가 a[2]라는 소리입니다.
연결 리스트
배열과는 다르게 그때그때 메모리를 추가로 할당받는 자료구조입니다.
연결 리스트는 자료와 함께 다음 요소를 가리킬 링크를 하고 있습니다링크를 가지고 있습니다.
- C, C++에서는 포인터로, 자바에서는 객체 참조 변수를 가지도록 구현하면 됩니다.
물리적 순서와 논리적 순서가 다를 수 있습니다.
연결리스트의 종류로는 단순, 더블, 서클이 있습니다.
- 앞에서 소개한 것이 단순 리스트입니다.
- 더블 연결리스트는 내 전 요소와 다음 요소를 동시에 가리키는 링크를 가지는 타입입니다.
- 서클 연결리스트는 마지막 요소가 처음 요소를 가리키는 링크를 가지는 타입입니다
데이터가 추가, 삭제하는데 들어가는 속도가 배열보다 더 빠르죠.
단, 특정한 곳을 찾아가는 것은 느립니다.
- 맨 처음부터 논리적으로 찾아야 하기 때문이죠.
- 그래서 이 연산에 시간 복잡도는 O(n)입니다.
연결리스트 VS 배열
학교를 생각해봅시다!
배열 같은 경우 미리 책상 30개를 두고, 학생들이 들어오면 미리 가져온 책상을 사용한다고 생각하면 됩니다.
- 한 줄로 쭉, 1번 다음엔 2번 다음엔 3번 ... 이런 식으로
연결리스트 같은 경우 전학생이 올 때마다 책상을 가져온다고 생각하면 되죠
- 아무 데나 앉아도 상관이 없습니다.
- 단, 논리적으로는 순서를 매겨서 기억해야 합니다.
스택(Stack)
스택은 말 그대로 쌓는 자료구조입니다.
상자를 위로 쌓듯, 나서스 스택 작을 하듯 하는 그 자료구조이죠.
상자를 위로 쌓고, 위에서부터 꺼내듯 스택은 모든 연산이 전부 맨 위에서 이루어집니다.
사실, 이 예시는 우리가 흔히 프로그래밍할 때 볼 수 있습니다.
- 함수 구조가 스택 메모리를 사용하기 때문이죠.
- main 함수에서 a 함수를 부르고, a 함수가 작업이 끝나면 다시 나갑니다.
- 가장 최근에 데이터를 꺼낸다거나, 장기에서 무르기 기능을 구현할 때 스택을 활용할 수 있습니다.
- 알고리즘에서는 DFS에 스택 구조를 쓸 수 있죠.
나중에 포스팅할 거지만 DFS는 깊이 우선 탐색 알고리즘 입니다.
큐(Queue)
이 자료구조는 선착순 개념과 같다고 보시면 됩니다.
나중에 들어온 사람이 먼저 나가는 스택과는 다르게, 먼저 들어온 사람이 먼저 나가는 방식이 큐지요.
그래서 우리는 스택을 LIFO 방식, 큐는 FIFO 방식이라고 부릅니다.
LIFO(Last In First Out) : 후입선출 즉, 나중에 들어온 사람이 먼저 나가는
FIFO(First In First Out) : 선입선출 죽, 먼저 들어온 사람이 먼저 나가는
큐는 맨 앞부분을 front, 자료가 추가되는 부분을 rear라고 부릅니다.
- 자료는 front 부분에서 꺼낼 수밖에 없고, rear 부분에서 추가해야 합니다.
자료 추가 오퍼레이션을 enQueue, 자료 삭제 오퍼레이션을 deQueue라고 합니다.
스택과 큐는 어떻게 구현하냐?
스택과 큐는 배열 혹은 연결리스트로 구현할 수 있습니다.
나중에 구현해볼 겁니다. 일단 스택은 배열로, 큐는 연결리스트로 구현해보죠.
마치며
네. 선형 자료구조에 대해 알아보았습니다.
다음 시간에는 트리, 그래프 같은 비선형 자료구조에 대해 배워보도록 하죠!
수고하셨습니다.
