본문 바로가기

그리디77

[자바] 백준 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.
[자바] 백준 18513 - 샘터 (java) 목차 문제 : boj18513 필요 알고리즘 개념 BFS (너비 우선 탐색) BFS로 풀 수 있는 문제이다. 논리는 약간 그리디에 가까운 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 샘터가 아래처럼 3개가 있다고 해보자. 당연하게도 샘터에서 가장 가까운 곳 부터 집을 두는 것이 이득일 것이다. 따라서 각 샘터에서 출발해 좌우로 퍼지면서 집을 지어주면 된다. 거리가 1 떨어진 집은 아래와 같다. 거리가 1 떨어진 .. 2023. 3. 3.
[자바] 백준 27315 - 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다 (java) 문제 : boj27315 필요 알고리즘 개념 그리디, 정렬 보통 그리디가 붙으면 나머지 태그들은 그리디 규칙을 적용시키기 위해 사용된다. 이번에도 마찬가지다! 매번 최선의 문제를 선택해나가면 문제를 풀 수 있고, 최선의 문제를 선택하기 위해 정렬이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 T와 E가 주어지지 않는다고 가정하고 생각해보자. 이 경우 간단한데, 매번 HD 이하의 D값을 가진 문제들 중에 P가.. 2023. 2. 17.
[자바] 백준 18310 - 안테나 (java) 문제 : boj18310 필요 알고리즘 개념 그리디, 정렬 그리디로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음엔 단순히 평균 구해서 평균과 가장 가까운 집을 선택하면 될 것이라 생각했다. 예제 입력 1도 그렇게 해보니 맞길래 그렇게 하니 당연히 틀렸다. 아래와 같은 경우, 평균으로 구하면 6.8 이므로 가장 가까운건 '6'이다. 그래서 '6'을 골라보면 차이의 합은 14이다. 하지만 실제론 9.. 2023. 2. 16.
[자바] 백준 18248 - 제야의 종 (java) 문제 : boj18248 필요 알고리즘 개념 정렬, 그리디 그리디라고 봐야할진 잘 모르겠다. 아무튼 규칙을 찾아 정렬해서 해결할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제를 이해하기 상당히 어려운 문제였던 것 같다. 결국 중요한건 N명의 사람이 종에서 특정 거리만큼 떨어져 있고, 그 위치가 바뀌지 않는다('타종이 진행되는 동안 사람들은 종소리에 집중하기 위해 움직이지 않는다')는 점이다. 그렇다면 이 문제.. 2023. 2. 15.
[자바] 백준 1448 - 삼각형 만들기 (java) 문제 : boj1448 필요 알고리즘 개념 그리디, 정렬 그리디로 접근해서 풀 수 있다. 수학 삼각형의 세 변을 이루는 규칙을 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 삼각형의 세 변을 이루는 규칙만 알면 풀 수 있다. 간단한데, 가장 긴 변이 있을 때 나머지 두 변의 합이 가장 긴 변의 길이보다 커야 한다. 아래 이미지를 보면 이해 가능할 것 같다. 그리고 이 문제에서 원하는건 '삼각형을 만들 수.. 2023. 2. 12.
[파이썬] 프로그래머스 - 과일 장수 (Lv1, Python) 문제 : Programmers-과일 장수 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 정렬, 그리디 그리디로 접근해서 풀 수 있다. 그리디 접근을 위해 정렬이 필요하다. 풀이 사과의 개수가 n개라고 해보자. 그렇다면 n%m 개 만큼은 버려져야 한다. 이 때 버려져야 하는 사과는 당연히 점수가 가장 낮은 사과들이다. 또한 이 문제는 m개씩 담은 상자에서 가장 점수가 낮은 사과를 기준으로 가격이 정해진다. 이 때 m개씩 짝지었을 때 낮은 사과가 가장 높게 나오는 방법은 내림차순으로 정렬 후 m개씩 고르는 방법이다(그리디). 위의 두 가지 모두 내림차순으로 정렬 후, m개씩 짝짓고 남는건 버리는 규칙에 부합한다. .. 2023. 2. 6.