geminanolja 님의 블로그

https://www.acmicpc.net/problem/11399#include #include#includeusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector WaitingLine(n); for (int i = 0; i > WaitingLine[i]; } //for (auto a : WaitingLine) cout ❌ 순열로 풀면 비효율적! (Brute-force 접근 문제점)순열(모든 경우의 줄 서는 순서)을 사용하여 해결하는 방법도 가능하지만, 너무 비효율적순열을 이용한 풀이 방식N명의 사람이 줄을 서는 모든 경우(순열)를 구한다. →..

cote/Intermediate 2025. 2. 11. 15:05

기본 아이디어현재 상태에서 **가장 좋은 선택(최적의 선택)** 선택이 선택이 이후 문제에 영향을 미칠지 고민하지 않고, 현재 문제만 고려이렇게 탐욕적인 선택을 반복하면 전체 문제를 해결할 수 있음그리디 알고리즘의 특징탐욕적 선택 속성 (Greedy Choice Property):현재의 탐욕적 선택이 나중에 영향을 미치지 않고, 전체 문제의 최적 해를 보장합니다.부분 최적해 (Optimal Substructure):부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있어야 합니다.중요: 그리디 알고리즘은 모든 문제에 적합하지는 않음적용 가능한 문제의 조건탐욕적 선택 속성:각 단계에서의 최적의 선택이 전체 문제의 최적해를 보장해야 함최적 부분 구조:문제를 부분 문제로 나누었을 때, 각 부분 문제의 최적해..

자료구조&알고리즘/C++ 2025. 1. 19. 20:48