Brute force Study

[Algorithm/Greedy] 동전 거스름돈 문제

동전 거스름돈(Coin Change) 문제란?동전 거스름돈의 최소 동전 수를 찾는 그리디 알고리즘달성 목표 : 최소 동전 수제한 조건 : 거스름돈의 가치가 같도록 한다 그리디 방식의 동전 거스름돈을 결정하는 해결 문제매 순간마다 남은 거스름돈의 총액을 초과하지 않는 조건하에 ‘greedy, 욕심내어’ 가장 큰 액면의 동전을 취함가장 큰 액면을 가진 동전부터 차례로 선택하여 남은 거스름돈 액수보다 작을 경우 해답에 포함시킨다슈도 코드동전의 액면은 500원, 100원, 50원, 10원, 1원이라고 할 때입력 : 거스름돈 액수 W출력 : 거스름돈 액수에 대한 최소 동전수1. change=W, n500=n100=n50=n10=n1=0 // n500, n100, n50, n10, n1은 각각의 동전 카운트2. w..

[Algorithm/Greedy] 웰시-포웰 알고리즘(Welsh-Powell algorithm)

웰시-포웰 알고리즘이란앞에서 봤던 그리디 그래프 컬러링 알고리즘은 1번 정점부터 그래프 컬러링을 시작했다.시작한 정점에 따라 사용한 색상의 수가 달라질 수 있다. 이를 조금 향상시키는 방법은 차수(degree, 정점에 연결된 에지의 개수)가 높은 정점부터 차례대로 그래프 컬러링을 수행하는 것이다.이를 웰시-포웰 알고리즘이라고 한다.모든 정점을 차수에 대한 내림차순으로 정렬하고 배열에 저장한다정렬된 배열에서 색상이 지정되지 않은 첫 번재 정점을 선택하고(배열에서 색상이 지정되지 않은 것들 중에서 차수가 제일 높은 것), 이 정점과 연결된 모든 정점을 조사하여, 아직 사용되지 않은 색상을 해당 정점(아까 말한 차수가 제일 높은 정점)에 지정한다. 이 색상을 C라고 지칭하자.정렬된 배열에서 색상이 지정되지 않..

[Algorithm/Greedy] 그래프 컬러링

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

[Algorithm/Greedy] 최소 신장 트리(Minimum Spanning Tree, MST) 문제 (크루스칼)

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

[Algorithm/Greedy] 작업 스케줄링 문제

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

[Algorithm/Greedy] 배낭 문제(knapsack problem)

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

[Algorithm/Greedy] 최단 작업 우선 스케줄링(shortest-job-first scheduling)

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

[Algorithm/Greedy] About 그리디 알고리즘

그리디 알고리즘(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)이 되어서, 분할 후 입력 크기..