김영평생교육원 알고리즘 과제

문서 내 토픽

1. 그리디 알고리즘

그리디 알고리즘(탐욕(Greedy)알고리즘)이란 입력 데이터 간의 관계를 고려하지 않고 수행 과정에서 욕심을 내어 '근시안적으로' 최댓값 또는 최솟값을 가진 데이터를 선택하는 알고리즘이다. 쉽게 말해 눈앞의 이익만 취하고 보는 알고리즘으로, 현 시점에 가장 이득이 되어 보이는 해를 선택하는 행위를 반복한다. 원하는 결과를 얻는 데 시간이 너무 많이 걸리는 경우 항상 최적의 값을 보장하는 것이 아닌, 최적의 값의 '근사한 값'을 목표로 한다.
2. 동전 거스름돈 문제

동전 거스름돈 문제는 그리디 알고리즘이 최적화 알고리즘이 되는 경우의 예이다. 가장 큰 화폐 단위부터 돈을 거슬러 줘야 하는데, 이는 매 순간 남은 거스름돈보다 크지 않은 단위 중 가장 큰 단위의 동전을 선택하는 것이 지역적으로 최적의 선택이자 최적해를 구할 수 있는 방법이다. 이 문제는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합했을 때 다른 해가 나올 수 없기 때문에 그리디 알고리즘을 사용한 최적해 도출이 가능하다.
3. 0-1 배낭 문제

0-1 배낭 문제는 그리디 알고리즘이 최적화 알고리즘이 되지 않는 경우의 예이다. 도둑이 그리디 알고리즘을 사용한다면 가장 비싼 물건부터 차례로 가방에 넣는 과정을 반복할 것이다. 하지만 이 경우 최적의 해를 찾지 못할 수 있다. 이 문제에서는 탐욕스런 선택 조건을 만족하지 못했고, 그리디 알고리즘을 사용한 최적해 도출에 실패했다.

Easy AI와 토픽 톺아보기

1. 그리디 알고리즘

그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 하는 방식으로, 전체적인 최적해를 보장하지는 않지만 빠르고 간단한 해결책을 제공합니다. 이 알고리즘은 최적해에 가까운 해를 찾는 데 유용하며, 특히 문제의 구조가 단순하고 제약 조건이 명확할 때 효과적입니다. 하지만 그리디 알고리즘은 전체적인 최적화를 보장하지 않기 때문에, 문제의 특성을 잘 파악하고 다른 알고리즘과 비교하여 가장 적합한 방법을 선택해야 합니다.
2. 동전 거스름돈 문제

동전 거스름돈 문제는 그리디 알고리즘을 적용하기 적합한 대표적인 문제입니다. 이 문제에서는 가치가 큰 동전부터 사용하여 거스름돈을 최소한의 동전으로 지불하는 것이 최적의 해결책입니다. 그리디 알고리즘은 이 문제에서 최적해를 보장하며, 구현이 간단하고 실행 시간이 빠르다는 장점이 있습니다. 따라서 동전 거스름돈 문제와 같이 최적해를 보장하는 문제에서는 그리디 알고리즘이 매우 효과적인 해결책이 될 수 있습니다.
3. 0-1 배낭 문제

0-1 배낭 문제는 그리디 알고리즘으로 해결하기 어려운 대표적인 문제입니다. 이 문제에서는 각 물건의 무게와 가치를 고려하여 배낭에 담을 물건을 선택해야 하는데, 그리디 알고리즘은 이러한 최적화 문제를 해결하기 어렵습니다. 대신 동적 계획법이나 분기 한정 알고리즘과 같은 최적화 알고리즘이 더 적합합니다. 이러한 알고리즘은 문제의 구조를 잘 활용하여 최적해를 찾을 수 있지만, 그리디 알고리즘에 비해 구현이 복잡하고 실행 시간이 더 오래 걸릴 수 있습니다. 따라서 문제의 특성을 잘 파악하고 적절한 알고리즘을 선택하는 것이 중요합니다.