Earticle

초록

영어

This paper proposed a division algorithm of performance complexity O(n(n+1)/2) 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 xj number of coins exchanged when a given amount of money C is exchanged for cj, j = 1,2 ⋯ , n 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 O(nC), and in general, when given C>2n , 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 k × n matrices in which only j columns are placed in descending order of cj of n for cj ≤ C and i rows are placed k excluding all the dividers in cj. 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.

한국어

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

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련연구와 문제점
Ⅲ. 다항시간 정확한 알고리즘
Ⅳ. 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un, Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380