- 자료구조는 "데이터를 조직하는 방법"이라고 할 수 있다. 또는 "데이터를 표현하고 관리하고 처리하기 위한 구조"를 의미한다.
📖 Contents
- Data Structure
-
Stack이란, 데이터를 차곡차곡 쌓아올린 형태의 자료구조이다. 데이터가 순서대로 쌓이다가 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.
- Stack은 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되고 자료를 삭제할 때도 top을 통해서 삭제가 가능.
- Stack에서 삽입 연산은 push / 삭제 연산은 pop이라고 한다. 후입선출의 구조로 LIFO(Last In First Out)이라고 부른다.
- ex) 웹 브라우저 방문 기록 뒤로가기, 실행 취소(undo), 역순 문자열 만들기, 후위 표기법 계산
-
큐(Queue)는 먼저 들어온 것이 먼저 나가는 선입선출로 FIFO(First In First Out)의 구조를 가지고 있다.
- FIFO 구조를 위해서 큐의 왼쪽 끝에는 삽입 작업이 / 오른쪽 끝에는 삭제 작업이 나뉘어서 이루어진다.
- 삽입 연산이 이루어지는 곳을 리어(rear)라고 하고, 리어에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부른다.
- 삭제 연산이 이루어지는 곳을 프론트(front)라고 하고, 프론트에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부른다.
- ex) 은행 업무, 대기열 순서와 같은 우선순위의 작업 예약 등, 서비스 센터 대기시간, 프로세스 관리
-
시간 복잡도란, 우리가 작성한 코드의 실행시간이 실행해보기 전에 정확하게 추측하는 것은 힘들겠지만 반복문을 몇 번 사용했는지, 입력값은 어떻게 되는지 등을 통해 대략적으로 추측할 수 있다. 즉, 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.
-
시간복잡도 예시
- 복잡한 곱하기와 같은 연산이 없고 넣으면 바로 결과값이 나오는 O(1)
- for 루프 하나는 O(n)
- for문안에 for문은 O(n^2)
- O(n^2+n) 예시
for i in range(1000000):
for i in range(10000):
pass
for i in range(100):
...- 시간복잡도를 고려한다면, for문과 while문은 최대한 사용하지 않는 것이 좋다.
-
힙(heap)은 무언가를 차곡차곡 쌓아 올린 더미라는 뜻으로, 완전이진트리의 형태로 만들어진 자료구조이다. 즉, 위로 갈수록 노드의 수가 줄어드는 모습이다. 힙은 최댓값 혹은 최솟값을 빠르게 찾아내기에 유리한 자료구조이다.
- 이진트리는 각 노드가 최대 2개의 자식을 갖는 트리를 뜻한다. 즉, 각 노드는 자식이 없거나 한개이거나 두개만을 갖게 된다.
- 그리고 완전이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리 자료구조이다. 또한, 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
-
힙을 만드는 과정
- 값 삽입 - 힙 구조로 변경 - 값 삽입 - 힙 구조로 변경
- 이 과정에서 힙은 항상 부모 노드가 자식 노드보다 커야 한다는 조건이 지켜져야 한다. 그래서 매번 값이 들어올 때마다 값을 비교하고 swap을 해줘야 한다. 자식 노드들 끼리는 값을 비교하지 않는다.
- 힙 구조가 완성되면 완전 이진트리이면서 부모 노드가 자식 노드보다 큰 트리 구조이다. 이러한 과정을 통해 최댓값을 빠르게 찾을 수 있는 구조가 바로 힙이다.
- 힙 구조는 최댓값 혹은 최솟값을 빨리 찾기 위한 구조이지 이걸 사용했다고 정렬이 되지는 않는다.
- 링크드 리스트란, 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
- 링크드 리스트를 python으로 구현하면, 링크드리스트에서 가장 시작점인 데이터를 의미하는 Head부터 탐색해서 뒤에 노드가 추가된다. 그리고 링크드리스트에서 가장 마지막 데이터를 의미하는 Tail까지 존재한다.
- 하나의 노드를 클래스로 구현하면 self.data = data로 데이터가 있고, self.next = None라는 코드로 다음 데이터를 연결하기 위해 작성한다. Next=None(또는 Null)은 다음 데이터가 없을 경우 포인터의 주소값을 None(또는 Null)이라고 한다.
- 위의 내용과 같이, ArrayList는 index가 있고, LinkedList는 각 원소마다 앞,뒤 원소의 위치값을 가지고 있다. 이러한 특징으로 조회, 삽입, 삭제 시 아래와 같은 시간복잡도 차이를 가진다.
-
ArrayList
-
get/set
- 배열의 index를 통해 접근하는 방식이기 때문에, random access속도가 빠르며 get/set 메소드는 상수 시간을 가지게 된다.
-
add
- ArrayList는 배열이기 때문에 중간에 값을 끼워넣는 연산이 불가능하다.
- 만약 새로운 값을 추가하려고 할 때, List의 크기가 생성되어 있는 배열의 size(생성시 따로 설정하지 않았다면 size = 10인 배열이 생성된다)보다 커지게 되면, 이전 크기의 2배가 되는 배열을 생성해 배열 전체를 복사하여 새로운 배열에 복사하고 제일 뒤에 값을 추가해야 한다.
- 따라서 기존에 있던 배열에서 추가하고 싶은 index부터 마지막 index까지 한 칸씩 뒤로 미루는 연산이 필요하다. 그래서 해당하는 인덱스를 찾아가는 시간(O(1)) + 배열을 복사하는 시간(O(n)) = O(n)의 시간이 소요된다.
-
remove
- add와 유사하게 remove는 삭제된 index + 1부터 마지막 index까지 한 칸씩 앞으로 당기는 연산을 하게 된다. 따라서, add와 동일한 O(n)의 시간 복잡도를 가지게 된다.
-
LinkedList
-
get/set
- LinkedList는 연결 리스트 형태를 띄고 있기 때문에 해당하는 index에 대한 값을 얻어올 때 시작이나 끝에서부터 해당 index까지 순차적으로 접근하며 값을 얻어온다. 따라서, 시간 복잡도는 O(n)을 가진다.
-
add
- 일반적인 경우 : 추가를 원하는 index에 도달할 때까지 순차 접근을 하는 시간복잡도 O(n) / index-1의 노드의 next와 index+1의 prev를 새로 추가한 노드에 연결하는 작업은 n에 영향을 받지않는 상수 시간이기 때문에 O(1)이다. 따라서, O(n)의 시간복잡도를 가진다.
- 시작이나 끝에 요소를 추가할 때 : LinkedList는 head와 tail을 갖는 doubleLinkedList의 구조이기 때문에 시작과 끝에 해당하는 노드을 찾아가는데는 O(1)이라는 시간 복잡도를 갖게된다. 따라서, 시간 복잡도는 O(1)이다.
-
remove
- 일반적인 경우 : 원하는 index에 도달할 때까지 순차 접근을 하는 시간복잡도 O(n) / index - 1의 노드의 next를 index의 next의 요소와 연결하고, index + 1의 prev를 index의 prev요소로 변경하면 된다. List의 길이에 영향을 받지않는 상수 시간이기 때문에 O(1)이다. 따라서, O(n)의 시간복잡도를 가진다.
- 시작이나 끝에 요소를 삭제할 때 : 시작과 끝 요소를 찾아가는데 O(1)이라는 시간 복잡도를 갖기 때문에, 시간 복잡도는 O(1)이다.