Computer Science/Data structure & Algorithm
그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 필수적으로 알고 있어야 하는 개념이다. 원래 귀찮아서 글을 안썼는데 알고리즘 시험 범위에 들어가있어서 이번 기회에 정리했다. BFS (Breadth First Search) 너비우선탐색 : 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법 Queue를 이용하여 구현한다. 과정 q와 visitied을 이용해 구현할 것이다. - q : 다음 방문할 노드를 담아두는 자료구조 - visited : 노드의 방문 여부를 기록해두는 곳 -> visited를 사용하지 않으면 무한 루프에 돌 수 있다. 시작 정점을 q에 삽입..
그래프 정의 G = (V, E) V : 공집합이 아닌 유한한 정점의 집합 E : 유한한 edge들의 집합. 그래프 종류 방향성에 따른 분류 Undirected Graph 방향성이 없는 그래프 (u, v) = (v, u) Directed Graph 방향성이 있는 그래프 != 위 사진의 a, b가 undirected이고 c가 directed이다. 순환성에 따른 분류 Cyclic Graph 시작과 끝이 동일한 path가 있는 그래프 Acyclic Graph 순환할 수 없는 그래프 (tree가 대표적인 acyclic graph이다.) 가중치에 따른 분류 Unweighted Graph edge에 가중치가 없는 경우 Weighted Graph edge에 가중치가 있는 경우 / 인접 행..
최단 경로 문제 (Shortest path problem) 가중치가 있는 그래프에서 한 정점에서 다른 정점까지 갈 수 있는 최단 경로를 구하는 문제이다. s 에서 t로 갈 때 지나가는 경로 상에 있는 cost의 합이 최소화 되는 경로를 찾는 경우이다. 최단경로 문제는 Internet packet routing, flight reservation, driving directions 등 다양한 경우에 사용된다. 최단경로 문제를 해결하는 방법은 여러가지가 있는데 그 중에 대표적인 것은 아래 세 가지이다. 다익스트라 알고리즘 (Dijkstar's algorithm) 플로이드-와샬 알고리즘 (Floyd Warshall algorithm) 벨만 포드 알고리즘 (Bellman Ford algorithm) 오늘은 이 ..
허프만 코드는 그리디 알고리즘으로 해결할 수 있는 대표적인 문제이다. 오늘은 허프만 코드가 무엇인지, 그리고 어떻게 구현하는지에 대해 알아볼 것이다. 2023.06.08 - [Computer Science/Data structure & Algorithm] - [Algorithm] Greedy Algorithm (탐욕 알고리즘) [Algorithm] Greedy Algorithm (탐욕 알고리즘) Greedy Algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. (위키피디아) 탐욕법 : 단계마다 최적의 선택을 ..
Greedy Algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. (위키피디아) 탐욕법 : 단계마다 최적의 선택을 하여 문제 해결을 수행하는 경험론적 알고리즘. 그리디 알고리즘은 이름에서 유추할 수 있듯이 각 단계마다 당장 가장 '좋은' 방법을 선택한다. 문제를 전체적으로 고려해 가장 좋은 것을 찾는 DP나 이진탐색과는 차이가 있다. 기본 접근법 선택 절차 (selection procedure) 특정 후보 중에 하나를 선택해 해당 방식이 주어진 문제의 해인지 결정하는 절차이다. 이때 해는 현재의 상황에서 가장..
지난번에 가방 문제가 무엇인지 알아보고 0/1 knapsack problem을 DP 로 해결하는 방법을 알아보았다. 이번에는 그 글을 이어서 fractional knapsack problem에 대해 알아보겠다. 0/1 knapsack problem 과 다른 상황이니 주의하고 글을 읽기 바란다. 0-1 knapsack 은 greedy algorithm으로 풀 수 없다. 2023.06.07 - [Computer Science/Data structure & Algorithm] - [Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용 [Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용 Knapsack problem 어떤 물건들의 집합이 주어졌..
Knapsack problem 어떤 물건들의 집합이 주어졌을 때, 가방에 담을 수 있는 최대 가치의 물건들의 집합을 결정하는 문제 Knapsack problem은 크게 2가지 유형이 있다. 0/1 knapsack problem Fractional knapsack problem (a)가 문제상황이다. (b)와 달리 (c)는 물건을 쪼개서 (20/30) 가방에 넣었다. 이렇게 쪼갤 수 있는 경우를 Fractional problem, 그러지 못하는 상황을 0/1 knapsack problem이라고 한다. 오늘은 이 중 Dynamic programming으로 해결할 수 있는 0/1 knapsack problem에 대해 자세히 알아보겠다. 2023.06.08 - [Computer Science/Data struc..
Floyd-Warchall 알고리즘 그래프에서 모든 노드 간의 최단경로를 찾는 r다이나믹 프로그래밍 기법이다. 보통 플로이드 와샬 알고리즘을 다루기 전에 다익스트라 부터 공부하는데, 알고리즘 수업이 반대로 학습해서 나도 플로이드와샬부터 정리하겠다. 1. 문제 상황 가중치가 있는 그래프에서 모든 노드 간 최단경로를 찾는다. 1에서부터 5로 간다고 생각해보자. 그럼 1 -> 2 -> 4 -> 5 로 갈 수도 있고, 1-> 3-> 2-> 4-> 5로 갈 수도 있다. 비용만 살펴보면 첫번째 경우는 1+2+4=7의 비용이 발생하고 두번째 경우는 12의 비용이 발생한다. 즉, 1에서 5로 가는 최단경로는 1 - 2- 4- 5라는 것을 알 수 있다. 알고리즘 초심자에게 이걸 설명해주면 반정도의 사람들은 의문을 가진다..
2023.05.22 - [Computer Science/Data structure & Algorithm] - [Algorithm] Needleman-Wunsch algorithm [Algorithm] Needleman-Wunsch algorithm 오늘은 Alignment algorithm 중 global alignment에 해당하는 Needleman-Wunsch algoritm(니들만 브니쉬) 에 대해 알아보겠다. alignment 알고리즘은 LCS (longest commen sequence) 알고리즘과 유사하다. LCS에 대해 궁금하면 mobuk.tistory.com Needleman-Wunsch algorithm에 이어서 설명을 진행하기 때문에 꼭 이전 글을 읽고 오길 바란다. Smith-Wate..
오늘은 Alignment algorithm 중 global alignment에 해당하는 Needleman-Wunsch algoritm(니들만 브니쉬) 에 대해 알아보겠다. alignment 알고리즘은 LCS (longest commen sequence) 알고리즘과 유사하다. LCS에 대해 궁금하면 아래 글을 참고하자. 2023.05.21 - [Computer Science/Data structure & Algorithm] - [Algorithm] LCS (Longest Common Sequence) [Algorithm] LCS (Longest Common Sequence) DP의 대표 문제 중 하나인 LCS에 대해 다루어 보겠다. Longest Common Substring 공통 부분 문자열을 찾으라고 ..
