자료구조
데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조
배열 (Array)
배열은 가장 기본적은 data 구조다. index와 index에 해당하는 요소(Element)로 구성된다.
특징
- 길이가 고정되서 생성된다. (정적 메모리 할당)
- Random Access를 지원한다. 즉, index 통해 각 요소에 직접 접근할 수 있는 특징이 있다.
- 배열은 논리적 순서와 물리적 순서가 일치한다. 인접한 메모리 위치에 연이어 저장된다.
시간 복잡도
-
검색 : 요소마다 index 부여했기 때문에, 특정 요소 접근하는 시간 복잡도는 O(1)이다. 하지만 index를 모르는 특정 값을 찾기 위해서는 배열의 모든 요소들을 살펴봐야 하기 때문에 O(n)의 시간 복잡도를 갖는다.
-
추가/삭제 : 삽입이나 삭제를 하기 위해서는 길이가 고정되어 있기 때문에 차례대로 한 칸씩 밀어야 하는 과정이 필요하고 그 과정에서 O(n)의 시간 복잡도가 생긴다.
기타
배열 이용해 구현
장점 : index 통한 순차적 접근 유리
단점 : 삽입, 삭제 시 계산량 많아짐 (해당 index 기준 앞/뒤 shift 연산 필요)
연결 리스트 (Linked List)
배열의 추가/삭제 연산에 대한 비효율성을 극복하고자 등장한 data 구조다. 각 요소는 다음 노드 연결에 대한 정보를 담은 포인터 또는 주소와 함께 노드에 저장된다.
단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등의 종류가 있다.
특징
- 새로운 요소가 추가될 때 런타임에 메모리를 할당한다 (동적 메모리 할당)
- Sequential Access를 지원한다. 요소에 접근할 때 순차적으로 접근해야 하는 특징이 있다.
- 인덱스나 위치와 같은 물리적 배치를 사용하지 않고 참조 시스템(다음 노드 연결에 대한 포인터 또는 주소)을 사용한다.
시간 복잡도
- 검색 : 처음부터 순차적으로 접근해야하기 때문에 O(n)의 시간 복잡도를 갖는다.
- 추가/삭제 : 동적인 메모리 크기를 갖기 때문에, 새로운 요소를 추가하거나 삭제할 경우에 해당되는 부분만 변경하면 되기 때문에 O(1)의 시간 복잡도를 갖는다.
기타
node = data + next로 구성 : next 다음 node 위치 저장
단일 연결 (Singly Linked List)
: 동적 메모리 사용하지만, 특정 데이터 찾으려면 head부터 찾아야함
이중 연결 (Doubly Linked List)
: 양방향으로 각 node의 전,후 알 수 있지만, pointer를 2개 보유해야 함
원형 연결 (Circular Linked List)
: 마지막 node의 next가 첫번째 node 가리킴
Stack
순서가 보존되는 선형 자료구조
한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 후입선출 형식의 자료 구조
펜케이크 비유를 들면 이해가 잘간다.
펜케이크 굽다가 누가 달라고 하면
맨 위에 놓은 펜케이크를 주는것이 stack이다.
특징
- data 받는 순서대로 정렬
- LIFO, 후입선출
- 동적 메모리
시간 복잡도
- 검색 : 처음부터 순차적으로 접근해야하기 때문에 O(n)의 시간 복잡도를 갖는다.
- 추가/삭제 : 가장 위에 데이터를 추가하거나 삭제하기 때문에 O(1)의 시간 복잡도를 갖는다.
기타
Array / Linked List로 구현
함수 호출 및 재귀 프로그램 순서 제어, 서브루틴 호출 시 주소 저장 등에서 사용
Queue
순서가 보존되는 선형 자료구조
먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 선입선출 구조를 가진다.
특징
- data 받는 순서대로 정렬
- FIFO, 선입선출
- 동적 메모리
시간 복잡도
- 검색 : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다.
- 추가/삭제 : 가장 위에 data를 추가하거나 삭제하기 때문에 O(1)의 시간 복잡도를 갖는다.
기타
Array / Linked List로 구현
Heap
최댓값 , 최솟값 찾아내는 연산 쉽게 하기 위해 고안된 구조
완전 이진 트리의 일종
여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록
만들어진 자료구조
데이터들 우선순위 가지고 있어 우선순위 높은 데이터 먼저 나간다
설명 참고 site
https://im-designloper.tistory.com/109
hash table
hash table은 ( Key, Value)로 data를 저장하는 자료구조 중 하나로 빠르게 data를 검색할 수 있는 자료구조이다
hash 테이블 구현하기 위해서는 연결 리스트와 해시 함수가 필요하다.
Hashing은 해시 함수를 통해서 임의의 값을 고정된 크기의 값으로 변환하는 작업
key 값을 입력 받아 해시 함수를 통해 얻은 해시를 배열의 index로 환산해서 값에 접근하는 것을 의미
특징
- Key 값을 배열의 index로 사용하기 때문에, 값을 직접 접근할 수 있다. 따라서 해시 테이블의 평균 시간 복잡도는 O(1)이다. ( 운이 없어 충돌이 일어나는 경우 O(n))
- 충돌이 발생할 수 있다. 이 경우 분리 연결법 혹은 개방 주소법을 사용해 해결한다.
- data 저장되기 이전 미리 공간을 만들어야한다. 공간 복잡도 크다.
- 해시 함수 통해 배열 index의 범위를 조절할 수 있다. 이를 Resizing(리사이징)이라고 한다.
- key와 해시의 연관성이 없어 보안에도 자주 사용
충돌 해결방법
-
Separate Chaning (분리 연결법) : Linked List, Tree를 사용하는 방법. 충돌이 발생하는 경우 index가 가리키고 있는 값에 노드를 추가해 값을 추가한다. 대신, 두 방법 모두 많이 추가하면 비효율적이다.
-
Open Address (개방 주소법) : 해시 테이블의 빈공간을 사용하는 방법이다. 추가적인 메모리 공간을 필요하지 않은 장점이 있다. 그 방법에는 Linear Probing, Quandratic Probing, Double Hashing 등이 있다.
기타
그래프
그래프는 비선형 자료구조로, 노드/정점(Vertice)과 이들 사이를 연결하는 엣지(Edge)로 구성된 자료구조를 의미한다.
특징
- 그래프는 방향이 있을 수도(Directed) 없을 수도(Undirected) 있다.
- 다양한 구조로 설계된다. 구조에 따라서 시간 복잡도가 달라지고 다양하게 응용이 가능하다.
- 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
- 시간 복잡도/공간 복잡도를 이야기할때 노드(N)/정점(V)과 엣지(E)의 수를 사용해 표현한다.
시간 복잡도
-
두 노드의 연결 확인 : 인접행렬의 경우 고유 index로 바로 접근 가능해 O(1)의 시간 복잡도를 갖는다. 인접 리스트의 경우 한 노드의 인접 리스트 안의 특정 노드가 있는지 확인해야 하기 때문에, 최악의 경우 전체를 봐야하므로 O(N)/O(V)의 시간 복잡도를 갖는다.
-
한 노드에 연결된 모든 노드 확인 : 인접 행렬의 경우 특정 노드를 나타내는 행렬을 돌아서 연결된 노드를 가져와야 하기 때문에, O(N)/O(V)의 시간 복잡도를 갖는다. 인접 리스트의 경우 연결된 노드의 갯수는 곧 엣지의 갯수이므로, 엣지의 갯수만 확인하면 되므로 O(E)의 시간 복잡도를 갖는다.
-
추가/삭제: 추가의 경우 노드/정점이나 엣지 모두 O(1)의 시간 복잡도를 갖는다. 하지만, 삭제의 경우에는 노드/정점의 경우 특정 노드/정점을 찾는 시간과 그와 연결된 엣지를 삭제해야 하므로 O(N+E)/O(V+E)의 시간 복잡도를 갖는다. 엣지의 경우 특정 엣지를 찾는 시간이 소요되므로 O(E)의 시간 복잡도를 갖는다.
Tree
트리는 비선형 자료구조, 노드로 구성된 계층적 자료구조
최상위 노드(Root)를 만들고, 부모 노드에 자식 노드를 추가하고 그리고 그 자식 노드가 부모 노드로써 또 다른 자식 노드를 추가하는 구조를 가지고 있다.
특징
- Tree에 또 다른 Tree가 있는 재귀적 자료구조이다.
- data를 순차적으로 저장하지 않는 비선형 자료구조다.
- 이진트리 (Binary tree), 이진탐색트리(BST), 균형트리(B-tree, Balanced tree), 힙트리(Heap tree) 등 다양한 종류가 존재한다.
우선순위 Queue와 내부 구조 및 시간복잡도
우선순위큐는 가장 우선순위가 높은 데이터 먼저 꺼내기 위해 고안된 자료구조
구현하기 위해서 일반적으로 힙을 사용한다.
힙은 완전이진트리를 통해 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)이다.
- logn 설명 : https://neos518.tistory.com/145
Array와 Linked List 차이
ArrayList는 data들이 순서대로 늘어선 배열의 형식을 취하고
LinkedList는 자료의 주소값으로 서로 연결된 형식을 가진다.
- Array
원하는 data에 무작위로 접근 가능
list 크기 제한되어 있고 list 크기를 재조정하는 것은 많은 연산이 필요
추가/삭제 위해 다른 요소들의 주소도 전부 변경(임시 배열 생성해 복제)해야 하기 때문에 비효율적
- LinkedList
처음부터 순차적으로 접근해야 해서 검색 비효율적이다.
list 크기에 영향 없이 data 추가할 수 있다.
추가/삭제 시 해당되는 요소 메모리 주소만 변경하면(새로운 node 생성해 연결) 되기 때문에 효율적
무작위 접근 불가능, 순차 접근만 가능
메모리 할당 차이
Array는 선언 시 요소들을 인접한 메모리 위치에 연이어 저장하고 크기 고정되어 있는 정적 메모리 할당
Linked List 새로운 요소 추가되면 메모리를 할당하고 그 정보를 저장한느 동적 메모리 할당
간단히 정리
Array는 검색 빠르지만 삽입/삭제 느림
LinkedList 삽입/삭제 빠르지만 검색 느림
Queue, Stack 구현
-
Queue : Array로 구현하면 poll 연산 이후 객체를 앞당기는 작업이 필요하다. 하지만 List로 구현하면 객체 1개만 제거하면 되므로 삽입/삭제가 용이한 LinkedList로 구현하는 것이 좋다.
-
Stack : List로 구현하면 객체를 제거하는 작업이 필요. 하지만 Array로 구현하면 삭제할 필요 없이 index를 줄이고 초기화만 하면 되므로, Array로 구현하는 것이 좋다.
Stack과 Queue의 차이점
두 자료구조 모두 순서 보존되는 선형 자료구조의 일종, 동시에 Push와 Pop과 같은 핵심적인 기능만 알면 되는 추상적 자료구조이기도 하다. 가장 큰 차이점은 처리하는 순서에 있다. Stack은 후입선출, Queue는 선입선출 메커니즘을 갖는다. 이러한 특징으로 Stack는 DFS나 재귀에 사용, Queue는 BFS나 캐시를 구현할 때 사용
DFS : 깊이 우선 탐색 / https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
BFS : 너비 우선 탐색 / https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
Stack과 Queue 실사용 예를 간단하게 설명
Stack - Java의 Stack 메모리 영역
지역변수와 매개변수 data 값이 저장되는 공간, method 호출시 memory에 할당되고 종료되면 memory 해제되며, LIFO 구조를 가진다.
Queue - OS의 스케쥴러
자원의 할당과 회수를 하는 스케쥴러 역활을 할 수 있다.
memory에 적재된 다수 process 중 어떤 process에 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고, 가장 단순한 형태의 스케쥴링 정책이 선입선출 즉 Queue라고 볼 수 있다.
ArrayList 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명
Array 가장 큰 특징 순차적으로 데이터를 저장
데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재, index를 사용해 특정 요소를 찾고
조작이 가능하다는 것이 Array의 장점
순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점도 존재해 정보 자주 삭제되거나 추가되는 데이터 담기에 적절하지 않다.
Array 적용시키면 좋은 데이터의 예를 들고 이유와 사용하지 않으면 어떻게 되는지 설명하세요
주식 차트가 있다.
주식 차트에 대한 data는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 data다.
순서가 굉장히 중요한 data이기 때문에 Array 같이 순서를 보장해주는 자료구조를 사용하는 것이 좋다.
Array를 사용하지 않고 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어렵고 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생
Array와 ArrayList 차이점
Array 크기 고정적, ArrayList는 크기 가변적
Array는 초기화 시 memory에 할당되어 ArrayList보다 속도 빠르고
ArrayList는 data 추가/삭제 시 memory 재할당하기 때문에 속도가 Array보다 느리다.
출처
https://dev-coco.tistory.com/159
https://mangkyu.tistory.com/89
https://re-code-cord.tistory.com/
