Data Structures/Graph
-
최대 부분 증가 수열 - LISData Structures/Graph 2023. 9. 29. 17:14
Longest Increasing Subsequence 나무위키 최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki 최장 증가 부분 수열 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. `3 5 7 9 2 1 4 8` 위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다. 3 7 9 1 4 8 (5, 2 제거..
-
TreeData Structures/Graph 2023. 9. 29. 17:14
트리(Tree)는 계층적인 구조를 표현하는 비선형 자료구조로 노드(Node)와 간선(Edge)으로 이루어져 있으며, 루트(Root) 노드에서부터 여러 개의 자식 노드들이 분기(Branch)되어 나가는 형태로 구성된다. 대표적인 트리의 종류는 다음과 같다. 삼항 트리(Ternary Tree) : 각 노드가 최대 세 개의 자식 노드를 갖는 구조 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 갖는 구조 이진 검색 트리(Binary Serach Tree) 최대 두 개의 자식을 가지는 구조 노드의 왼쪽 자식의 값이 자신의 값 이하이며,오른쪽 자식의 값은 자신의 값 이상이다. 이진 검색 트리의 장점 가운데 하나로 룩업 연산(특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 처리할 수..
-
Graph 활용-1Data Structures/Graph 2023. 9. 29. 17:13
출처 엔지니어 대한민국 문제 1. Graph에서 두지점의 경로찾기 그래프에서 두 개의 노드가 서로 찾아갈 수 있는 경로가 있는지 확인하는 함수를 구현해보자 그래프에서 특정 노드 A와 B를 잇는 간선의 존재 여부를 판단하는 메서드이다. DFS와 BFS 두 가지 방법 모두 경로를 찾을수 있지만 이런 문제의 경우 시작점을 기준으로 영역을 점차 넓히며 접근하는게 조금 더 빠른 방법일 수 있기 때문에 BFS, 넓이 우선 탐색을 사용해 접근한다. 구현 import java.util.LinkedList; import java.util.Iterator; import java.util.NoSuchElementException; class Queue{ } class Graph{ class Node{ int data; //..
-
Graph에 대해Data Structures/Graph 2023. 9. 29. 17:13
그래프(Graph)와 트리(Tree)는 모두 노드(Node)와 노드를 연결하는 간선(Edge)으로 구성된 자료 구조이지만 몇 가지 차이점이 존재한다. 순환(cycle)의 존재 여부 그래프는 순환을 가질 수 있지만, 트리는 순환을 가질 수 없다. 트리는(DAG, Directed Acyclic Graph)라고도 부른다. 루트(Root)의 존재 여부 - 트리는 하나의 루트 노드를 가지며, 모든 노드는 루트 노드로부터 유일한 경로로 연결된다. - 그래프에는 루트 노드가 없다. 간선의 방향성 그래프의 간선은 양방향일수도 있고, 단방향일수도 있지만 트리는 단방향이다. 연결성 그래프에서는 연결성(Connectivity)이 중요한 개념이지만, 트리에서는 연결성이 보장된다. 즉, 트리는 모든 노드가 연결되어 있어서 어떤..
-
Graph 검색 구현Data Structures/Graph 2023. 9. 28. 23:07
그래프를 검색하는 방법은 대표적으로 깊이 우선 검색(Depth-First Search, DFS), 넓이 우선 검색(Breadth-First Search, BFS)가 있다. DFS DFS는 이진 트리를 순회할 때 사용했던 inorder, preorder, postorder 순회 방법이 깊이 우선 검색에 속하는데 시작 노드에서 자식 노드로 탐색을 진행하다 더 이상 탐색할 자식 노드가 없으면 부모 노드로 돌아가 다음 자식 노드를 탐색하고 이 과정을 반복해 그래프를 끝까지 탐색하게된다. DFS는 모든 노드를 탐색하며, 각 노드를 한 번씩 방문한다. DFS는 그래프에서 연결된 모든 노드를 방문할 수 있으며, 이를 통해 그래프의 구조를 파악하는데 도움이 된다. 또한, 그래프에서 경로를 찾거나 사이클을 검사하는데 사..