개발하는 고라니

그래프가 주어졌을 때 하나의 시작 정점에서 다른 모든 정점들로 가는 최단 경로를 구하는 알고리즘은 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford)가 있다. 만약 그래프에 존재하는 모든 정점 사이의 최단 경로를 구하려면 다익스트라 알고리즘을 정점의 수(n) 만큼 반복 실행하면 된다. 즉 구해야할 최단 경로가 총 n^2개다. (자기 자신으로의 경로 포함) 하지만 이보다 간단한 방법으로 모든 정점 쌍 사이의 최단 경로를 구하는 방법인 플로이드-와샬(Floyd-Warshall) 알고리즘을 알아보고자 한다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했다면, 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 또한 이 알고리즘은 동적..

비트 마스킹은 알고리즘이라기 보다는 비트의 연산을 이용한 테크닉이라고 볼 수 있다. &, |, ^등의 비트 연산을 활용하여 정수의 이진 비트를 처리하는 작업이다. 그렇게 많이 사용될 일은 없겠으나, 가끔 사용해야 할 때 비트 마스킹을 사용하면 훨씬 빠르고 간단하게 코드를 구현할 수 있다. 비트 마스킹의 장점은 다음과 같다. 메모리를 적게 사용할 수 있다 프로그램이 빠르게 동작 소스코드가 직관적이게 된다 가령 미로를 탈출하는 시뮬레이션에서 코드를 구현할 때, 필요한 열쇠가 6개(a, b, c, d, e, f)라고 하자. 현재 이 중에 어떤 열쇠를 갖고 있는지를 어떻게 저장할 것이며, 특정한 열쇠가 필요한 상황에서 그 열쇠가 있는지 어떻게 판단할 것인가. 방법은 아주 다양하다. List, Set 같은 Col..

[알고리즘] 다익스트라(Dijkstra) 알고리즘 최단 경로 최단 경로 문제에서 입력 그래프의 유형은 크게 두 가지이다. 모든 간선 가중치가 음이 아닌 경우 음의 가중치가 존재하는 경우 음의 가중치를 허용하지 않는 경우 다익스트라(Dijkstra) dev-gorany.tistory.com 이전 포스팅의 다익스트라 알고리즘을 구현한 코드는 O(N^2)의 시간 복잡도를 갖는다. 모든 정점을 한 번씩 순회하는 N번의 loop와 그 안에서 distance[i]의 가장 작은 값의 인덱스를 찾는 N번의 loop가 호출되었다. 단순히 다익스트라 알고리즘을 구현하고 사용하는데에는 코드도 직관적이고 다른 자료구조도 안쓰여서 쉽게 쓸 수 있으나 문제를 풀거나, 서비스에 적용해야 할 때는 문제가 될 여지가 충분하다. 이를 ..

최단 경로 최단 경로 문제에서 입력 그래프의 유형은 크게 두 가지이다. 모든 간선 가중치가 음이 아닌 경우 음의 가중치가 존재하는 경우 음의 가중치를 허용하지 않는 경우 다익스트라(Dijkstra) 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치를 허용하는 경우 벨만-포드 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치는 허용하지만 가중치 합이 음수인 사이클은 절대 허용하지 않는다. 음의 사이클이 있으면 해당 사이클을 몇번이고 돌아 경로의 가중치 합을 무한정 낮출 수 있기 때문에 최단 경로 문제 자체가 성립하지 않는다. Dijkstra 알고리즘 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구한다. 다만 이 때 음의 가중치를 갖는 간선은 허용하지 않는다. 임의의 두 정점 ..

크루스칼(Kruskal) 알고리즘 이 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 사이클(Cycle)을 만들지 않는 범위에서 최소 비용 간선(Edge)을 하나씩 더해가며 최소 신장 트리(Minimum Spanning Tree, MST)를 만든다. 실제로 여러 도시가 있을 때 각 도시를 도로로 연결하는데 최소 비용을 들여 연결할 때 사용될 수 있는 알고리즘이다. n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요하므로, 처음에 간선이 없는 상태에서 시작하여 n-1개의 간선을 더하는 것이다. 크루스칼 알고리즘은 프림 알고리즘 처럼 하나의 트리를 키워나가는 방식이 아니고, 임의의 시점에 최소 비용의 간선을 더하므로 여러 개의 트리가 산재하게 된다. 크루스칼은 시작점을 정..

정렬은 n개의 원소를 순서대로 배열하는 것이다. 원소는 숫자, 문자, 문자열, 날짜 등 다양한 것이 될 수 있다. 정렬은 그 자체로도 매우 자주 사용되지만 알고리즘의 설계와 분석, 생각하는 방법 등을 훈련하기에도 더없이 적합한 주제인 것 같다. 이번 포스팅에서는 짧고 핵심만 간추려서 간단하고 기본적인 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬을 Java로 구현해보고 각 정렬이 완료되는데 걸리는 시간도 보도록 한다. 선택 정렬 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나이다. n개의 원소를갖는 배열 A[a[1], a[2], ..., a[n]]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 맞바꾼다. 그러면 현재 A[n]에는 이 배열에서 가장 큰 원소가 있으므로 더..

그래프에서 모든 정점을 방문하는 방법 중 하나인 너비 우선 탐색(Breadth-First Search, BFS)에 대해 공부하고자 한다. 그래프의 모든 정점을 방문하는 방법인 DFS와 BFS는 간단하지만 그래프의 알고리즘에서 핵심적인 위치를 차지한다. 따라서 반드시 알아야 할 알고리즘들 중 하나이며, 코딩테스트에도 빈번히 출제되는 유형이다. 루트를 시작으로 탐색을 한다면 BFS는 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트의 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 또 다음으로 루트에서 세 개의 간선을 거쳐서 도달할 수 있는 정점들 순으로 루트에서 거리 순으로 방문한다. (거리에 따라 단계별로 탐색한다.) BFS는 두 노드 사이의 최단 경로(멀리 떨어진 ..

그래프에서 모든 정점을 방문하는 방법 중 하나인 깊이 우선 탐색(Depth-First Search, DFS)에 대해 공부하고자 한다. 그래프의 모든 정점을 방문하는 DFS와 BFS는 간단하지만 그래프의 알고리즘에서 핵심적인 위치를 차지한다. 따라서 반드시 알아야 할 알고리즘들 중 하나이며, 코딩테스트에도 빈번히 출제되는 유형이다. 이와 더불어 너비 우선 탐색(Breadth-First Search, BFS)도 있다. 이는 다음에 공부해보도록 한다. DFS는 BFS에 비해 구현이 간단하나, 검색 자체 속도는 BFS보다 느린 편이다. DFS는 루트(Root)의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳 까지 내려간다. 더 이상 내려갈 수 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다..