언제 사용하는가? 이전 포스팅에서 다루었듯 최단거리 혹은 최소비용을 구하는것에 적합한 알고리즘은 BFS, 데이크스트라 알고리즘 등이 있다. 먼저 둘의 차이는 데이크스트라 알고리즘 포스팅에서 다루었으니 넘어가도록 하고 이번에 다뤄볼 플로이드 와샬 알고리즘과 데이크스트라 알고리즘의 차이부터 짚고 넘어가고자 한다. 간단히 말해서 모든 정점에서 하나의 정점으로 가는 최단거리를 구하고 싶을땐, 데이크 스트라 모든 정점에서 모든 정점으로 가는 최단거리를 구하고 싶을 땐 플로이드 와샬 알고리즘을 사용한다. 자세히 들어가자면, 데이크스트라 알고리즘은 그때 그때 마다 힙에서 최소비용에 해당하는 정점 하나씩 꺼내 비교후 갱신하는 방식이지만 플로이드 와샬은 거쳐하는 모든 정점을 확인해 갱신하는 방식으로 동작한다. 어떻게 사..
이번 포스팅에서는 양의간선을 갖는 최단거리, 최소비용을 찾을때 사용하는 데이크스트라 알고리즘을 다뤄보도록하겠다. 언제 사용되는가? 최단거리을 탐색하는 대표적인 알고리즘을 꼽으라면 먼저 BFS를 언급할수 있겠다. 이때 BFS는 간선의 가중치가 모두 동일한 상황에서 사용하기 적합한데 이때 가중치가 모두 다른 상황이라면 BFS 보다는 데이크스트라 알고리즘을 사용하는것이 해당 문제상황을 해결하는것에 더 도움이 될것이다. 즉 간선의 가중치가 다른 상황에서 최단거리를 찾고자 할때 데이크스트라 알고리즘을 사용한다. 그래서 실사용되는 부분으로는 네트워크 라우팅 프로토콜, 빠른 길찾기(네비게이션), 소셜네트워크 분석(친구찾기) 등 활용도가 높은 알고리즘이다. 어떻게? 데이크스트라 알고리즘은 탐색을 시작할 정점에서 모든 ..
이번 포스팅에서는 문자열 데이터를 다루기에 최적화된 자료구조중 하나인 트라이에 대해 다뤄보고자 한다. 먼저 위키백과를 통해 기본 정의부터 알아보도록 하겠다. https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85) 트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. "A", "to", "tea", "ted", "ten", "i", "in", "inn"를 키로 둔 트라이. 이 예제에는 모든 자식 노드가 알파벳 순으로 왼쪽에서 오른쪽으로 정렬되어 있지는 않다. (루트 노드 ko.wikipedia.org 정의를 보면 탐색트리의 일종으로 동적집합이나 연관배열을 저장하는데 사용되..
알고리즘 문제를 풀다보면 소수를 다루는 문제가 종종 보인다. 그럴때 사용하기 좋은게 바로 에라토스테네스의 체인데, 먼저 위키에 잘나와있으니 한번 읽어 보고 오도록 하자. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수 ko.wikipedia.org 잘 설명 되어있는 알고리즘은 간단하다. 소수를 구하고자하는 구간의 모든..
이번 포스팅에서는 조금 어렵지만 이해하고 사용한다면 정말 강력한 무기가 될 수 있는 힙에 대해 다뤄보도록 하겠다. 먼저 위키백과를 통한 정의를 살펴보고 오겠다. https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 ko.wikipedia.org 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree..