코딩 테스트/자료구조 & 알고리즘

그래프(Graph)란?그래프(Graph)란 노드와 간선을 이용한 비선형 데이터 구조로 데이터 간의 관계를 표현하는데 사용된다.데이터를 노드로 데이터 간의 관계는 간선으로 표현한다. 또한 데이터 간의 관계에서 정도를 표현할 필요가 있다면 가중치를 사용해 표현한다.그림으로 표현하면 다음과 같다.참고로 노드, 간선, 가중치는 다음과 같은 용어로 혼용된다.노드(Node)정점버텍스(vertex)간선엣지(Edge)가중치(Weight)비용(cost) 그래프의 종류방향성간선은 그래프에서 두 정점간의 관계를 나타낸다.그래프에서 간선은 방향을 가질 수도 있고 없을 수도 있다.그래프가 방향이 있는 간선을 포함하면 방향 그래프그래프가 방향이 없는 간선을 포함하면 무방향 그래프라고 한다.가중치그래프에선 가중치를 통해 관계의 정..

상호베타적(서로소) 집합이란?상호베타적 집합(또는 서로소 집합: Disjoint Set)이란 교집합이 없는 집합관계를 의미한다. 상호베타적 집합은 다음과 같이 트리 형태로 표현한다.집합 A와 B는 교집합이 존재하지 않으므로 상호베타적 집합이라고 할 수 있다. 상호베타적 집합 표현하기상호베타적 집합은 위에서 봤듯 트리 구조로 표현할 수 있다. 이에 대해 더 자세히 알아보도록 하자. 대표원소상호베타적 집합에서 각각의 집합에는 대표원소라는 것이 존재한다.대표원소는 트리의 루트노드에 해당한다. 상호베타적 집합을 배열로 구현하기트리구조로 표현한 상호베타적 집합은 배열로 구현할 수 있다. 방법은 간단하다.배열에 자신의 부모 노드에 해당하는 원소값을 넣으면 된다.루트노드일 경우에는 자신의 원소값을 넣는다. 그림으로 ..

이진 탐색 트리(Binary Search Tree)이진 탐색 트리란?이진 탐색 트리는 다음의 두 가지 조건을 만족하는 이진 트리이다.1. 왼쪽 자식노드들은 자신의 부모 노드보다 작다.2. 오른쪽 자식노드들은 자신의 부모 노드보다 크다(같을 때도 오른쪽). 이러한 배치는 트리에서 특정 데이터를 찾거나 삭제할 때 매우 유용하다. 탐색예를 들어 4라는 값을 찾는다고 가정해보자 4는 8보다 작으므로 왼쪽으로 이동한다.4는 3보다 크므로 오른쪽으로 이동한다.4는 6보다 작으므로 왼쪽으로 이동한다4를 찾았다.이진 탐색트리에서 특정 값을 탐색할 때 아래 노드로 내려갈 때마다 그 반대쪽 노드들은 무시해도 되게 된다.이는 시간복잡도가 O(logN)이 됨을 의미한다.배열에서는 인덱스 순서대로 비교해가며 탐색을 했기 때문에..

트리(Tree)란? 트리의 개념트리는 노드와 간선으로 이루어진 계층형 자료구조이다.나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놨다해서 트리라는 이름이 붙여졌다.계층 구조로 이루어져있기 때문에 데이터를 저장하고 탐색하기에 유용하다. 트리의 구성요소노드트리를 구성하는 요소 루트 노드노드 중 가장 위에 있는 노드 엣지(간선)노드와 노드를 연결해주는 선단방향이며 루트 노드에서 각 노드까지의 경로는 유일하다. 노드 간의 관계엣지로 연결된 노드들은 부모-자식 관계를 가지는데 상위에 있는 노드를 부모 노드, 하위에 있는 노드를 자식 노드라고 한다.같은 부모 노드를 가지는 노드를 형제 노드라고 한다. 리프 노드자식 노드가 없는 노드 차수특정 노드에서 아래로 향하는 엣지의 갯수 이진트리 순회하기 이진 트리란?..