jundyu 님의 블로그

들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한 알고리즘 문제를 해결할 수 있게 됩니다. 이번 포스트에선 그래프가 무엇인지, 그래프는 어떤 방식으로 표현되는지, 그래프는 어떤 유형이 있는지, 마지막으로 그래프를 탐색하는 알고리즘에 대해 다뤄보려고 합니다. 이론 위주로 다루기 때문에 특정 언어에 국한되지 않습니다. 그래프 이론: 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번 이미지부터 순서대로 반시계 방향, 시계 방향, 일직선인 경우입니다. 사람의 눈으로 세 점의 방향 관계를 파악하는 것은 아주 쉽지만 프로그래밍 언어를 통해 세 점의 좌표를 받고 판별하는 로직을 구현하는 것은 ..

들어가며긴 글에서 주어진 패턴의 문자열을 검색할 때 가장 구현이 쉬운 방식은 text와 pattern이 주어졌을 때 인덱스를 각각 비교하는 방식(=브루트 포스)입니다. 길이 N인 text를 길이 M만큼의 pattern과 비교하기 때문에 시간 복잡도는 O(N*M) 입니다. 이런 방식은 text의 길이가 10만이고 pattern의 길이가 1000인 경우 시간 복잡도는 1억으로 급격히 커지는 것을 알 수 있습니다. 이런 시간복잡도 문제를 해결하기 위해 만들어진 알고리즘은 대표적으로 KMP와 Rabin-Karp가 있습니다. KMP는 단지 비교 횟수를 줄임으로써 시간복잡도 문제를 개선했고, Rabin-Karp는 해시를 이용해서 일치하는 pattern을 찾는 일종의 Rolling-Hash 방식입니다. 이번 글에서는..