본문 바로가기

그리디16

[백준] 1439번 : 뒤집기 – JAVA [자바] https://www.acmicpc.net/problem/1439  문제  해결 방법 이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다. 1. 0과 1이 각각 몇 번 그룹으로 나뉘는지 계산한다. 예를 들어 0001100의 경우, 000 / 11 / 00으로 0 그룹 2개, 1 그룹 1개가 된다. 11001100110011000001의 경우, 11 / 00 / 11 / 00 / 11 / 00 / 11 / 00000 / 1로 0 그룹 4개, 1 그룹 4개가 된다. 2. 0과 1의 그룹 수 중 작은 값을 선택하면 최소 뒤집기 횟수가 된다. 예를 들어 0001100의 경우 0 그룹 2개, 1 그룹 1개이므로 최소 1번 뒤집으면 해결 가능하다. 110011001100110000.. 2025. 3. 13.
[백준] 15903번 : 카드 합체 놀이 – JAVA [자바] https://www.acmicpc.net/problem/15903  문제  해결 방법 이 문제는 그리디 알고리즘(Greedy Algorithm)을 이용하여 해결할 수 있다. 항상 가장 작은 두 수를 합치는 것이 최적의 선택이 되므로, 우선순위 큐(Priority Queue, 최소 힙)를 사용하면 효과적으로 풀 수 있다. 1. 처음에 주어진 n장의 카드를 우선순위 큐(최소 힙)에 넣는다. 2. m번 동안 다음 과정을 반복한다. - 가장 작은 두 개의 카드를 꺼낸다. - 두 값을 더한 뒤, 해당 값을 두 카드에 덮어쓴다. - 새로운 값을 다시 큐에 삽입한다. 3. 모든 합체가 끝난 후, 큐에 남아있는 값들의 합이 최종 점수가 된다.  코드  import java.io.*;import java.util.*;.. 2025. 3. 12.
[백준] 12904번 : A와 B – JAVA [자바] https://www.acmicpc.net/problem/12904  문제  해결 방법이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다. 왜냐하면 특정 상황에서 선택할 수 있는 연산이 항상 하나로 정해져 있기 때문이다. 일반적으로 문자열 S에서 T로 변환하는 방식으로 접근하면 여러 경우의 수를 고려해야 하지만, T에서 S로 변환하는 방식으로 접근하면 연산이 명확하게 결정된다. S에서 T로 변환하는 방법은 밑에 그림처럼 여러 경우의 수가 있다. 하지만, 문자열 T의 마지막 문자가 'A'라면 그 이전 상태는 반드시 'A'를 추가하기 전의 상태이므로 'A'를 제거하면 된다. 반면 마지막 문자가 'B'라면 그 이전 상태는 반드시 문자열을 뒤집고 'B'를 추가하기 전의 상태이므.. 2025. 3. 11.
[백준] 1541번 : 잃어버린 괄호 – JAVA [자바] https://www.acmicpc.net/problem/1541  문제문제 풀이문제 해결 방법:1. '-'를 기준으로 나누기 '-' 연산자는 큰 숫자를 빼는 것이므로, 이를 기준으로 나누면 최솟값을 만들기 쉬워진다.2. 각 그룹의 숫자를 더하기 '-'를 기준으로 나눈 각 부분은 '+' 연산자로 연결된 숫자 그룹이다. 따라서, 각 그룹을 먼저 더한다. 3. 첫 번째 그룹을 시작값으로 설정하고 나머지 그룹을 빼기 첫 번째 그룹은 그대로 사용하고, 이후의 그룹들은 모두 빼주면 된다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 25.
반응형