jundyu 님의 블로그

들어가며이번 글은 최소 신장 트리를 구하는 알고리즘 중 하나인 Prim에 대해 설명하는 글입니다. 글을 읽기 전에 아래의 링크에서 그래프 이론 및 그래프 탐색 글을 읽어보는 것을 추천합니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Prim 알고리즘을 설명하기 전에 최소 신장 트리에 대해 간략하게 설명하면서 시작하겠습니다. 최소 신장 트리 (MST : Minimum Spanning Tree)1. 정의우선 트리(Tree)의 사전적 정의는 사이클이 없고, 모든 정점이 연결된 무방..

들어가며제목에서 알 수 있듯이 이번 글은 위상 정렬을 위한 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년 로버트 플로이드가 현재 사용되는 형태로 발표한 알고리즘으로 플로이드 알고리즘, 로이-워셜 알고리즘 등의 이름으로도 불립니다.플로..

저번 3월 8일 SQLD 시험을 치르고 이틀 전인 4월 4일에 가채점 결과가 나왔습니다.  비전공자로서 82점을 받게 되었는데 시험을 준비할 때의 제 베이스와 시험 준비 방법이 다음 SQLD 시험을 준비하는 분들에게 조금이나마 도움이 되길 바라는 마음으로 글을 쓰게 되었습니다. 이미 시험을 친지 3주가 지나서 문제 유형은 구체적으로 기억나지 않습니다. 대신 어떤 식으로 준비했는 지 자세히 적어보려합니다! 1. 베이스 우선 저는 비전공자입니다. 하지만 작년 8월 쯤에 약 일주일간 MySQL이라는 RDBMS를 통해 처음 SQL 쿼리문 작성을 배웠습니다. 그리고 웹 앱 프로젝트에서 백엔드를 맡아 처음으로 ERD 설계를 경험했습니다. 그러고 시간이 쭉 흘러서 12월에 SQLD 자격증을 따야겠다는 생각을 했고, ..

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