개발자 모드

오늘은 DP와 분할정복에 대해서 알아보겠습니다. 또한 DP와 분할정복이 언뜻 보면 비슷한 것으로 생각할 수도 있는데, 이의 차이점을 조금 명확하게 확인해봅시다. 분할정복 분할정복이란 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘입니다. 분할정복은 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하고 이들의 해를 취합하여 원래 문제의 해를 얻습니다. 즉, 하나의 문제를 더 이상 분할할 수 없는 부분 문제로 쪼개고, 해당 부분 문제에 대한 부분 해를 구하여 최종 문제에 대한 해를 구하는 방식이죠. 아래의 그림이 분할 정복을 잘 설명해주고 있습니다. DP(Dynamic Programming) 동적계획 알고리즘 즉, DP는 입력 크기가 작은 부분 문제들을 해결한 후에, 그 해들을 이용하여 보다..

이전 글에서 그리디 알고리즘에 대한 개념과 그에 대한 대표적인 예시를 다뤘습니다. 오늘은 그에 이어서 허프만 압축에 대해서 다뤄보겠습니다. 허프만 압축 우리는 파일을 작성한 후에 저장하거나 전송할 때 크기를 압축하고, 필요할 떄 원래의 파일로 변환할 수 있으면 메모리 공간을 효율적으로 사용할 수 있으며 파일 전송 시간을 단축할 수 있을 것입니다. 이러한 파일의 크기를 줄이는 방법을 파일 압축이라고 하며 파일 압축의 방법 중 한 가지인 허프만 압축을 소개합니다. 허프만 압축은 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 방식으로 진행됩니다. 허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성이 존재합니다. 더보기 접두부 특성이란..

오늘은 분할 정복 알고리즘의 대표적인 문제 중 하나인 최근접 점의 쌍 찾기에 대해서 알아보겠습니다. 최근접 점의 쌍 찾기 위와 같은 점들이 있다고 합시다. 여기서 가장 가까운 점의 쌍은 어떤 점일까요?? 물론 이 그림에서는 직관적으로 보일 수 있지만, 이러한 점이 많거나 직관적으로 확인하기 어려울 때 말이죠. 우리는 이러한 문제를 알고리즘으로 해결하기 위해서 분할 정복을 사용합니다. 간단한 방법 사실 간단한 방법으로는 모든 점의 쌍에 대한 거리를 구한 후에, 가장 작은 거리를 구하면 됩니다. 하지만 그렇게 되면 시간 복잡도가 O(n^2)이 되어서, 그렇게 좋은 알고리즘 같아 보이진 않습니다. 그래서 우리는 분할 정복을 이용해 시간 복잡도를 낮춰보겠습니다. 분할 정복을 이용한 알고리즘 가장 먼저는 n개의 ..

오늘은 선택 알고리즘에 대해서 알아봅시다. 선택 문제 선택 알고리즘을 알아보기 전에, 이 알고리즘이 어떻게 나오게 되었는지를 알아봅시다. 그러기 위해서 선택 문제를 우선 설명해야할 것 같은데, 선택 문제란 정렬되지 않은 길이가 n인 수열에서 k번째로 작은 숫자를 찾는 문제를 의미합니다. 통상 이 문제를 해결하기 위한 단순한 알고리즘은 아래의 두가지 일 것입니다. 1. 주어진 수열에서 가장 작은 수를 찾는 과정을 k번 반복했을 때, k번째 작은 수를 찾을 수 있습니다. 선택된 가장 작은 수는 해당 수열에서 삭제하는 방식으로 말이죠. 이렇게 된다면 시간복잡도는 아마 O(kn)이 될 것입니다. 2. 숫자들을 정렬한 이후에, k번째에 위치한 수가 k번째로 작은 수가 될 것입니다. 이는 정렬 알고리즘의 시간복잡도..

오늘은 그리디 알고리즘에 대해서 알아보겠습니다. 그리디 알고리즘 그리디 알고리즘, 욕심쟁이 알고리즘이라고 불리는 이 방식은 문제를 해결하기 위핸 문제해결 패러다임 중 하나입니다. 매순간마다 직면한 상황에서 가장 좋은 선택지를 선택하는 알고리즘이죠. 그리디 알고리즘에 속하는 많은 알고리즘이 있습니다. 동전 거스름돈 문제 최소 신장 트리(MST) 구하기 최단 경로 찾기 부분 배낭 문제 집합 커버 문제 작업 스케쥴링 허프만 압축 오늘은 이 중에서 집합 커버 문제까지 다뤄보겠습니다. 동전 거스름돈 문제 음료수 자판기가 있다고 해봅시다. 각 자판기는 현금을 받고 음료수를 줍니다. 거스름돈이 있다면 거스름돈을 어떻게 줄지에 대해서 결정해야합니다. 이 때, 그리디 알고리즘이 쓰입니다. 대한민국 기준으로 동전은 500..

오늘은 그래프의 최단 경로를 찾는 알고리즘 중 마지막 Floyd-Warshall 알고리즘에 대해서 알아보겠습니다. Floyd-Warshall 알고리즘 Floyd-Warshall 알고리즘은 기존 Dijkstra와 Bellman-Ford의 단점을 모두 보완한 알고리즘입니다. 총 n번 반복하는동안 i(i=0, 1, ..., n-1)번째 정점을 경유하여 가는 경우들을 갱신하는 방법을 이용합니다. Floyd-Warshall은 DP(Dynamic Programming)에 속합니다. 결국 Floyd-Warshall 알고리즘을 이용하여 결과를 도출할 때, 각 정점 사이의 거리를 이용하여 결과를 도출하기 때문입니다. 예제를 통해 Floyd-Warshall 알고리즘의 과정을 살펴봅시다. 위와 같은 그래프와 우측에는 D라는..

오늘은 최단 경로를 찾는 알고리즘 중 Dijkstra 알고리즘의 단점을 보완한 Bellman-Ford 알고리즘에 대해서 알아보겠습니다. Dijkstra 알고리즘의 단점 이전 포스팅에서 말한 Dijkstra 알고리즘의 단점을 찾아보셨나요?? 여기서 간단하게 다뤄봅시다. 0번 정점을 우선 방문했습니다. 그리고 1번 정점과 2번 정점에 대해서 값을 갱신해줍니다. 이제 1번 노드를 선택할 것입니다. 가중치도 같이 갱신해줍시다. 이제 2번 정점에 갈 차례입니다!! 2번 정점에서 값을 갱신해봅시다. 이렇게 모든 노드를 방문하고 알고리즘을 종료합니다. 이제 0번 노드로부터 각 노드의 최단거리를 알았습니다. 0에서 2로 가는 최단거리는 1 0에서 1로 가는 최단거리는 -2 뭔가 이상하지 않나요?? 사실 0에서 1로 가..

오늘은 하나의 그래프 내에 정점 A에서 정점 B까지 가는 최단 경로를 구하는 알고리즘 중 하나인 Dijkstra 알고리즘에 대해서 알아보겠스빈다. Dijkstra 알고리즘이란? 앞서 말씀드린 것처럼, Dijkstra 알고리즘은 그래프 내에서 어떤 정점으로부터 다른 정점으로 갈 때의 최단 경로를 구하는 알고리즘입니다. Dijkstra 알고리즘은 Dynamic Programming에 속하기도 하고 그리디 알고리즘에 속하기도 합니다. 더보기 Dynamic Programming(동적 계획법) DP는 하나의 큰 문제를 작은 문제로 나누어서, 작은 문제들에 대한 해답을 이용해 큰 문제를 해결하는 하나의 문제해결 패러다임입니다. 그리디 알고리즘을 이용해 A에서 B로가는 경로를 구했다고 해봅시다. 그러한 경로가 A ..

오늘은 마지막으로 MST를 찾는 알고리즘 중 Sollin 알고리즘에 대해서 알아보겠습니다. Sollin 알고리즘이란? Sollin 알고리즘도 Kruskal, Prim 알고리즘과 같이 하나의 그래프에서 MST를 찾는 알고리즘입니다. Sollin은 각 정점을 하나의 트리로 간주하고, 각 트리 사이의 간선 중 가장 작은 간선을 선택하여 두 개의 트리를 하나로 이어주는 방식을 통하여 MST를 구성하는 방식입니다. 순차적으로 진행하는 Kruskal과 Prim과는 달리 한번에 진행하여 최악의 상황이 아닌 일반적인 상황에서는 굉장히 빠른 속도로 완료할 수 있다는 장점이 있습니다. 그럼 이제 그림을 통해서 확인해봅시다. 이런 그래프가 있습니다. Kruskal과 Prim에서 다뤘던 그래프와 동일합니다. 여기서 우리는 각..

오늘은 MST를 만드는 알고리즘 중 Prim 알고리즘에 대해서 알아보겠습니다. Prim 알고리즘이란? Prim 알고리즘은 MST(Minimun Spanning Tree)를 찾는 알고리즘 중 하나입니다. 임의의 시작점에서 시작하여 해당 점과 가장 가까운 정점을 추가하여 하나의 트리를 만들고, 해당 트리에서 가장 가까운 정점을 하나씩 추가하여 MST를 만드는 알고리즘입니다. 아래의 그림으로 차근차근 진행해봅시다. Kruskal의 동일한 예제를 통해 확인해봅시다. 가장 먼저 모든 정점 간의 연결이 없다고 생각하고 진행합니다. 거기서 임의의 한 정점을 뽑을건데, 음.. 저는 5번 정점을 시작으로 진행해보겠습니다. 5번 정점과 연결된 가장 가까운 정점은 거리가 2인 3번 노드입니다. 3번 노드와 하나의 트리를 이..