자료구조
-
트리순회자료구조 2021. 2. 15. 12:13
## 트리순회 - 트리순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한번 방문하는 과정을 말한다. 그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데 특히 이진 트리에서 DFS는 노드의 방문 순서에 따라 다음과 같이 크게 3가지 방식으로 구분된다. 1. 전위 순회(NLR) 2. 중위 순회(LNR) 3. 후위 순회(LRN) 순회 방식의 영문 두문자어를 구성하는 L, R, N 중 L은 현재 노드의 왼쪽 서브트리 R은 현재 노드의 오른쪽 서브트리, N은 현재 노드 자신을 의미한다. 즉 전위 순회는 NLR이므로 현재 노드를 먼저 순회한 다음 왼쪽과 오른쪽 서브트리를 순회하고, 중위 순회는 LNR이므로 왼쪽 서브트리를 순회한 다음 현재 노드 마지막으로 오른쪽 노드, 후회..
-
트리자료구조 2021. 2. 3. 15:49
트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다. 트리는 하나의 뿌리에서 위로 뻗어 나가는 형상처럼 생겨 '트리' 라는 명칭이 붙었는데, 트리 구조를 표현할 때는 나무의 형상과는 반대 방향으로 표현한다. 트리 구조는 ㄴ우리 주변 일상에서 쉽게 볼 수 있는 위아래 개념을 컴퓨터에서 표현한 구조다. 한 가족의 계보를 나타내는 족보나 회사의 조직등을 보면 보통 트리 구조 형태로 되어있다. 좀 더 중요한 트리의 속성중 하나는 재귀로 정의된 자기 참조 자료구조라는 점이다. 쉽게 말하면, 트리는 자식도 트리고 또 그지삭도 트리다. 즉 여거 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 궝된다고 표현하는데, 앞서 트..
-
그래프 순회자료구조 2021. 1. 23. 13:43
그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정을 이야기 한다. 그래프 순회는 크게 깊이 우선 탐색(Depth First Search)와 너비 우선 탐색(Breadth First Search)의 2가지 알고리즘이 있다. DFS - 일반적으로 BFS에 비해 더 널리 쓰인다. - 코테에서도 그래프 탐색은 주로 DFS로 구현하게 된다. - 주로 스택이나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보인다 앞서 말했듯 DFS는 스택으로 구현하며 재귀를 이용 하면 좀 더 간단하게 구현 할 수 있다. 코테에서도 재귀 구현이 더 선호된다. 재귀 구조로 구현 해당 사진은 위키피디아에 제시된 수도코드이다. 이 수도코드에서 정점 v(vertex)의 모든 인접 유향(Directed) 간선들을 반..
-
해시 테이블(해시 맵)자료구조 2021. 1. 22. 01:09
정의 - 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현 하는 자료구조이다. 특징 - 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이기 때문에 데이터 양과 관계없이 빠른 성능 기대 가능 해시함수 - 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수 - 사용되는곳: 체크섬, 손실 압축, 무작위화 함수, 암호 위 그림은 해시 함수를 통해 키가 해시 값을 변경되는 과정을 도식화 한것이다. 이처럼 해시 테이블을 인덱싱하기 위해서 해시 함수를 사용하는 것을 해싱이라고 한다. 여러 해시함수들 중에서 단순하고 널리쓰이는 정수형 해싱 기법인 모듈 연산을 이용한 나눗셈 방식 하나만 살펴보자. 수식은 아래와 같다. H(x) = x mod m 여기..