책/Do it! 알고리즘 코딩 테스트 자바 편

Day-10,11 그리디 알고리즘

댈팽이 2024. 4. 3. 17:58
728x90

1. 그리디 알고리즘 (탐욕법)

  • 현재 상태에서 보는 선택지 중 최선의 선택지를 고르는 알고리즘이다.
  • 탐욕법의 결과는 주어진 선택지에서 최적의 결과를 보장해주는 것은 아니다.

2. 그리디 알고리즘 과정

  1. 현재 상태에서 가장 최선인 해를 선택
  2. 선택한 해가 문제의 조건에 부합하는지 검사
  3. 현재까지 선택한 해 집합이 문제를 해결할 수 있는지 검사,
    해결할 수 없으면 1로 돌아가 같은 과정을 반복

3. 예제 문제

 

[11047] 동전 0 (JAVA)

# 문제 설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구

spicyrisotto.tistory.com

 

[2839] 설탕 배달 (JAVA)

# 문제 설명 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지

spicyrisotto.tistory.com

 

[1931] 회의실 배정 (JAVA)

# 문제 설명 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않

spicyrisotto.tistory.com

728x90