greedy

https://www.acmicpc.net/problem/2413 문제분석Greedy를 활용해 문제를 풀어야 한다.최적 해는 다음과 같다.1. 짝을 맞춰야 한다. n은 n-1과 위치를 바꾸는 것 밖에 안되기 때문.2. n이 n-1보다 높은 자릿수(순열의 앞쪽(왼쪽))에 있을 때, 무조건 바꿔야 한다. 가장 작은 순열을 구해야 하기 때문.3. 순열의 앞쪽(왼쪽)부터 짝을 찾아서 바꿀 수 있는지 여부를 확인해나아가야 한다.코드import java.util.*;import java.io.*;public class Main{ public static void main(String[]args)throws IOException{ BufferedReader br = new BufferedReader..

https://www.acmicpc.net/problem/2457 군자의 복수는 10년이 걸려도 늦지않는다. 문제 해결을 실패하고, 2년 좀 안되는 시점에 다시 시도해서 성공했다! 너무 기쁘다!!!문제분석어쩌면 살짝 억울하다고 느끼는 점은, 아이디어 자체는 2년 전 시도와 완벽하게 동일하다. 단지 언어 변경과 그리디 알고리즘에 대한 공부(이게 가장 큰 것 같긴 하다)를 통해 생각보다 쉽게 해결하였다.사실 쉬운 정도가 아니라, 2년 전 시도 코드와 비교하면 말도 안되게 짧다. 부분 문제의 최적해를 이어서 전체 문제의 최적해로 나아간다는 아이디어를 통해 대폭 줄인 것 같다. 풀이는 다소 간단하다. 꽃을 심으면서, 다음 조건을 만족하면 된다. 1. 직전의 꽃이 죽기 전에 피는 꽃들 중 하나를 무조건 골라야 ..

문제분석정확히 백준 2569 짐정리와 같은 문제이다solved.ac에 적용이 안되어 이유를 보니, 이 문제와 같은 문제여서 2569가 등록이 안되더라. 그래서 코드 일부(long)만 수정하여 푼 문제로 등록하였다.해결과정완벽하게 2569와 같은 문제(long 신경 써 줘야 하는것 제외하면)이다. 따라서 아래 글을 참고하면 된다.https://chabin37.tistory.com/99 [JAVA] 백준 2569 짐정리https://www.acmicpc.net/problem/2569 그리디가 메인인 문제인 줄 알고 풀었으나, 알고보니 사이클 관련 문제였다...그래도 그리디가 있긴 하지만..뭔가 찜찜..문제분석처음엔 그리디에 초점을 두고, 최소chabin37.tistory.com 문제에서 2^30까지 신경써야..

https://www.acmicpc.net/problem/1715 문제분석카드를 최소한으로 비교하는 상황을 찾고, 그때 비교 횟수를 출력하는 문제이다. 예를들어, 10,20,40이 있으면 10과 20을 먼저 합치고, 만들어진 30과 40을 합치면 된다. 그리디 알고리즘 연습으로 선택한 문제인데, 우선순위 큐 까지 배울 수 있는 좋은 문제인 것 같다. 그리디인 만큼 '최소해' 를 먼저 찾아야 한다.해결과정첫 번째로 생각한 부분 최적해는, 정렬 이후 '작은 카드 더미부터 합쳐나가기' 였다. 하지만 틀렸고, 이유를 생각해보니 더 좋은 방법이 존재했다. 10, 20, 20, 20, 100으로 이루어진 상황이다. 첫번째 아이디어로 접근하면 정답이 나오지 않는다->부분 최적해가 아님.두번째 상황이 최적해 인 것을..

https://www.acmicpc.net/problem/1700문제분석그리디 알고리즘 연습을 위한 문제이다 보니, '부분 최적해' 를 구하기 위해 노력하였다.플러그 구멍이 남는 경우, 제품이 이미 꽃혀있는 경우들은 문제가 아니므로 제외한다. 따라서 생각해야 하는 문제는 아래와 같다.플러그가 가득 찼을 때, 새 플러그를 꽃기 위해 뽑아야 하는 플러그는 무엇인가?가장 처음 생각한 부분 최적해는 '남은 횟수가 적은 제품 먼저 플러그를 뽑을 것' 이다. 이 방식으로 문제를 풀어보니, 다음 반례에 막히게 된다.2 91 2 3 1 2 3 1 2 34가 나오지 않는 문제에 직면했다. 따라서 부분 최적해를 잘못 설정했다는 것을 알 수 있었다.이후, 두번째로 생각한 것은 '사용할 제품부터 N개를 확인한 후, 가장 뒤에..