자료구조, 알고리즘 간단 요약
업데이트:
자료구조 알고리즘 요약
*참고도서: 알고리즘도감, 윤성우의 열혈 자료구조
1. 리스트(list)
- 데이터(data), 포인터(pointer)로 구성
- 리스트는 데이터가 메모리상에서 연속된 위치에 저장 되지 않아도 되며, 일반적으로 서로 떨어진 영역에 흩어져서 저장됨. 이것으로 Spark를 사용할 때 dataframe이 왜 리스트 형식인지 추측할 수 있다.
- 데이터가 흩어져 있으므로 중간에 놓여있는 데이터에 접근하고 싶은 경우 첫 포인터부터 순서대로 따라가야함.
- 데이터 추가, 삭제 시에는 앞뒤 포인터를 변경하기만 하면 되기 때문에 간단함.
- 요약 : 데이터 접근 시에는 시간이 오래걸리지만, 데이터 추가/삭제는 빠른 시간에 가능.
2. 배열(array)
- 데이터가 연속된 메모리 영역에 순서대로 저장.
- a[0], a[1]과 같은 형식으로 데이터에 빠르게 접근 가능.
- 배열 중간에 데이터 추가, 삭제를 할 경우, 데이터가 연속되게 저장되어있으므로 추가될 공간 뒷부분의 데이터를 모두 한칸씩 오른쪽으로 이동시켜 공간을 확보해야 하므로 시간이 오래걸림.
- 요약 : 데이터 접근 시에는 시간이 빠르지만, 데이터 추가/삭제 시에는 시간이 오래걸림.
3. 스택(stack)
- 스택에 데이터를 추가하면(push) 가장 위에 추가됨.
- 스택에서 데이터를 꺼내면(pop) 가장 위(가장 최근 추가된) 데이터부터 꺼냄.
- Last In First Out(LIFO)
4. 큐(queue)
- 큐에 데이터를 추가하면(enqueue) 가장 위에 추가됨.
- 큐에서 데이터를 꺼내면(dequeue) 가장 아래(가장 오래된) 데이터부터 꺼냄.
- First In First Out(FIFO)
5. 해시 테이블
- 키(key) : 데이터 식별자
- 값(value) : 데이터 내용
- 각 데이터가 (키, 값) 한 쌍으로 구성됨.
6. 트리(tree)
- 이진트리는 재귀적인 특성
- 트리를 채우는 방향은 위에서 아래로, 왼쪽에서 오른쪽으로 채운다.
- 트리 순회(Traversal) 세가지 방법
- 전위 순회(Predrder Traversal): 루트 노드를 먼저
- 중위 순회(Inorder Traversal): 루트 노드를 중간에
- 후위 순회(Postorder Traversal): 루트 노드를 마지막에
6-1. 배열을 기반으로 트리 구현
- 배열을 기반으로 이진트리를 구현하려면 노드에 고유의 노드 번호를 부여해야한다.
- 배열을 기반으로 이진트리를 구현할때는 인덱스가 0인 배열의 요소는 사용하지 않는다. 왜냐면 구현할때 편리하고, 실수할 가능성을 낮춰주기 때문에 일반적으로 사용하지 않는다.