본문 바로가기

Greedy79

[자바] 프로그래머스 - 두 큐 합 같게 만들기 (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.
[자바] 백준 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.
[자바] 백준 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.

티스토리툴바