공부 기록장

0/1 knapsack, 배낭채우기 문제는 DP에서 유명한 문제 중 하나이다. 1) N개의 물건에 각각 무게 정보와 가치 정보가 주어지고 2) W의 무게까지 담을 수 있는 가방이 있을 때, 3) 가방의 가치를 가장 높게 만들어 줄 물건들을 담아야 한다. 보통은 도둑이 물건을 훔쳐갈 때, 들고갈 수 있는 무게는 제한적이니 그런 것들을 이용해서 알고리즘 문제가 나오더라. 하지만 오늘은 특정 문제를 포스팅 하는게 아니라, 알고리즘 자체를 올려보려고 한다. 이 알고리즘의 로직은 1) 첫 물건부터 끝 물건까지, 가방의 무게를 1부터 W까지 모두 고려해서 2) 물건의 무게가 현재 가방의 무게보다 작거나, 같으면 넣어본다. 2-1) 이번 아이템을 넣지 않았을 때와, 넣었을 때를 비교해서 더 큰 값을 저장해주는 방식이..

이 알고리즘은 Floyd-Warshall 알고리즘이라고 불리기도 하고, 줄여서 floyd 알고리즘이라고 불리기도 한다. 이 알고리즘도 다익스트라와 비슷하게, 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로를 찾는 것이다. 하지만 다익스트라와는 다르게 가중치가 음의 값을 가지고 있어도 되고, 모든 쌍의 최단경로를 구하는 알고리즘이기 때문에 계산이 끝난 후에는 내 마음대로 출발점과 끝나는 점을 잡아도 최소 거리를 알려준다. 이 알고리즘은 점화식을 통해 계산을 하는데, 간단하게 생각해야 이해하기 쉽다. 1) 출발지에서 경유지를 거쳐, 도착지 까지 간다. 2) 출발지에서 도착지로 바로 가는 경우와 출발지에서 경유지를 거쳐 도착지로 가는 경우 중 더 빠른 길을 담아둔다..

다익스트라 알고리즘은 DP를 활용한 최단경로 탐색 알고리즘이다. 흔히 인공위성 GPS SW등에서 많이 사용되며, 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하지만 그 간선중에 음수가 있어서는 안된다. 다익스트라 알고리즘이 DP인 이유는 여러개의 최단거리를 모아서 최종 최단거리를 만들기 때문이다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단거리들의 정보를 활용해서 구한다. 다익스트라 알고리즘을 구현하기 위해 1) 시작점, 끝점(start, end) 2) 간선의 정보가 담겨있는 배열(adjMatrix) 3) 최단거리가 담겨있는 배열(distance) 이 필요하다. 다익스트라 알고리즘은 1) 하나의 기준점 잡기 2) 기준점으로부터 가장 가까운 점 찾아서 그리로 이동 3) ..

PRIM 알고리즘 또한 크루스칼과 비슷하게 최소신장트리 알고리즘 중 하나이다. 프림 알고리즘은 하나의 정점을 시작점으로 하여 cycle을 생성하지 않는 범위 내에서, 최소 가중치를 가지는 정점을 하나씩 포함하여 N-1개의 간선까지 확대하는 알고리즘이다. 1) 임의의 정점을 시작 정점으로 택해서 최소 신장트리의 루트 노드로 삽입하기. 2) 최소 신장트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사하여 이 가중치가 가장 작은 간선을 골라 최소 신장트리에 삽입 3) 모든 점이 다 연결될 때 까지 반복. public class MST_PRIM { public static void main(String[] args) throws IOException{ BufferedRe..

크루스칼 알고리즘은 대표적인 최소신장트리 알고리즘 중 하나이다. 간선을 하나씩 선택해서 MST(최소신장트리)를 찾는 알고리즘이다. 1) 최초로 모든 간선을 가중치에 따라 오름차순으로 정렬한 뒤, 2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. 이때, 사이클이 존재하면 다음으로 가중치가 낮은 간선을 택한다. 3) 간선이 모두 선택될 때 까지 2를 반복한다. 지난번 포스팅에서 다뤘던 Union-Find 알고리즘을 응용해서 만드는데, 새로운 자료형을 선언해 주는 것이 편하기 때문에 Edge라는 자료형을 만들어주었다. 간선이 어디에서 와서 어디로 가는지, 가중치가 얼마인지에 대한 정보가 담겨있다. static class Edge implements Comparable{ int from,to,we..

Union-Find 알고리즘은 최소신장트리 알고리즘에 많이 쓰이지만 사실은 서로소 집합을 찾는 알고리즘이다. 서로소 집합은 서로 중복 포함된 원소가 없는 집합들, 즉 교집합이 없는 집합이다. 따라서 집합에 속한 하나의 특정 멤버인 대표자를 이용해 각 집합들을 구분한다. 서로소 집합을 표현하는 방법에는 대표적으로 연결 리스트와 트리가 있다. 연결 리스트 - 같은 집합의 원소들은 하나의 연결리스트로 관리하고, 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. - 즉, 연결리스트의 헤드가 대표자가 되는 것이다. - 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다. 트리 - 트리도 연결리스트와 비슷하다. 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다. 이런 서로소 집합들을 서로 연결 ..

Greedy 알고리즘을 사용하면 눈 앞에 보이는 최적의 해답을 찾아서 이동하기 때문에 빠르게 답을 구해낼 수 있지만, 그리디 알고리즘만으로는 해결하지 못하는 경우가 있다. 그럴때는 완전탐색 기법을 사용해서 해결한다. 완전 탐색 혹은 완전 검색이라고 불리는 이 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. 이 방법은 Brute-force 혹은 generate-and-test 기법으로도 불리는데 모든 경우의 수를 테스트 한 후 최종 해법을 도출해낸다. 장/단점으로는 모든 경우의 수를 생성하고 테스트하기 때문에 수행속도가 느리다고 오래걸린다는 단점이 있다. 하지만 모든 경우의 수를 다 검색해 보기 때문에 해답을 찾아내지 못할 확률이 적다. 느리긴 하지만, 크기 제한이 ..