그리디 알고리즘 그리디 알고리즘이란 눈앞의 이익만 우선 추구하는 알고리즘을 말한다. 예를들어 이진 트리에서 그리디 탐색을 한다고 했을때 트리의 내용을 사전에 알지 못하는 상태에서 루트부터 시작해 왼쪽으로 갈지 오른쪽으로 갈지 매 단계마다 결정해서 가장 큰값을 찾아낸다고 하자 루트의 오른쪽에 60 이 있고 루트의 왼쪽에 15가 있다면 그리디는 눈앞의 이익을 우선하기 때문에 60을 쫒아간다. 하지만 60은 밑에 자식이 없고 15는 밑에 100이라는 자식이 있다면 결국 15로 갔을때 가장 큰값이 나오게된다. 이렇듯 그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우가 있다. 그 예로는 최소 신장 트리를 찾는 프림알고리즘이 있다. 프림 알고리즘은 그래프에서 연결하는 간..

최소 신장 트리 그래프 G=(V,E)의 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것입니다. 임의의 그래프로부터 만들 수 있는 신장 트리는 매우 다양합니다. 너비 우선 트리와 깊이 우선 트리도 신장 트리입니다. 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 합니다. 밑은 최소신장 트리 종류중 하나인 프림 알고리즘입니다. 1. Prim's 알고리즘 Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후, 그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다. 초기 그래프입니다. 모든 정점들의 key 값은 inf가 할당되어 있습니다. 그..

위상 정렬(Topological Sort)이란 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상 정렬(Topological Sort)의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이 러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야 한다. 위상 정렬(Topological Sort)을 이용한 ..

그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 ..

그래프의 개념 그래프는 현상이나 사물을 정점과 간선으로 표현하는 것이다. 정점(Vertex)은 대상이나 개체를 나타내고 간선(Edge)은 이들 간의 관계를 나타낸다. 예를 들어, 사람 간의 친밀도를 나타내고 싶다고 하자. 각 사람을 하나씩의 정점으로 표시한다. 서로 친말한 사람 간에는 간선을 둔다. 그러면 과 같은 그래프가 된다. 각 간선은 간선으로 연결된 두 사람이 친밀함을 나타낸다. 간선은 두 도시를 연결하는 도로의 존재 여부, 두 집안 간의 혼인 여부 등을 나타낼 수 있다. 그림 2는 그림 1을 조금 변형한 것이다. 그림 1이 사람 간의 친물도 존재 여부만 표시하는 데 비해 그림 2는 친밀도의 크기까지 표시한다. 즉, 간선에 가중치를 주어 친밀감의 정도를 보여준다. 이런 가중치는 도시 간의 거리, ..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 ...더보기 3 4 7 10 예제 출력 ...더보기 7 44 274 접근 방법 예시에서 정수가 4일 때와 7일 때의 방법의 수(경우의 수)를 알 수 있다. 그래서 ..