barded

그리디(greedy) 알고리즘 그리디 알고리즘은 단어 그대로 욕심쟁이 알고리즘이다. 현재 상황에서의 최선의 것을 골라서 탐색하는 방식이며 현재의 선택이 나중에 미칠 영향은 고려하지 않는다. 가장 대표적인 예로 거스름돈 문제가 있다. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10월짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬로 줘야 할 돈 N은 항상 10의 배수이다. import java.util.Scanner; public class ChangeMoney { public static int changeMoney(int N) { int [] change ..

순열 순열(Permutation) 이란 n개 중 r개의 숫자를 순서대로 뽑는경우를 말한다. 예를들어 [1, 2, 3] 에서 2개의 숫자를 뽑는 경우는 [1,2],[1,3] [2,1],[2,3] [3,1],[3,2] 이렇게 총 6개가 된다. visited 배열을 사용해서 순열을 구현해보자. static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) { if(depth == r) { print(output, r); return; } for(int i = 0; i < n; i++) { if(!visited[i]) { visited[i] = true; output[depth] = arr[i]; perm(arr, out..