본문 바로가기

그리디 알고리즘8

[자바] 백준 27988 - 리본 (Hard) (java) 목차 문제 : boj27988 필요 알고리즘 그리디 알고리즘, 정렬 문제를 좀 더 간단히 생각해보면 동일한 규칙을 적용시켜서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각 과정은 다음과 같다. 1. 일단 입력으로 들어온 데이터부터 좀 더 이해하기 편하게 바꿔보자. X위치에 달린 길이 L의 구부릴 수 있는 리본이라 함은 결국 [X-L, X+L] 에서 다른 색상을 만나기만 하면 되는 리본이라 볼 수 있다. [.. 2023. 6. 16.
[자바] 백준 1083 - 소트 (java) 목차 문제 : boj1083 필요 알고리즘 그리디 알고리즘 최선의 방법을 정해 매번 시도하면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각 과정은 다음과 같다. 1. N이 50인데 S가 100만?! -> 버블 정렬 생각해보면 결국 N(1+N)/2번 수행되면 어차피 내림차순으로 가능하므로, S가 큰건 의미가 없다. S가 1275 초과일 경우 어차피 의미 없는 값이므로, 100만이라도 문제없음! if.. 2023. 6. 14.
[자바] 백준 2258 - 정육점 (java) 목차 문제 : boj2258 필요 알고리즘 그리디 알고리즘, 정렬 그리디 알고리즘으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤게 이득일지 직관적으로 한번 생각해보자. 뭐 당연히 싸고 무게 높은 고기일수록 이득이다. 그럼 싼게 더 중요할까 무게 높은게 더 중요할까? 이 문제의 경우엔 둘 중 하나를 선택하기가 어려운데, 어떠한 덩어리를 샀을 때 그 덩어리보다 싼 고기는 무료로 구매가 가능하기 때.. 2023. 3. 15.
[자바] 백준 1092 - 배 (java) 목차 문제 : boj1092 필요 알고리즘 그리디 알고리즘, 정렬 규칙성을 찾아 매번 최선의 방식으로 진행하는 그리디로 풀 수 있는 문제이다. 보통 그리디 태그는 정렬도 필요한 경우가 많다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 풀고나서 다른 사람들 코드를 보니 아예 다른 로직들이 보여서 좀 당황스러웠다. 보통 크레인 무게 제한 내림차순, 박스 무게 내림차순으로 정렬한 후, 각 크레인에 가능한 박스를 넣는 시뮬레이션.. 2023. 3. 14.
[자바] 백준 20365 - 블로그2 (java) 목차 문제 : boj20365 필요 알고리즘 그리디 알고리즘 탐욕법으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내가 생각한 방식은 다음 두 가지 경우 중 횟수가 작은쪽을 선택하는 것이다. 1. 전체를 파란색으로 칠한 후, 연속된 'R'들을 빨간색으로 칠한다. 2. 전체를 빨간색으로 칠한 후, 연속된 'B'들을 파란색으로 칠한다. 따라서 입력으로 받은 문자열에서 연속된 'R'그룹과, 연속된 'B'.. 2023. 3. 11.
[자바] 백준 22864 - 피로도 (java) 문제 : boj22864 필요 알고리즘 개념 그리디 알고리즘 논리적으로 최선의 경우를 만드는 규칙을 정해 모든 경우에 적용시켜서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 뭔가 곱셈, 나눗셈으로 풀 수 있을 것 처럼 생겼는데, 단 한번이라도 M을 넘기면 안되는걸 판단하기가 많이 어려울 것 같다. 24시간만 판단하면 되므로 총 24번 매번 확인하면 된다. 확인 방식은 간단한데, 매번 A만큼 피로도가 쌓여도 M.. 2022. 10. 25.
[자바] 백준 10162 - 전자레인지 (java) 문제 : boj10162 필요 알고리즘 개념 그리디 알고리즘 규칙을 정해, 매번 해당 규칙을 적용시켜 답을 구하는 그리디 알고리즘 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최소 버튼 조작 횟수이므로, 그냥 초가 큰 버튼부터 눌러주면 된다. A,B,C를 초로 변경해주면 300,60,10 이므로 300을 누를 수 있는만큼 누르고, 60을 누를 수 있는 만큼 누르고, 10을 누를 수 있는 만큼 누르면 된다. 근데 .. 2022. 8. 21.
[자바] 백준 1715 - 카드 정렬하기 (java) 문제 : boj1715 필요 알고리즘 개념 그리디 일정한 규칙을 정해 매번 해당 규칙을 적용시키다 보면 답이 나오는 알고리즘으로, 뭔가 알아야 하는건 아니고 그냥 그런 식으로 생각할 수 있어야 한다. 우선순위 큐 (Priority Queue), Min heap 다른걸 사용해서 풀어도 되지만, 이 문제를 가장 쉽게 풀 수 있는건 우선순위 큐를 사용해 min heap으로 사용하는 것이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다... 2022. 8. 21.