geminanolja 님의 블로그

문제를 해결할 때 각 단계에서 그 순간에 최선이라고 생각되는 선택을 하는 방식이 과정에서 얻은 선택들이 모여 전체 문제에 대한 최적의 해를 구하는알고리즘 그리디 알고리즘은 지역적최적해(Local Optimal Solution)를 찾는 과정 에서, 이를 모아 전역적 최적해(Global Optimal Solution)를 구하는 방식  다만, 모든 경우에 전역 최적해를 보장하지는않음  예를들어12100원짜리물건을구매할때내가가지고있는돈이다음과같다고해봅시다.10000원 5개 5000원 5개 1000원 5개 100원 5개 라고 했을때 가장지폐를적게내는(동전도지폐라고취급)경우의수는무엇일까요? 바로 10000원 1개. 1000원 2개. 100원 1개.를 내는 것입니다. 이렇게 우리는 가장 큰 것부터 내면 최적해라는것을..

자료구조&알고리즘/C++ 2025. 1. 21. 22:53

https://www.acmicpc.net/problem/2343     강토는 강의의 동영상을 블루레이에 저장하려고 합니다. 총 NNN개의 강의가 있으며, MMM개의 블루레이를 사용하여 강의를 저장해야 합니다. 이때 다음 조건을 만족해야 합니다:블루레이 하나에 포함된 강의들은 순서가 바뀌면 안 됩니다.각 강의의 길이는 주어지며, 하나의 블루레이에 녹화되는 강의들의 총 길이가 블루레이의 용량을 초과하면 안 됩니다.MMM개의 블루레이를 모두 사용하는 상황에서, 블루레이의 크기(용량)를 최소화해야 합니다그리디 알고리즘과 이진탐색 #include #include #include #include using namespace std;// 블루레이 크기로 강의들을 나눌 수 있는지 확인하는 그리디 알고리즘을 이용한 ..

cote/Intermediate 2025. 1. 17. 09:56