그리디 알고리즘 탐욕 알고리즘이라고도 부름 "현재 상황에서 지금 당장 좋은 것만 고른다" -> 최적의 해를 보장할 수 없을 때가 많음 ex. 거스름돈 문제 [500, 100, 50, 10] => 가장 큰 화폐단위부터 Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적해를 보장하는 이유? (정당성 분석) A. 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기에 작은 단위의 동전을 종합해 다른해가 나올 수 없기 때문 그리디 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함 문제1. 곱하기 혹은 더하기 문제: 각 자리 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' ..