하수하따 록기장

📍 문제 링크 : https://www.acmicpc.net/problem/2138 📍 알고리즘 분류 : 그리디 알고리즘 📍 문제 풀이 신기한 점이 어떤 전구를 먼저 켜고 끄든, 순서가 중요하지 않다는 것이다!따라서 우리는 첫 번째 전구부터 순서대로 탐색하면 된다. 그리디하게. 현재에 최적이 되도록.첫 번째 전구를 목표 상태와 비교하고 다르다면 전구의 상태를 바꾸고, 같다면 그냥 두면 된다. 그런데 전구는 자신의 왼쪽, 자신, 자신의 오른쪽 이렇게 3개의 전구의 상태에 영향을 미치게 되는데그리디하게 접근할 경우 이 조건이 훨씬 쉽게 만들어진다. 현재 보고 있는 i번째 전구를 변경하고자 할 경우 할 수 있는 것은 i+1번째 전구를 누르는 것이라는 것이다! i-1번째 전구나 i번째 전구를 누르면 안되는..

📍 문제 링크https://www.acmicpc.net/problem/1339 📍 알고리즘 분류그리디 📍 문제 풀이직관적으로 높은 자리에 큰 수가 와야된다는 것을 파악할 수 있다. 그런데 단어가 하나가 아니기 때문에, 어떤 단어에서는 높은 자리수의 알파벳이 다른 단어에서는 가장 낮은 자리수에 위치해있을 수도 있다. 따라서 모든 단어를 종합하여 판단해야 한다. ABC와 CADB가 주어졌다고 해보자.단어 수의 합은 (100*A + 10*B + C) + (1000*C + 100*A + 10*D + B) = (1000*C + 200A + 11B + C)가 될 것이다.이게 최대가 되기 위해서는 가장 큰 수를 곱하는 알파벳부터 9, 8, 7, 6, .. 순서대로 바꿔주면 된다.따라서 C = 9, A = 8, ..

📍문제 링크https://www.acmicpc.net/problem/1202 📍알고리즘 분류그리디, 우선순위 큐 📍 풀이 방법최대한 많은 보석을 훔치기 위해서는 최대한 비싼 보석을, 많이 담아야 한다.따라서 비싼 보석부터 담아야 하는데, 최대로 용량을 채울 수 있는 가방에 넣어야 한다.반복문을 통해 가방을 하나씩 그리디하게 보면서 넣을 보석을 정해준다.우선순위 큐를 이용해서 하나의 가방 안에 들어갈 수 있는 무게의 보석들 중 가격이 가장 비싼 것을 담으면 된다. 어떤 가방부터 보아야할까?용량이 큰 가방부터 본다면, 비싼데 크기가 작은 보석이 용량이 큰 가방에 담길 것이다. 더 보석을 가져갈 수 있을텐데 용량이 낭비될 것이다.따라서 용량이 작은 가방부터 탐색한다. 작은 가방에 담기는 무게 중에서 비싼..

더보기목차1. Greedy 알고리즘이란2. MST란3. Kruskal 알고리즘- 이론, 구현4. Prim 알고리즘- 이론, 구현1. Greedy 알고리즘이란Greedy 알고리즘이란 욕심장이 기법으로 당장 이 순간에서 최적이 되는 해를 구하는 것에, 즉 현재에 집중하는 알고리즘입니다. 과거와 미래는 전혀 신경쓰지 않습니다. Greedy 알고리즘의 핵심 단계는 다음과 같습니다.  1) Selection Procedure (선택)현재를 기준으로 가장 최적이 되는 해를 선택하는 단계입니다. 최적 해를 선택하여 집합에 추가합니다. 이 과정을 위해 선행되는 핵심은 어떤 값을 먼저 볼 것인지에 대한 우선순위 결정입니다. 2) Feasibility Check (유효성 검사)앞에서 선택한 해를 포함한 집합이 문제를 해결..