알고리즘 & 자료구조
[Algorithm] 다이나믹 프로그래밍
-다이나믹 프로그래밍이란? 솔직히 여러 블로그나 강의를 봤을 때 드는 예시가 대표적으로 피보나치 수열이라 개념의 이해자체는 쉬웠다. 분할 정복 방식과는 다른 형태로 어떤 큰 문제가 작은 문제로 나눠질 때 또 이 큰 문제가 더 큰 문제의 작은 문제일 때, 동시에 해당 값들에 변화가 없을 때 사용한다고 한다. 즉 피보나치 수열에서 f(3) = f(2) + f(1) 이고, f(4) = f(3) + f(2)이므로 f(3)에서의 f(2)와 f(4)에서의 f(2)는 값이 변하지 않는 중복되는 연산이다. 이러한 중복 연산들을 메모이제이션 기법으로 별도로 기록해두고 (캐시같은 개념) 필요할 때 마다 가져다 사용하면 되는 것이다. 즉, f(3)의 결과를 최초로 실행할 때 저장해 둔 후, f(4)를 구할 때 f(3)을 구..
[Algorithm] 이진트리의 순회 알고리즘(JAVA 구현)
-이진트리란? 트리의 한 종류로써 대표적인 비선형 자료구조의 형태로 1개의 데이터에 대해 0, 1, 2개의 자식 노드를 가지는 트리를 말한다. 이진트리는 일반적으로 탐색을 할 때 많이 사용하는데 그 이유는 특정 데이터를 탐색하고자 할 때 좌, 우로 나뉘어서 탐색하기 때문에 한쪽을 일방적으로 제외할 수 있어 빠른 탐색속도를 가지게 된다. 이진트리의 구현은 일반적으로 배열과 노드를 이용해 구현이 가능하지만, 완전 이진트리를 제외하고는 배열을 사용할 때 많은 메모리 낭비가 발생하기 때문에 노드로 구현하는 것이 좋다. -이진트리의 순회방식 이진트리의 순회방식으로는 3가지가 존재하는데 1)전위순회, 2)중위순회, 3)후위순회이다. 이는 탐색하는 순서에 따라 구분되며 D를 현재의 노드, L을 왼쪽 자식노드,R을 오..
[Algorithm] Kruskal 알고리즘 (JAVA 구현)
- 크루스 칼(Kruskal) 알고리즘이란? 크루스 칼 알고리즘이란, 각 정점을 최소 비용으로 연결시키는 최소 비용 신장 트리를 만드는 대표적인 알고리즘으로 일반적인 그래프에서 각 정점을 연결하는 간선에 비용을 추가해 최소 비용으로 모든 정점을 순환하는 그래프로 만드는 것이다. 크루스칼 알고리즘으로 그래프를 구현할 때 비용은 최소가 되어야 하기 때문에 두 정점과 그 간선에 소모되는 비용을 하나의 클래스로 정의하여 비용을 기준으로 오름차순 정렬을 한 후 가장 적은 비용부터 차례대로 정점을 연결해 나가면 된다. 또한 각 정점에서 사이클이 발생하지 않고, 간선의 수가 정점의 수 -1 개가 연결될 때까지 진행한다. 정점의 수 -1 개의 간선이 연결되면 모든 정점이 연결될 수 있기 때문이다. 이때 사이클의 발생여..
[Algorithm] Union-Find 알고리즘 (JAVA 구현)
-Union Find 알고리즘이란? 서로소 집합 알고리즘과 같은 개념으로 여러 개의 노드가 존재하는 그래프에서 두 노드가 연결되어있는지 판별하는 알고리즘이다. 구현에 필요한 자료구조로는 1) 모든 정점들의 부모 정점을 표현하기 위한 배열이 필요하다. 다음과 같이 6개의 독립적인 노드가 존재한다고 할 때 배열을 이용해서 원소에 해당 노드의 부모 노드를 표시하게 된다. 현재는 모두 독립된 노드이기 때문에 자기 자신을 부모로 삼는다고 할 수 있다. 1 2 3 4 5 6 1 2 3 4 5 6 이와 같은 상태에서 만약 1번 정점과 2번 정점이 연결을 수행하게 되면 두 정점을 합치는 Union작업이 수행되게 되는데, 이 과정을 거치고 나면 아래와 같이 2번 정점의 원소를 부모 정점인 1로 바꿔주게 된다. 이 과정에..
[Algorithm] 깊이 우선 탐색 알고리즘(JAVA 구현)
-깊이 우선 탐색(DFS)이란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. 그중 깊이 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 방문하며 스택(Stack)에 삽입한다. 인접한 정점이 없는 정점까지 2번을 반복한다. 이후 인접한 정점이 없는 경우 다시 스택에서 pop() 후 2~3번을 반복한다. 즉 깊이 우선 탐색의 경우에는 인접한 정점이 없는 정점에 도달할 때까지 인접한 정점을 반복해서 방문하며 Stack에 넣는 작업을 한다. 깊이 우선..
[Algorithm] 너비 우선 탐색 알고리즘(JAVA 구현)
-너비 우선 탐색(BFS)란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. (또한 너비 우선 탐색은 두 정점 사이의 최단 거리를 구하거나 임의의 경로를 구할 때 사용한다고 하는데, 필자도 현재까지는 단순한 구현과 개념의 이해정도 수준에 그치기 때문에 후에 추가적으로 작성할 예정이다.) 그중 너비 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하며 큐(Queue)에 삽입한다. 인접한 정점을 모두 방문했다면, 큐에 삽입했던 정점을 반환..