그리디92 [자바] 백준 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. [자바] 백준 25498 - 핸들 뭘로 하지 (java) 문제 : boj25498 필요 알고리즘 개념 그리디 알고리즘 각 트리 깊이마다 사전상 마지막에 오는 문자를 택하는 규칙을 세워야 한다. bfs, dfs 트리를 탐색하기 위해 bfs 혹은 dfs를 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 대회 당시에 규칙은 맞게 세워놓고 구현을 침착하게 안하다보니 엄청 틀렸었다 ㅠ. 어차피 트리이니 사이클이 없고, 루트 노드도 주어졌으므로 루트노드부터 시작해서 리프노드까지.. 2022. 8. 26. [자바] 백준 25496 - 장신구 명장 임스 (java) 문제 : boj25496 필요 알고리즘 개념 그리디 특정 규칙을 정해 매번 해당 규칙을 따라가면 결과가 구해지는 그리디 문제이다. 정렬 정렬 하는 방법을 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 백준 자바러의 전설 임스님이 만든 문제이다. 남은 피로도가 200-P가 있고, N개의 정수 Ai가 주어진다. 200-P의 피로도 내에서 가장 많은 Ai 들을 선택하면 된다. 어차피 Ai들마다 별다른 가중치 .. 2022. 8. 25. [자바] 백준 20207 - 달력 (java) 문제 : boj20207 필요 알고리즘 개념 그리디 매번 통하는 일정한 규칙을 정해서, 해당 규칙을 따르면 원하는 답을 구할 수 있는걸 말한다. 보통 엄밀히 증명되기 보다는 '이렇게 하면 될 것 같은데?' 라고 해서 시도해보고 맞는 경우가 많다. 딱히 방법이 정해진 알고리즘이 아니고, 개념적인 거니 알아야 풀 수 있고 그런건 아니다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제는 문제에서 제시된대로 시뮬레이션 문제.. 2022. 8. 12. [자바] 백준 24839 - Speed Typing (java) 문제 : boj24839 필요 알고리즘 개념 문자열 파싱 String을 character 단위로 볼 줄 알아야 한다. 그리디 알고리즘 (greedy) I의 모든 문자가 순서대로 P에 존재해야 하는지를 매번 '그리디하게' 확인한다. 두 포인터 (two pointer) I와 P의 시작점에 가상의 포인터를 하나씩 두고 양측이 점점 움직이면서 답을 찾아나가야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 I는 읽기 힘드므로,.. 2022. 7. 27. [자바] 백준 2195 - 문자열 복사 (boj java) 문제 : boj2195 p의 각 부분 문자열들에 대해 가장 s에 많이 포함되도록 골라주면 된다. 예를들어 예제 입력 1의 경우엔 다음과 같다. xy0z zzz0yyy0xxx 위의 경우로만 보면 헷갈릴수도 있으니 다음의 예시를 봐보자. abxyz abababxyzzz 위와 같이 p를 각 부분문자열로 나눴을 때의 각 부분문자열이 s에 가장 많이 포함되게 해주면 된다. 그럼 이 부분문자열 구간을 어떻게 나눌 수 있을까? 간단하게, p의 첫번째 문자부터 차례대로 보면서 s에 포함되어있는 최대 부분문자열까지 잘라내면 된다. 예를들어 위의 예제는 다음과 같이 진행된다. 1. abababxyzzz "a"는 s에 포함되므로 좀 더 봐보자. 2. abababxyzzz "ab"도 s에 포함되므로 좀 더 봐보자. 3. ab.. 2022. 7. 26. [자바] 백준 24524 - 아름다운 문자열 (boj java) 문제 : boj24524 'S 에서의 순서대로 이어 붙여' 부분이 가장 중요하다. 예제 입력 2번처럼 순서가 안맞으면 카운팅을 하면 안된다. 그럼 이걸 어떻게 알 수 있을까? 이하의 말로 설명한 로직을 생각해보자. 1. s의 각 문자열의 문자(character)를 처음부터 순서대로 확인하면서.. 2. 각 문자가 t에 존재하는 문자가 아니라면 무시한다. 3. 현재 s에서 보고 있는 문자를 c라고 하자. t에서 c가 나온 위치 직전의 문자를 bf라고 하자. 예를들어 c가 'a'이고, t가 "bac"라면 bf는 'b'이다. 이제 여기가 중요하다. 현재까지 s에서 나온 각 문자의 횟수를 cnt[] 라고 하자. 즉 c가 현재까지 나온 횟수는 cnt[c]이다. 이 때, cnt[c] >= cnt[bf] 라면, 현재 .. 2022. 7. 24. [코틀린, 자바] 백준 25214 - 크림 파스타 (boj kotlin java) 문제 : boj25214 매번 최소값과 최대값을 갱신한다고 생각해보자. 이 때 최소값이 갱신된 경우가 문제인데, 애초에 최소값이 갱신됬다고 i를 해당 값으로 선택하면 선택할 수 있는 j는 자기 자신밖에 없다(i cur) min = cur else ans = Math.max(ans, cur-min) sb.append(ans).append(' ') } println(sb) } 코드(java) : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { Buffered.. 2022. 7. 11. [자바] 백준 12034 - 김인천씨의 식료품가게 (Large) (boj java) 문제 : boj12034 정상가와, 정상가의 75%인 할인가가 n 쌍 존재한다. 그리고 문제 조건으로 '정답은 단 하나만 존재하는것이 보장되어 있음'라고 했으므로 정답을 찾으려면 단순히 생각해서 모든 경우를 살펴봐서 그 중 모든 정상가-할인가 쌍이 맞아떨어지는 경우를 찾으면 될 것이다. 하지만 잘 생각해보면 결국 할인가는 정상가보다 언제나 클 것이다. 따라서 주어진 값들 중 가장 큰 값은 할인가가 될 수 없으며 무조건 정상가이다. 따라서, 큰 값부터 정상가로 생각해 할인가를 찾아나갈 경우, 매번 남은 값들 중 가장 큰 값은 정상가일 수 밖에 없다. 정리하자면 오름차순으로 입력이 들어오므로, 마지막 값부터 시작해서 점차적으로 내려오면서 아직 존재하는 값이라면 무조건 정상가이고, 해당 값과 그 할인가를 제외.. 2022. 6. 23. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
