그래프 Graph 그래프란? 정점(Vertex)의 집합과 이들을 연결하는 간선(Edge)의 집합으로 구성되어있다. 주로 선형 자료구조나 트리로 표현하기 어려운 M:N 관계를 표현하기 위해 주로 사용됩니다. 트리도 그래프의 한 종류이다. ✅ 용어 정점(Vertex) :노드(node), 데이터 저장 간선 (Edge) : 정점을 연결하는 선 분지수(차수, degree) : 무방향 그래프에서 하나의 정점에 붙어있는 간선 개수 내향 분지수 (진출 차수, in-degree): 방향 그래프에서 들어오는 간선의 수 외향 분지수(진입 차수, out-degree): 방향 그래프에서 나가는 간선의 수 인접 인접(adjacent) : 정점 사이 간선이 있음 부속(incident) : 정점과 간선 사이 관계 경로(path) :..
브루트 포스 Brute Force Brute Force란? 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져오는 알고리즘 방식입니다. Brute Force 특징 이 알고리즘의 가장 큰 특징은 모든 영역을 전체 탐색하는 방법입니다. 전체 탐색하는 방법으로는 선형구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색 DFS, 너비 우선 탐색 BFS가 기본적인 도구입니다. 예를 들어서 4개의 숫자를 Brute Force 장점 경우의 수가 상대적으로 작을 때 유용합니다. Brute Force 단점 경우의 수가 상대적으로 늘어나기 시작하면 수행 속도가 느려져 시간복잡도에 매우 민감하다는 단점이 있습니다. 브루트 포스 알고리즘) 백준 토마토 7569 문제 풀어보기 75..
버블정렬 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 첫번째-두번째와 두번째-세번째, 세번쨰-네번째 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 이해하지 쉽고 구현도 쉽지만, 시간복잡도가 O(n^2)이기 때문에 비효율적이다. import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] arr = {36, 12, 18, 15, 41, 19}; int n = arr.length; //첫번째 원소와 인접한 원소를 비교, //두번째 원소와 세번째 원소를 비교 // ... // n-1번째 원소와 n번째 원소를 비교 for (int i = 0; i < n..
✅ 이진 탐색 트리 탐색 작업을 효율적으로 하기 위한 자료 구조 모든 노드의 데이터가 서로 다른 이진 트리 어느 노드에게 자식이 있는 경우 왼쪽 자식의 데이터는 부모보다 작다 오른쪽 자식의 데이터는 부모보다 크다 루드 노드 기준으로 왼쪽 서브 트리의 모든 데이터는 루트 노드보다 작다. 오른쪽 서브 트리의 모든 데이터는 루트 노드보다 크다. 중위 순회 할 경우, 오름차순 정렬된 데이터를 얻을 수 있다. ✅ 탐색 루트 노드와 탐색데이터를 비교 데이터가 더 작을 경우 왼쪽 서브트리로 (6과 12를 비교)O(h) ~ O(logn) 데이터가 더 클 경우 오른 쪽 서브트리로 편향 이진트리의 경우 O(n) ✅ 삽입 탐색 과정을 따라간다. 탐색에 성공할 경우 삽입 불가 탐색에 실패하는 시점에 새로운 노드로 데이터 추가..
Tree란? 한 개 이상의 노드로 이루어진 유한 집합 상위 원소와 하위 원소의 관계가 있는 계층적 자료 구조 하위 원소로 내려가면서, 나무의 가지가 자라나는 모습에서 Tree라는 이름이 붙었다. 각각 데이터를 담고 있는 원소를 노드 또는 정점이라고 한다. 노드 중 최상위 노드를 루트(root)노드라 한다. 각 노드는 0개 이상의 자식 노드를 가질 수 있다. 하나의 부모에 여러 자식이 연결되어 있다. 하나의 자식은 둘 이상의 부모를 가질 수 없다. 노드의 갯수가 N개 일 때, N-1개의 간선을 가지고 있다. 그래서 순환 구조가 생기지 않는다. ✅ 형제 노드 같은 부모 노드를 가진 자식 노드들 ✅ 조상 노드 간선을 따라 루트 노드까지 가는 경로의 모든 노드들 ✅ 서브 트리 부모 노드와 연결된 간선을 끊었을 ..
깊이 우선 탐색 (DFS) : 깊이 우선 탐색은 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 그래프를 비롯한 비선형 자료구조에서 모든 자료를 빠짐없이 검색하는 방법 중에 하나 입니다. DFS는 스택 자료 구조 (혹은 재귀 함수)를 이용한다. 지도에 표시된 모든 곳에 들르기로 했는데, 길을 가다가 갈림길을 만났다고 가정해보자. 갈림길은 어느쪽이든, 들러야 하는 지점으로 향한다. 이렇게 갈림길에서 한쪽 방향을 고집하며 가장 깊게 들어가는 방식으로 탐색하는 방식을 깊이우선탐색이라고 부릅니다. 구현방법 방문한 점에서 도달할 수 있는 점들을 살펴보고, 아직 방문하지 않은 점들의 정보를 스택에 PUSH한다. 스택에서 점의 정보를 pop 하여 방문한다. 이후 다시 1번으로 돌아간다 스택이 빌 때까지 반복한다. 정..
