Brute force Study

동전 거스름돈(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..

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

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

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