minkylee

문제크기가 N X N 인 도시가 있고 집과 치킨집이 주어진다. M개의 치킨집을 남기고 모두 폐업시키려고 할 때 도시의 치킨 거리의 최소값을 구해라치킨거리 : 집과 가장 가까운 치킨집 사이의 거리, 각각의 집은 치킨 거리를 가지고 있다.도시의 치킨 거리 : 모든 집의 치킨 거리의 합이다.예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.0 2 0 1 01 0 1 0 00 0 0 0 00 0 0 1 10 0 0 1 20은 빈 칸, 1은 집, 2는 치킨집이다.(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.(5, 4)에 있는 집과 ..

문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다LCS LCS는 DP 알고리즘의 대표적인 문제이다.사실 브루트포스로도 풀 수 있는데 부분 문자열을 모두 구하고 비교해야 하므로 시간복잡도가 $2^n$ 인 무시무시한 숫자가 나온다. 두 개의 문자열을 A, B라고 하자,현재 보고있는 문자가 A[i] 와 B[j] 일 때, A[i]와 B[j] 가 같을 경우 최장 공통 부분 수열은 A[i - 1] B[j - 1]까지의 최장공통 부분 수열에 현재 문자를 더한 것과 같다. ABC 와 BC라는 실제 문자열을 가지고 생각해보자 현재..

문제 알파벳 소문자로 구성된 길이 1 이상의 두 문자열 X, Y가 있다. 이 문자열들의 임의의 위치에 공백을 삽입하여 두 문자열의 길이를 같게 만든 다음, 앞에서부터 한 글자씩 살펴보면서, 같은 위치에 있는 두 문자 X[i], Y[i]에 대해서 다음과 같이 점수를 계산한다. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다. 입력 첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자..

그리디 알고리즘 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자. 예를 들어 5개의 도시를 모두 한 번씩만 거쳐서 여행한다고 가정하자, 기름값을 아끼기 위해 가장 짧은 경로를 선택해야한다고 하면, 이 문제를 해결하기 위해 여러 방법을 사용할 수 있다. 모든 경로를 검사하는 브루트 포스를 이용해 답을 구하거나, 외판원 순회같은 복잡한 전략을 쓸 수도 있고 " 지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다 " 는 방법, 즉 그리디 알고리즘을 쓸 수도 있다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 전혀 없다. 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될..

분할 정복이란? 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음, 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합 정렬이 있다. 그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다. 분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. 마스터 정리 점화식을 해결하기 위한 일반적인 방법 중 하나로, 분할 정복 알고리즘에서 주로 사용된다. 점화식이 특정한 ..

Searching list : 하나 이상의 필드로 된 레코드의 집합 키 (key) : 레코드를 구분하기 위해서 사용되는 필드 순차 탐색(Sequential Search) 레코드 리스트를 왼편에서 오른편 또는 오른편에서 왼편으로 레코드를 검사하는 것 int SeqSearch(int a[], const int n, const int key) { for (int i = 1; i n) return 0; return i; } 이원 탐색 (Binary Search) n개의 레코드를 가진 리스트를 탐색하기 위해 O(logn) 시간이 걸림 (순차탐색보다 빠르다.) 순차나 이원 탐색 방법은 실제로 사람이 사용하는 탐색 방법과 대응되지 않는다. 보간법(interpolation)에 의한 탐색 리스트가 정렬되었을 때만 사용 ..

어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾는다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? 만약 도시가 20개라고 할 때, 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 20!이다. 20!=2,432,902,008,176,640,000 이기 때문에 시간복잡도가 어마무시하다... 정의 주어진 완전 그래프 G=(v, E)가 연결되어 있고, 가중치가 있는 완전한 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을..

조합 최적화 문제의 일종, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 분할 가능한 배낭 문제 아이템들을 분할해서 담는 것이 가능하다 -> 단위 무게당 가치 순으로 높은 것들부터 담는 그리디 알고리즘 사용하면 됨 0-1 배낭문제 아이템들을 분할해서 담는 것이 불가능 그리디 알고리즘으로는 최적해를 찾을 수 없다. 동적 계획법, 백트래킹 등의 조합 최적화 문제의 풀이 방법으로 풀어야 한다. 대표적인 DP 알고리즘 중 하나. DP란, 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다. 작은 부분의 답이 큰 부분의 답이 되고 이 부분들의 답이 전체의 ..