개요
입문자들을 위한 코딩테스트 준비과정을 작성하다보니 자료구조에 대한 기초지식을 짚고 넘어가야겠다는 생각을 했다.
- 1:1 선형 자료구조
- List(Array), Linked-List, Charset, Stack, Queue
- 1:N 비선형 자료구조
- Tree, Graph
- 필요한 설명을 모두 적는 것 보다, 좋은 링크가 있다면 첨부하면서 작성하겠다.
1:1 선형 자료구조
List(Array)
- index가 있어서 random-access 가 가능하다
- 특정 위치에 삽입, 삭제가 어렵다 : O(N)
- 마지막위치, 처음위치는 경우에 따라 O(1)도 가능
Linked-List
- Geek for Geeks
- index가 없는 대신 각 노드가 다음 노드의 주소를 저장하고 있다.
- 따라서 Circular 형태도 가능하다
- Circular 인지 판단하는 방법은 fast-runner, slow-runner 기법 사용!
- 삽입, 삭제가 매우빠르다 : O(1)
- 특정 노드 검색은 느리다 : O(N)
Charset
- ASCII 위키페이지
- character set은 이름 그대로 문자의 집합
- 컴퓨터에서는 char를 해석하기 위해서 int형으로 각 char를 표기함
- 알고리즘 작성 수준에서는 ASCII 정도로 적당함(127개)
- 'A' = 65
- '0' = 48
- 'a' = 97
- 외울필요는 없다
Stack
- LIFO(Last In First Out) 형식의 자료 구조
- push, pop, top, isEmpty 등의 method 사용
- 재귀 알고리즘, DFS(깊이 우선 탐색), 웹 브라우저 방문기록(뒤로가기), 후위표기법, 수식 괄호 검사 등에 사용됨
Queue
- FIFO(First In First Out) 형식의 자료구조
- push, pop, isEmpty 등의 method 사용
- 데이터를 입력된 순서대로 처리해야 할 때, BFS (너비 우선 탐색) 구현할 때
1:N 비선형 자료구조
Graph
- 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
- 순회는 BFS, DFS 방식으로 가능하다
- 구현방법
- 인접행렬
- 인접리스트
Tree
- 트리는 그래프에 포함된 개념이다
- 일반적으로 자식이 2개가 최대인 이진트리를 일컫는다
- 이진트리, 이진탐색트리, 힙, 세그먼트트리, 트라이, 아호코라식트리 등등... 범위가 매우 다양하다
- 알고리즘 수준에서는 이진트리, 이진탐색트리, 힙 정도 익히면 된다.
hello world