Brute force Study

그래프 컬러링 문제란?정의: "주어진 그래프 G에서 서로 인접한 정점끼리 같은 색을 가지지 않도록 모든 정점에 색상을 지정해야 한다"그래프 컬러링의 평가는 얼머나 적은 수의 색상을 사용했는가에 의해 결정된다.택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기 문제 등을 그래프로 모델링 한 후 컬러링 문제로 해결할 수 있다.그래프 컬러링에 필요한 최소 개수의 색상 수를 찾는 것은 NP-완전 문제로 알려져 있다.문제를 조금 변경함으로써 시간 복잡도를 크게 변경할 수 있다.그리디 방식이 유용한 근사치를 제공한다.ex) 컴파일러 설계에서 사용 EX) 스도쿠 퍼즐을 그래프 컬러링 문제로 모델링하기각각의 셀(cell)을 그래프 정점으로 표현한다같은 행, 같은 열, 3X3 블록 안에 있는 모든 정점기리 에지를 연결한다생성된 ..

최소 신장 트리 문제란?정의"정점(vertex)의 집합 V와 가중치를 갖는 에지(edge)의 집합 E로 구성된 그래프 G = (V, E)가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오"신장 트리 :  주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리정점의 수가 n 개이면 신장 트리의 간선 수는 n-1 개최소 신장 트리(MST): 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리ex) 상수도관 네트워크, 도로 네트워크 설계Example)지도상에 여덟 개의 마을이 있고, 모든 마을이 서로 연결될 수 있도록 도로를 설계한다고 해보자. 연결된 도로는 사이클을 구성하면 안 된다.연결된 도로의..

작업 스케줄링 문제앞으로 해야 할 작업 목록을 가지고 있다고 해보자. 어떤 작업을 어떤 순서로 시행해야 할까?  Case 1) 특정 시점에 오직 하나의 작업만 수행할 수 있을 때솔루션) 종료 시간 기준각각의 작업은 고유한 ID, 시작 시간, 종료 시간을 갖는다. 이러한 작업을 표현할 구조체를 생성하자. 이 구조체는 인스턴스로 각 작업을 표현한다.N개의 작업을 포함하는 list를 생성한다. 각 작업은 1부터 N까지 고유한 ID를 가지며, 시작 시간과 종료 시간은 임의의 정수로 설정한다스케줄링 함수를 작성한다종료 시간을 기준으로 전체 작업 리스트를 정렬한다.현재 리스트에서 그리디 방식으로 가장 빠른 종료 시간을 갖는 작업을 선택하자현재 선택된 작업과 시간이 겹치는 작업은 모두 제거한다. 즉, 현재 작업 종료..

배낭 문제0-1 배낭 문제라고 부르는 일반 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다.하지만 문제를 조금 변경한 분할 가능 배낭 문제(fractional knapsack problem)은 그리디 방식으로 해결할 수 있다. 0-1 배낭 문제물건들의 집합 O = [O1, O2, O3, .... , On]이 있고, 여기서 i번째 물건 Oi의 무게는 Wi이고 가격은 Vi라고 하자.그리고 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 하나 주어진다이제 물건들을 가방에 담아야 하는데, 가방에 넣은 물건들의 가격 합이 최대가 되로록 물건을 선택해야 한다물건들의 무게 합이 T를 넘지 않아야 한다.위에서 말했듯이 0-1 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 ..

최단 작업 우선 스케줄링사람들이 은행 창구에 줄을 서서 순서를 기다리는 상황을 생각해보자. 대기열에는 N명의 사람이 기다리고 있다.각 사람마다 일 처리에 필요한 시간은 다르다대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록 대기 순서를 다시 정하는 것에 동의한다고 가정한다.따라서 평균 대기 시간을 최소화하는 것이 목표이다.가능한 많은 사람의 대기 시간을 줄일 수 있는 방법을 찾아보자.일 처리가 가장 빨리 끝나는 사람을 맨 앞에 세워야 한다 최단 작업 우선 스케줄링 구현최단 작업 우선 스케줄링을 구현하는 것은 매우 단순하다. 일 처리 소요 시간 순으로 오름차순으로 정렬하면 된다.정렬 전 대기 시간과 정렬 후 대기 시간을 비교해보는 코드를 작성해보자 #include ..

그리디 알고리즘(greedy algorithm)이란?알고리즘 설계 패러다임 중 하나로, 매 단계에서 '가장 좋아 보이는' 해답을 선택하는 알고리즘이다. 매 단계마다 전체적으로 최적인지는 판단하지 않고 현재 최적이라고 판단되는 결정을 함. 즉 과거(이전 선택)나 미래(앞으로의 선택)는 생각하지 않고, 오직 현재의 최대 만족만을 추구. (근시안적 선택)그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식이다.  Example) 지도 지도 서비스에서 두 지점의 최단 이동 경로 기능을 제공한다이 때, 출발 지점에서 아직 방문하지 않은 가장 가까운 지점까지의 경로를 찾고, 이를 목적 지점에 다다를 때 까지 반복하여 경로를 구한다.(다익스트라 알고리즘의 기본 개념) 그리디 접근..

거듭 제곱 계산법C^2을 계산하기 위해서는 다음과 같이 C 자신을 두 번 곱해야 한다C^2 = C X CC^n을 계산하려면 C 자신을 n번 곱해야 한다.이를 코드로 바꾸면 다음과 같다int Power( int Base, int Exponent ){ int i=0; int Result = 1; // C^0은 1이므로 for ( i=0; i 지수 크기만큼 곱셈을 수행하므로 O(n) 수행 시간을 소요한다는 사실을 알 수 있다.이보다 더 빠른 방법은 없을까?접근C^8은 C x C x C x C x C x C x C x C 로 정의되지만다음과 같이 표현할 수도 있다. C^2을 구한 뒤 제곱을 두 번 더 반복하여 결국 세 번의 곱셈만 수행함으로써 같은 결과를 얻을 수 있다.하지만 이 방법을 모든 제곱 연산에 적용할..

분할 정복을 적용하는데 있어서 주의할 점분할 정복이 부적절한 경우입력이 분할될 때 마다 분할된 부분 문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 커지는 경우ex) 피보나치 수 구하기recursive하게 정의 : F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.예를 들어, n 번째의 피보나치 수를 구하는데 F(n) = F(n-1) + F(n-2)로 정의되므로 재귀 호출을 사용하는 것이 자연스러워 보이나, 이 경우의 입력은 1개이지만, 사실상 n의 값 자체가 입력 크기인 것이다따라서 n이라는 숫자로 인해 2개의 부분 문제인 F(n-1)과 F(n-2)가 만들어지고, 2개의 입력 크기의 합이 (n-1) + (n-2) = (2n-3)이 되어서, 분할 후 입력 크기..

트로미노 타일로 체스판 채우기구멍이 하나 있는 정사각형 체스판을 L 자 모양의 트로미노(tromino) 타일로 채울 수 있는가?체스판의 크기를 2^k ×2^k 라 가정  접근가장 작은 크기의 부문제인 “구멍이 하나 있는 2×2 체스판” 에 대해 어느 곳에 구멍이 있더라도 체스판을 채우는 것이 가능한가? -->  “구멍이 하나 있는 2^k×2^k 체스판”에서 “구멍이 하나 있는 (2^1)×(2^1) 체스판”으로 문제를 점차 줄여나갈 수만 있다면 분할정복 알고리즘을 사용하여 해결 가능하다. 아이디어정사각형의 체스판을 4개의 작은 체스판으로 나눈다하나의 2^k X 2^k 체스판 문제에서 4개의 2^(k-1) X 2^(k-1) 체스판 문제로 분할한다.그런데, 3개의 2^(k-1) X 2^(k-1) 체스판에는 구..

최근접 점의 쌍 문제란?2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 가장 간단한 해결 방법모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운점의 쌍을 찾다.nC2 X O(1) = O(n^2)이것보다 효율적인 방법은 없을까?분할 정복을 이용한 해결 방법1. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리 (d)를 가진 점의 쌍을 일단 찾는다. (recursive하게 반복하여 구함)2. [결합] 2개의 부분해를 취합할 때에는 반드시 두 부분 문제서 각각 한 점씩 포함되는 점의 쌍 중에서 그 거리가 d 보다 작은 쌍을 찾는다. (중간영역 고려!)만일 이러한 쌍이 있다면 그런 쌍 중에 ..