.png)
자료구조
배열
1) 원소 덧붙이기, 끝에서 꺼내기
- O(1) : 순식간에 할 수 있는 일로, 리스트의 길이와 무관
- 상수 시간 : 즉 아무리 리스트의 길이가 늘어난다 하더라도 시간이 증가하지 않는다.
2) 원소 삽입, 삭제하기
- O(n) : 리스트가 길면 오래걸리는 일
- 선형 시간 : 리스트의 길이에 비례
연결 리스트
선형탐색 & 이진탐색
선형탐색
- 보통 앞에서 시작해서 뒤쪽으로 진행하며 찾는 원소가 나올 때까지 진행.
- O(n) : 리스트의 길이에 비례하여 시간 소요
- 최악의 경우 모든 원소를 다 비교해 봐야 한다.
이진 탐색
- 배열이 미리 원소의 크기 순서대로 정렬되어 있음을 가정
- 반씩 잘라, 찾는 원소가 있을 가능성이 없는 쪽을 버림
- 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
- 크기 순으로 정렬되어 있다는 성질 이용
- O(log n) : 한 번 비교가 일어날 때마다 배열 절반씩 줄임
이진탐색이 선형탐색보다 효율적일 수 있지만, 언제나 그렇지는 않다.
이진탐색을 위해 배열을 크기 순으로 정렬을 할 때, n에 비례하는 것보다 더 복잡한 시간 복잡도가 든다.
때문에 데이터가 크고, 여러번의 탐색을 행한다면 이진탐색을 선택하지만, 한번만 탐색을 행한다면 선형탐색이 더 효율적일 수 있다.
스택 & 큐
스택
- 자료를 보관할 수 있는 선형 구조
- 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고(푸쉬)
- 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 한다.(팝)
- 후입선출(LIFO)
큐
- 자료를 보관할 수 있는 선형구조
- 단, 넣을 때에는 한 쪽 끈에서 밀어 넣아야 하고(인큐 연산)
- 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음(디큐 연산)
- 선입선출(FIFO)
트리
이진트리
- 모든 노드의 차수가 2이하인 트리
이진 탐색 트리
모든 노드에 대해서
1)왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고,
2) 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을,
만족하는 이진 트리
(중복되는 데이터 원소는 없는 것으로 가정)
.jpg)
정렬된 배열을 이용한 이진 탐색과 비교
- 장점 : 트리의 형태를 갖추고 있기 때문에, 데이터 원소의 추가, 삭제가 용이
- 단점 : 공간 소요가 큼, 데이터를 담고 있는 노드를 표현해야 하고, 이차원 트리구조로 표현하기 위해 연결관계를 표현하기 위해서도 메모리가 소요되기 때문이다.
start coding