그리디90 [자바] 백준 25644 - 최대 상승 (java) 문제 : boj25644 필요 알고리즘 개념 그리디 매번 입력 중 최소값과, '현재값-최소값'의 최대값을 갱신하면서 모든 경우를 보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀 때 주의할점이, 문제의 조건이 '주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득' 이므로 딱 한번만 주식을 사야 한다는 점이다. 즉 입력이 '1 5 2 6' 일 경우 1에사고 5에 팔아서 4의 .. 2022. 9. 29. [자바] 백준 9440 - 숫자 더하기 (java) 문제 : boj9440 필요 알고리즘 개념 정렬 + 그리디 정렬을 통해 매번 낮은 수 부터 확인하는 그리디 개념으로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 가장 처리하기 까다로운 부분은 두 수가 0으로 시작하면 안된다는 점이다. 그러니 우선 입력값에 0이 없다고 생각하고 한번 생각해보자. 1,2,7,8이 있다면 두 수를 어떻게 정해야 할까? 중요한건 각 자리수에 어떤 수 2개를 사용할지이다... 2022. 9. 23. [자바] 백준 12993 - 이동3 (java) 문제 : boj12993 필요 알고리즘 개념 정수론, 수학 수학적인 사고가 약간 필요하다. 그리디 태그엔 없긴한데 내 경우엔 그리디 개념으로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 x, y 중 큰 값이 [3^a, 3^(a+1)) 일 때, k=a 부터 0까지 감소하면서 현재 남은 x와 y중 큰 값에 3^k를 그리디하게 빼준다. 최종적으로 x와 y 모두 0이 되면 1을 출력해주고, 아니면 0을 출력해준다.. 이 .. 2022. 9. 22. [자바] 백준 14572 - 스터디 그룹 (java) 문제 : boj14572 필요 알고리즘 개념 그리디 풀이를 보면 왜 그리디인지 알 수 있다! 투 포인터 (두 포인터) 이 문제의 경우 그리디 규칙을 적용시킬 때 투 포인터로 적용하는게 편하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 효율성 E를 구할 때 필요한 요소들을 하나씩 살펴보자. 1. 그룹 내의 학생들이 아는 모든 알고리즘의 수 -> 학생 수가 늘어나면 항상 동일하거나 늘어난다. 2. 그룹 내의 모든 학생들이 .. 2022. 9. 17. [자바] 백준 2873 - 롤러코스터 (java) 문제 : boj2873 필요 알고리즘 개념 구성적, 그리디 정규화된 방식 없이 이 문제만을 위한 규칙이 필요한 구성적 문제이다. 또한 그리디를 적용해 해당 규칙을 정할 수 있긴하다(?). 구현 보통 플래급에서 '구현'이 태그로 있다는건 구현이 엄청 어렵다는 뜻이다 ㅋㅋ ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 규칙자체는 여러 케이스에 대해 마구 그려보면서 머리로 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 문제는.. 2022. 9. 17. [자바] 백준 12933 - 오리 (java) 문제 : boj12933 필요 알고리즘 개념 그리디 찾을 수 있는 오리를 한마리씩 모두 찾아주는 규칙을 취하면 더 쉽게 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 이해가 다소 어려울 수 있는 문제이다. 사실 문제만 이해 잘 하면 그리 어렵지 않게 풀 수 있다. 그러니 여러 예시를 보면서 문제를 잘 이해해보자. 만약 '오리의 최대 마리수'를 찾는다고 생각해보자. 그럼 quackquackquack 에 대해.. 2022. 9. 13. [자바] 백준 24498 - blobnom (java) 문제 : boj24498 필요 알고리즘 개념 그리디 좀 생각해보면 그럴 수 밖에 없는 규칙이 보인다. 그 규칙대로 답을 구하면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음과 마지막이 아닌것 중 하나를 선택한다. 그럼 그 좌우는 -1, 중간은 +1이 된다. 그렇다면 각 위치가 서로 연관관계가 있을 수 있을까? 즉, 예를들어 1번째에 대해 문제에서 제시된 '행동'을 하고나서 2번째나 3번째에 대해 '행동'을 하는 .. 2022. 9. 6. [자바] 백준 25418 - 정수 a를 k로 만들기 (java) 문제 : boj25418 필요 알고리즘 개념 동적계획법(DP), 너비 우선 탐색(BFS), 탐욕법(greedy) DP, BFS, 그리디 정도가 풀이로 생각나는 문제이다. 셋 다 알아야 하는건 아니고, 셋 중 하나만 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 - DP 풀이 dp[x]를 x를 만들기 위한 최소 횟수로 정의하자. 그리고 dp[x]를 모두 무한대로(이 문제의 경우 나올 수 있는 최대수치가 .. 2022. 9. 4. [자바] 백준 1343 - 폴리오미노 (java) 문제 : boj1343 필요 알고리즘 개념 그리디 사전순으로 가장 앞서는 답을 출력해주기 위해, 각 연속된 X 집합들의 갯수를 기준으로 최대한 AAAA를 앞에 나오도록 해야 한다. 이런식으로 일정한 규칙을 정해 적용시키다보면 답이 나오는 그리디 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 '.'은 답을 구하는데 영향을 끼치지 않는다. 연속된 'X' 집합만 생각해보자. 다음을 생각해보자. ...XXXXXXXXXX... 2022. 8. 30. [자바] 프로그래머스 - 두 큐 합 같게 만들기 (Lv2, Java) 문제 : Programmers-두 큐 합 같게 만들기 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 그리디 어떠한 규칙을 정해, 해당 규칙대로 진행하다보면 답이 나오게 되는 그리디 유형의 문제이다. Queue FIFO (선입선출) 특징을 가지는 큐에 대한 개념이 있어야 구현할 수 있다. 두 큐에 들어있는 모든 값들의 합을 sum이라 하자. 결국 우리가 알고 싶은건 한쪽 큐의 합이 sum/2를 가지게 하는 최소 횟수이다. (sum이 홀수인 경우라면 불가능한 경우이니 -1을 출력하면 된다) 모든 경우를 우선 생각해보자. queue1에 들어있는 값들의 합을 s1, queue2의 모든 값들의 합을 s2라고 하겠다. 1.. 2022. 8. 28. 이전 1 2 3 4 5 6 7 ··· 9 다음
