거스름돈 만들기 문제의 정확한 나눗셈 알고리즘 (An Exact Division Algorithm for Change-Making Problem)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 22권 / 3호 / 185 ~ 191페이지
· 저자명 : 이상운

초록

본 논문은 NP-난제로 다항시간 알고리즘이 알려져 있지 않은 거스름돈 만들기 문제(CMP)에 대해       수행 복잡도의 나눗셈 알고리즘을 제안하였다. CMP는 주어진 돈 를   ⋯ 의 동전으로 교환할 경우 교환되는동전 개수 의 합을 최소화 시키는 문제이다. CMP에 대해 알려진 다항시간 알고리즘으로는 욕심쟁이 알고리즘(GA), 분할정복(DC)과 동적 계획법(DP)이 있으나 최적 해는  의 DP로 구할 수 있으며, 일반적으로    으로 주어진경우 수행 복잡도는 지수적으로 증가하는 경향이 있어 다항시간 알고리즘이라고 할 수 없다. 본 논문에서는  ≤ 에한해,  열에 개의  내림차순으로 배치하고, 행에는 의 약수를 모두 제외시킨 개의 동전을 배치한 × 행렬에대해 상삼각행렬과 주대각선 셀에 대해 나눗셈을 하여 몫(quotient)을 구하는 단순한 알고리즘을 제안한다. 제안된 알고리즘을 다양한 유형의 39개 벤치마킹 실험 데이터에 적용한 결과 최적 해를 단순히 계산기만을 사용하여도 빠르고 정확하게 구할 수 있음을 보였다.

영어초록

This paper proposed a division algorithm of performance complexity       for a change-making problem(CMP) in which polynomial time algorithms are not known as NP-hard problem.
CMP seeks to minimize the sum of the  number of coins exchanged when a given amount of money  is exchanged for   ⋯  coins. Known polynomial algorithms for CMPs are greedy algorithms(GA), divide-and-conquer (DC), and dynamic programming(DP). The optimal solution can be obtained by DP of  , and in general, when given    , the performance complexity tends to increase exponentially, so it cannot be called a polynomial algorithm. This paper proposes a simple algorithm that calculates quotient by dividing upper triangular matrices and main diagonal for × matrices in which only  columns are placed in descending order of  of  for  ≤  and  rows are placed  excluding all the dividers in  . The application of the proposed algorithm to 39 benchmarking experimental data of various types showed that the optimal solution could be obtained quickly and accurately with only a calculator.

참고자료

· 없음