컴퓨터 공학/알고리즘2 탐욕 알고리즘(Greedy algorithm) 매 순간마다 최적의 해를 찾는 문제해결 패러다임 이다. 알고리즘의 작동 방식이 이름과 매우 흡사하다. 간단하게 예를 하나 들어보자. 탐욕 알고리즘을 이용하는 대표적인 문제는 동전 거스름돈 문제이다. 이 문제는 거슬러 받는 동전의 개수를 가장 적게 받아야 하는 문제이다. 동전의 종류는 현실과 마찬가지로 1원, 10원, 50원, 100원, 500원이 있다고 하고 거슬러 받아야 할 돈은 총 1761원이라고 하자. 생각하기 가장 쉬운 방법은, 액수가 가장 큰 동전부터 채워서 주는 것이다. 이렇게 줄 경우 500원 3개 + 100원 2개 + 50원 1개 + 10원 1개 + 1원 1개 ==>> 총 8개의 동전을 주게 된다. 과연 최소한의 개수로 동전을 준 것이 맞을까? 질문의 답은 '예' 다. 다만, 동전 거스름돈.. 2020. 4. 11. 동적 계획법(Dynamic Programming) 문제를 여러개의 작은 문제로 나누고, 작은 문제의 해를 이용하여 더 큰 문제의 해를 찾는 문제해결 패러다임 이다. 설명을 쉽게 하기 위하여 간단하게 예를 들어보자. 동적 계획법을 이용하는 대표적인 문제는 동전 거스름돈 문제이다. 이 문제는 거슬러 받는 동전의 개수를 가장 적게 받아야 하는 문제이다. 동전의 종류는 1원, 3원, 7원, 10원이 있고 거슬러 받는 돈이 총 14원이라고 하자. 생각하기 가장 쉬운 방법은, 액수가 가장 큰 동전부터 채워서 주는 것이다. 이렇게 줄 경우 10원 1개 + 3원 1개 + 1원 1개 ==>> 총 3개의 동전을 주게 된다. 과연 최소한의 개수로 동전을 준 것이 맞을까? 질문의 답은 '아니오' 다. 7원짜리 2개를 주는 방법이 동전을 더 적게 줄 수 있다. 만약, 동전의 .. 2020. 4. 11. 이전 1 다음
