탐욕법 문제

[Programmers]큰 수 만들기

문제 > 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 탐욕범을 사용하여 풀 수 있다. 숫자를 제거하며 높은 자리 부터 탐욕적으로 채워나가면 된다. 주어지는 number의 첫 자리부터 시작하여 비어있는 stack에 하나씩 psuh해준다. push를 하기 전 저장된 stack의 top의 값과 비교한다. 이 때 top보다 현재 자리의 숫자가 크다면 해당 top을 pop해준다. 이렇게 pop된 숫자는 제거가 된 숫자이다. 그렇기에 제거가 될 때 k를 -1 해준다. 해당 과정을 반복하여 k가 0이 되면 해당 과정을 멈추고 sta..

탐욕법(Greedy)

탐욕법은 말그대로 탐욕적으로 눈앞에 보이는 상황에서 가장 좋은 상황(최선의 선택)을 고르는 것을 말한다. 탐욕법은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다고 한다. 탐욕법 사용 가능 조건 Local minimum과 Global minimum이 같을 경우 sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우 ( 동적계획법과 동일) Problem들의 solution들이 서로 영향을 주면 안된다 탐욕법 예제 탐욕법의 가장 대표적인 예시는 coin change이다 예를 들어 760원을 [10,50,100,500]의 동전으로 주는데 동전을 최소로 주는 방법을 구하는 것이다. 이 때는 가장 큰 500원 부터 차례..