jundyu 님의 블로그

들어가며제목에서 알 수 있듯이 이번 글은 위상 정렬을 위한 Kahn's 알고리즘에 대한 글입니다. 그래프와 관련된 알고리즘이므로 아래의 그래프 이론과 해당 글에 연계된 그래프 탐색 알고리즘 글들을 먼저 읽어보면 이해하기 쉽습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com 위상 정렬 : Topological Sort1. 개념위상 정렬이란 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것입니다. 사전적 의미로는 어려울 수 있는데, 쉽게 말하면 해야할 일의 순서를..

들어가며이번 글은 벨만 포드 알고리즘에 관한 포스팅입니다. 만약 그래프 이론이나 다른 그래프 탐색 알고리즘들을 모른다면 먼저 읽어보고 오는 것을 추천합니다. 아래의 링크에 그래프 이론 및 탐색에 관한 내용이 잘 나와있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Bellman-Ford : 벨만 포드1. 알고리즘 명칭Bellman-Ford라는 알고리즘의 명칭은 "Richard Bellman"와 "Lester Ford Jr."이라는 수학자의 이름에서 유래되었습니다. 벨만 포..

들어가며이번 글은 그래프 탐색에 관한 글로 읽기 전에 아래의 링크에서 그래프 이론을 숙지하고, 너비 우선 탐색 및 데이크스트라 알고리즘을 먼저 익히고 나면 정말 쉽게 배울 수 있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com [Algorithm] BFS 알고리즘 with JAVA들어가며BFS 알고리즘을 공부하기에 앞서 그래프 이론을 먼저 공부하면 이 글을 이해하는 데 더 도움이 될 것 같습니다! 아래의 링크에 그래프 이론에 관한 개념이 잘 정리되어 있습니다. [Algorith..

들어가며벌써 3번째 그래프 탐색 알고리즘에 관한 글을 쓰게 되었습니다. 이번 글 역시 아래의 링크를 통해 그래프 이론을 먼저 숙지하고 읽는 겻을 추천드립니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Dijkstra : 데이크스트라1. 알고리즘 명칭Dijkstra라는 알고리즘의 명칭은 "Edsger Dijkstra"라는 네덜란드의 컴퓨터 과학자의 이름에서 유래되었습니다. 네덜란드식 발음으로는 데이크스트라가 맞지만 한국에선 흔히 다익스트라로도 많이 알려져있습니다. 따라서 이번 ..

들어가며BFS 알고리즘을 공부하기에 앞서 그래프 이론을 먼저 공부하면 이 글을 이해하는 데 더 도움이 될 것 같습니다! 아래의 링크에 그래프 이론에 관한 개념이 잘 정리되어 있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com 이번 글에선 그래프를 탐색하는 방식 중 너비 우선 탐색(BFS)에 대해 알아보겠습니다. BFS : Breadth First Search1. 그래프를 탐색하는 목적일반적으로 그래프의 탐색은 특정 목적지까지의 최단 경로를 구하거나 그래프의 전체적인 구조를 ..

들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한 알고리즘 문제를 해결할 수 있게 됩니다. 이번 포스트에선 그래프가 무엇인지, 그래프는 어떤 방식으로 표현되는지, 그래프는 어떤 유형이 있는지, 마지막으로 그래프를 탐색하는 알고리즘에 대해 다뤄보려고 합니다. 이론 위주로 다루기 때문에 특정 언어에 국한되지 않습니다. 그래프 이론: Graph Theory1. 그래프란 그래프는 정점과 간선으로 이루어진 자료구조입니다. 쉽게 말하면 점과 다른 두 점을 서로 연결하는 선으로 이루어진 도형입니다. 2. 그래프의 특징그래프는 비선형적 구조입니다. 따라서 현실 세계의 다양한..

들어가며플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘입니다. 3중 for문을 사용해서 전체 경로에 대해 지나칠 수 있는 노드를 점차 확장하며 가장 적은 비용의 경로를 찾아냅니다. 1번 노드 혹은 마지막 노드부터 순차적으로 확장하는 다이나믹 프로그래밍의 일종입니다.플로이드 워셜 알고리즘은 구현은 쉽지만 처음 접한다면 어려울 수 있으므로 그래프, 인접 행렬, DP(Bottom Up의 Tabulatoin)의 개념을 미리 숙지하고 보면 더 좋습니다. Floyd-Warshall 알고리즘1. 개요플로이드 워셜 알고리즘은 1962년 로버트 플로이드가 현재 사용되는 형태로 발표한 알고리즘으로 플로이드 알고리즘, 로이-워셜 알고리즘 등의 이름으로도 불립니다.플로..

들어가며문자열 관련 알고리즘에는 일반적으로 검색이나 비교&정렬과 관련된 것이 많습니다. 대표적으로 KMP, Boyer-Moore, Rabin-Karp 등이 있습니다. 이번에 소개할 알고리즘은 패턴 매칭의 Z 알고리즘인데 문자열을 검색하기 좋은 알고리즘입니다. 이번 글에선 간간히 KMP 알고리즘도 언급되므로 원활한 이해를 위해선 아래의 KMP 알고리즘도 읽어보시는 것을 추천합니다. [Algorithm] KMP 알고리즘 with JAVA들어가며긴 글에서 주어진 패턴의 문자열을 검색할 때 가장 구현이 쉬운 방식은 text와 pattern이 주어졌을 때 인덱스를 각각 비교하는 방식(=브루트 포스)입니다. 길이 N인 text를 길이 M만큼의 patterjundyu.tistory.com  Z - AlgorithmZ..

들어가며프로그래밍 언어로 피보나치 수를 구하는 방법은 크게 3가지 있습니다. 재귀와 동적 프로그래밍을 통해 피보나치 수를 구하는 것은 우리가 익히 알고 있습니다. 재귀 방식을 사용하면 하나의 호출이 2개의 호출을 발생시키므로 시간 복잡도가 O(2^n)으로 높은 시간복잡도를 요구합니다. 하지만, 동적 프로그래밍 방식(이하 DP)으로 메모이제이션을 사용한다면 시간 복잡도 O(n)으로 획기적으로 시간을 줄일 수 있습니다. 재귀 방식에선 일반적으로 30~40번째 피보나치 수를 구할 수 있고, DP 방식에선 시간 복잡도에 따라 100만에서 1000만까지 가능하지만 long의 범위를 한참 벗어나고, 메모리 초과가 발생하기 때문에 현실적으로는 BigInteger 타입으로 10만번째 피보나치 수까지 구할 수 있습니다...

들어가며최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고리즘입니다. 이번 글에서는 CCW의 원리와 구현 방법, 그리고 더 나아가 활용방법까지 JAVA 언어와 함께 알아보겠습니다. CCW : Counter Clock Wise좌표평면에 세 개의 점이 주어진 경우 점을 순차적으로 이었을 때 세 점을 이은 선이 시계방향인지 반시계방향인지, 일직선인지 판별하는 알고리즘입니다.1번 이미지부터 순서대로 반시계 방향, 시계 방향, 일직선인 경우입니다. 사람의 눈으로 세 점의 방향 관계를 파악하는 것은 아주 쉽지만 프로그래밍 언어를 통해 세 점의 좌표를 받고 판별하는 로직을 구현하는 것은 ..