승코딩당당당

문제[C++] 백준 1715: 카드 정렬하기 GOLD 4https://www.acmicpc.net/problem/1715 접근 방법이 문제는 여러 묶음의 카드가 주어졌을 때, 모든 카드를 하나로 합치는 데 필요한 비교 횟수의 최소값을 구하는 문제이다.핵심 아이디어는 항상 가장 작은 두 묶음을 먼저 합치는 것이다.두 묶음을 합칠 때 발생하는 비교 횟수는 두 묶음의 크기 합이고, 이 값은 이후에도 계속 누적되기 때문에 작은 값부터 처리해야 전체 합이 최소가 된다. 이를 효율적으로 구현하기 위해 우선순위 큐(priority_queue) 를 사용했다.모든 카드 묶음을 우선순위 큐에 넣는다. (오름차순)큐에서 가장 작은 두 값을 꺼내 합친다.그 합을 결과에 더하고, 다시 큐에 넣는다.큐에 하나만 남을 때까지 반..

문제[C++] 백준 11047: 동전 0 SILVER 4https://www.acmicpc.net/problem/11047 접근 방법이 문제는 주어진 동전들을 이용해 합이 K가 되도록 만들 때 필요한 최소 동전 개수를 구하는 문제이다.각 동전은 무한히 사용할 수 있고, 동전의 가치들은 오름차순으로 주어진다.이 문제의 핵심은 그리디 알고리즘이다.항상 가치가 가장 큰 동전부터 최대한 사용하는 것이 최적이라는 조건이 보장되어 있다.그래서 다음과 같은 방식으로 접근했다.동전 배열의 가장 뒤(가장 큰 가치) 부터 확인한다.현재 동전이 k보다 작거나 같다면,k / coin[i] 만큼 사용할 수 있고사용한 만큼 k %= coin[i]로 남은 금액을 갱신한다.모든 동전을 확인할 때까지 반복한다.이 과정을 거치면 최소..

그래프 탐색이나 탐색 알고리즘과는 다르게,선택의 기준이 핵심이 되는 알고리즘이 바로 그리디 알고리즘(Greedy Algorithm)이다.그리디 알고리즘은 매 순간 현재 상태에서 가장 좋아 보이는 선택을 하며 문제를 해결해 나가는 방식이다. 구현이 비교적 쉽고 빠르기 때문에 코딩 테스트에서 자주 등장하지만,항상 정답을 보장하지는 않는다는 점에서 주의가 필요하다.이번 글에서는 그리디 알고리즘의 개념과 특징, 동작 과정, 그리고 사용할 때 주의할 점을 중심으로 정리해보려고 한다. ✍️ 그리디 알고리즘이란?그리디 알고리즘(Greedy Algorithm)은현재 상태에서 볼 수 있는 선택지 중 최선의 선택을 반복하는 알고리즘이다. 즉,지금 당장 가장 좋아 보이는 선택을 하고그 선택이 이후의 선택에 어떤 영향을..

문제[C++] 백준 2512: 예산 SILVER 2https://www.acmicpc.net/problem/2512 접근 방법이 문제는 각 지방의 예산 요청이 주어졌을 때, 총 예산 M을 넘지 않도록 상한액을 정해 지방 예산을 배정하는 문제이다. 핵심은 “상한액을 X로 정했을 때, 각 지방에 min(요청 금액, X)를 배정하면 총합이 M을 넘는가?”를 판단하는 것이다.상한액이 커질수록 총 배정 예산은 증가하므로, 이 조건은 단조성을 가지게 된다.따라서 상한액을 대상으로 이분 탐색(Parametric Search) 을 사용할 수 있다.가능한 상한액의 범위: 0 ~ 요청 예산의 최댓값mid를 상한액이라고 가정하고 총 배정 예산을 계산총합이 M을 초과하면 상한액을 줄이고end = (mid - 1);초과하지 ..