본문 바로가기

그리디93

[자바] 백준 14204 - 표 정렬 (java) 목차 문제 : boj14204 필요 알고리즘 그리디, 애드 혹 일반적인 풀이 유형이 없는 애드 혹 문제이다. 내 경우엔 그리디한 방식으로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 참고로 '행 우선 순서' 라는 말은 아래처럼 행으로 쭉 정렬되어있음을 뜻한다. 1 2 3 4 5 6 '열 우선 순서' 라면 아래와 같은 형태다. 1 3 5 2 4 6 처음엔 원래 있어야 할 위치 기준 맨허튼 거리를 공책에 써보니 나름 .. 2023. 7. 13.
[자바] 백준 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.
[ABC301] C - AtCoder Cards (AtCoder Beginner Contest 301 in Java) 목차 문제 : ABC301 - C 필요 알고리즘 그리디 그리디라고 하기 좀 애매하긴한데, 아무튼 바꿀 수 있으면 대충 바꾸는 로직으로 풀 수 있으므로 일단 그리디라 적었음. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 cnt 배열에 'a'부터 'z' 까지 S에 나온 문자만큼 +1, T에 나온 문자만큼 -1을 해주며 세줬다. 예를들어 S가 "ABC", T가 "BCD" 라면 cnt[0] = 1, cnt[1] = 0, cnt[2.. 2023. 5. 13.
[자바] 백준 27961 - 고양이는 많을수록 좋다 (java) 목차 문제 : boj27961 필요 알고리즘 그리디 0마리 이상 k마리 이하에 안낚이도록 그리디 규칙을 정할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주의해야하는 점은 복제 마법 부분이다. 0마리 이상 k마리 이하라고 했는데, k마리 복제하지 않는게 이득인 경우가 과연 있을까? 없다(갯수 안넘어가게 조절할 때 빼고). 즉 이 문제는 고양이를 1마리 늘리거나, 2배 늘릴 수 있을 때 최소의 행동을 구하는.. 2023. 4. 19.
[자바] 백준 16200 - 해커톤 (java) 목차 문제 : boj16200 필요 알고리즘 그리디, 정렬 그리디 규칙을 잘 생각해보면 의외로 쉽게 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 팀을 어떻게 정하는게 항상 최선의 선택일지 규칙을 정해야 한다. 얼핏 X값이 큰 학생들부터 골라서 선택해야 각 팀의 인원이 많아지므로 팀의 수가 줄어든다고 생각할 수 있는데, 어차피 X값은 고정된 것이고 바뀔 수 없으며, 모든 학생은 하나의 팀에 소속이 되어야만.. 2023. 4. 11.
[자바] 백준 7570 - 줄 세우기 (java) 목차 문제 : boj7570 필요 알고리즘 그리디 알고리즘 모든 경우에 적용되는 규칙을 적용해 푸는 그리디 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이게 특정 위치의 수를 원하는 위치로 보낼 수 있었으면 좀 쉬웠겠는데, 맨 앞이나 맨 뒤로만 보낼 수 있는 부분 때문에 좀 생각하기 어려워지는 것 같다. 내가 정한 규칙은, 가장 긴 +1씩 증가하는 부분 수열을 고정시키고 나머지 애들을 어떻게든 움직여보는 것이다... 2023. 3. 16.
[자바] 백준 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.