거스름돈 알고리즘(Coin Change Algorithm), 동전교환 알고리즘
[출처] https://www.amazon.com/School-Smart-Assorted-Plastic-Coins/dp/B00JKIEQPS 거스름돈 알고리즘(Coin Change Algorithm) 또는 동전교환 알고리즘은 동전 coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000}이 있고 값 V 가 주어졌을 때 V와 동일하도록 동전을 선택하는 문제인데 이때 동전의 개수를 최소화(minimum)하는 방법을 찾는 것이다. (단, 같은 동전을 여러번 선택 가능하다) 예를들어 coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000} 들이 있을때 선택한 동전의 개수는 최소화 하면서 동전의 합이 70원이 되도록 해야만 한다면 20원, 50원 동전 2개를 선택..
순열(permutation) 알고리즘
순열(permutation)이란 숫자나 문자들의 집합(set)에 순서를 부여하여 나열하는 것이라고 생각하면 된다. 예를들어 원소가 'A', 'B', 'C'를 가진 집합 S 가 있다면 ( { 'A', 'B', 'C' } ∈ S) 이 A ,B, C 각각의 원소를 일렬로 나열했을때 나올수 있는 경우의 수는 (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A) 총 6가지가 나올수 있다. 순열에 대해서 자세히 알고 싶으면 순열(permutation) 를 먼저 읽어봐라. 그럼 순열을 프로그래밍적으로 어떻게 접근해야 할까? 만약 {a,b,c,d}의 모든 순열을 구한다고 하면 ☞ 첫 원소가 a이면서 {b,c,d}의 모든 순열 ☞ 첫 원소가 b이면서 {a,c..
