개요 우리가 집합이라는 개념을 생각했을 때 보통 아래의 그림처럼 벤-다이어그램으로 생각을 하곤 한다.▼ 그런데 이런 집합이라면 아래와 같이 배열로 표현할 수 있다.▼ 하지만 두 원소가 같은 집합에 있는지를 판단하라고 하면 약간 곤란해진다. A집합에 있는 1 원소와 B집합에 있는 5 원소가 같은 집합에 있는지를 판단하려면 A집합이나 B집합을 다 확인해야한다. A집합에 5 원소가 있는 지 없는 지, B집합에 1 원소가 있는지 없는 지를 확인해야한다. ▼ 배열로 구현하게 되면 집합의 대표를 알아내기가 힘들어서 같은 원소에 대해서 또 확인하게 되면 같은 연산을 계속 수행해야한다. 심지어는 두 집합이 서로소인것을 알아내어 합한다고 했을 때도, 원소를 옮기는 과정에서의 연산도 적지않게 수행된다. ▼ 이런 집합에 대..

개요 플로이드-와샬 알고리즘은 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 가중치가 음인 그래프는 있지만, 음수 싸이클은 없다. (음수 싸이클이란? 음의 가중치가 더 커서 최단 경로를 계속해서 줄일 수 있는 상태의 간선을 말함.) 벨만-포드와 음의 가중치의 최단 경로를 계산할 수 있다는 점에서 비슷하지만, 플로이드-와샬 알고리즘은 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 즉, 벨만-포드와 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구했다면, 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구한다. 또한 플로이드-와샬 알고리즘은 다이나믹 프로그래밍으로 볼 수도 있다. 알고리즘 알고리즘 분류..

개요 가중치가 있는 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 최단 경로 문제라고 하면 다익스트라와 같은 작업을 수행하고, 심지어는 다익스트라가 더 빠르기까지 하다. 하지만 벨만-포드 알고리즘의 의의는 다익스트라 알고리즘이 처리하지 못하는 음수인 간선을 처리할 수 있다는 것이다. 그래서 음수인 간선이 등장하는 경우에는 벨만-포드 알고리즘을 사용한다. 알고리즘 벨만-포드 알고리즘에서 중요한 부분 벨만-포드 알고리즘에서 가장 중요시 해야할 부분은 음의 싸이클이다. 벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 값이 더 작은 값이 나오면 갱신하는 식으로 진행된다. 그런데 음의 싸이클이 등장하게 되면, 한 번 순회를 돌 때마다 값이 계속 작아져서 무한히 갱신하게 된다. 그래서 우리는 순회 횟수를 V - ..

개요 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 그러나 음의 간선을 포함할 수 없다. 음의 간선을 포함하려면 벨만-포드 알고리즘을 사용해야한다. 하지만 현실에는 음의 간선이 존재할 수 없기도 하고, 그게 아니어도 양의 간선만을 비교하는 상황에서도 다익스트라 알고리즘이 벨만-포드 알고리즘보다 빠르기 때문에 다익스트라 알고리즘을 선호하는 편이다. 알고리즘 알고리즘 분류와 특징 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리가 단일 대상의 거리를 말하는 게 아니라 여러 개의 최단 거리의 합으로 이루어져 있기 때문이다. 거대한 최단 거리가 있다고 생각하..

문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는..

개요 간단하게 말하면, 최소 신장 트리란 신장 트리 중에서 사용된 가중치 합이 최소인 트리를 말한다. 신장 트리란? (Spanning Tree) 신장 트리란, 그래프 내의 모든 정점을 포함하는 트리를 말한다. 스패닝 트리, 신장 트리, Spanning Tree 모두 같은 말이다. 신장 트리는 그래프의 최소 연결 부분 그래프를 말한다. 여기서 최소 연결이라고 하면, 간선의 수가 가장 작은 것을 말한다. n개의 정점을 가지는 그래프의 최소 간선의 수는 n - 1 개이고, n - 1 개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되며 이를 신장 트리라고 부른다. 한 그래프에는 아래 그림처럼 여러 개의 신장 트리가 있을 수 있다. 결국, 최소 신장 트리란 최소 연결된 부분 그래프들 중 간선 가중치의 합이..

개요 그래프는 정점과 간선으로 이루어진 자료구조이다. 정확히는 정적(vertex)간의 관계를 표현하는 조직도라고 볼 수도 있다. 이런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다. 그래프에서 사용하는 용어 정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장된다.(0, 1, 2, 3) 간선(edge) : 링크(arcs)라고도 하며 노드간의 관계를 나타낸다. 인접 정점(adjacent ver..

추후 원본 내용을 수정하여 업로드할 계획입니다...! 이항계수 피보나치 수열 행렬 곱하기 알고리즘 다이나믹 프로그래밍 예제

개요 내용은 추후 추가될 예정입니다...! 더하기 / 곱하기 알고리즘 이진 탐색 합병 정렬 허프만 부호화

개요 트리(tree) 구조는 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 말이 조금 어렵게 되어 있는데, 좀 더 쉽게 말하면 현재 노드를 떠나면 같은 길을 되돌아오는게 아닌 한 현재 노드로 돌아올 수 없다는 것이다. 버스를 탄다고 했을 때, 보통 반대 차선으로 가면 똑같은 버스가 있기 마련인데 가끔 편도로 가는 버스들이 있다. 일단 위의 말이 이해가 안된다면, 트리 구조를 편도로 가는 버스 정도로 이해하고 들어가자.▼ 앞에서 트리에 대한 설명으로 `순환이 없는 연결 그래프`라고 했다. 트리와 그래프와는 별개의 자료구조로 느껴지지만, 트리는 따지고 보면 그래프의 한 종류가 될 수 있다. 다만 그 특수성이 짙은 자료구조로서 그래프와 따..