전체 글
-
[백준 2437번] 저울 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 11. 18:00
백준알고리즘 2437번 : 저울 이런 Greedy Algorithm 문제가 Algorithm Test를 준비하기 위한 문제인 동시에 매몰 당하지 않아야하는 문제인것 같다. Test에 유용한 문제인 이유는 특정한 수학적 공식을 알지 못하면 풀기 몹시 어렵기 때문이고 ㄱ매몰 당하지 않아야하는 문제인 이유도 위와 동일하다. 바꿔말하면 공식을 알기만 하면 쉽게 풀리기 때문에.. 고민하는 데 많은 시간을 쏟는게 좀 허탈하게 느껴지기도 했다. 그래도 개중에는 많은 고민을 거듭한 끝에 수학적 규칙을 간파하는 사람이 있을것이기 때문에, 내가 아직 그런 경지에 이르지 못한 것을 탓해야겠다. 결과적으로 필요한 공식은 'a1=1이고, a(n+1) > S(n)+1일 때 측정할 수 없는 최소값은 S(n)+1이다.' a(n)이 ..
-
[백준 1783번] 병든 나이트 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 11. 00:44
백준알고리즘 1783번 : 병든 나이트 처음 보았을 때 조금 까다롭게 느껴졌는데, 규칙을 찬찬히 쪼개면서 생각해보니 어렵지 않게 풀렸다. 드물게 switch~case문을 사용하기에 적합한 문제였던 것으로 보인다. 풀이 과정 1. 나이트는 오른쪽으로만 간다. 2. 나이트는 위아래로 2칸이내에서만 움직이므로, 세로길이가 3이상이면 모든 이동방법을 사용할 수 있다. 3. 이동 횟수가 4이상(가로칸이 5이상)이라면 이동 방법을 모두 한번씩 사용해야하므로, 가로길이가 7이상이면 적어도 2 번은 오른쪽으로 2칸씩 이동해야한다. 4. 2번 3번 규칙에 입각하여, 세로길이(N)가 3이상이고 가로길이(M)가 7이상이라면, 나이트의 방문 최댓값은 M-2이 될것이다. 5. 세로길이가 3이상이고, 가로길이가 4이상 6이하면 ..
-
[백준 2812번] 크게 만들기 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 10. 17:45
백준알고리즘 2812번 : 크게 만들기 역시 그리디 알고리즘은 어떻게 풀지 구상하는 것이 실마리의 절반 이상을 차지하는 것 같다. 엄청 애먹었지만 풀이 방식을 몇번 뒤엎은 끝에 stack을 이용해서 문제 해결에 성공했다. 처음 풀었을 때는 '지워야 하는 숫자의 갯수를 기억함과 더불어 check가 필요한 남은 숫자도 기억해야 하는게 아닌가?' 라고 생각했다. 이런 생각을 가지고 풀다보니 지워야하는 숫자와, 남은 문자열의 길이를 함께 계산하여 무지막지한 소스가 완성되었고 뻘짓을 4시간가량 반복했다. 결과적으로는 남은 문자열의 길이는 크게 신경쓸 필요 없으며, 판단해야하는 것은 두가지 뿐이다. 1. 지워야 하는 숫자의 개수를 먼저 소진했는가? 2. 지워야 하는 숫자가 아직 남았는가? 이 조건만 check하고 ..
-
[백준 1213번] 팰린드룸 만들기(Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 4. 14:27
백준알고리즘 1213번 : 팰린드룸 만들기 팰린드롬이란 회문, 즉 거꾸로 읽어도 같은 말이 되는 단어 혹은 문장을 말한다. 단어가 주어졌을 때 사전순으로 앞서는 팰린드롬을 만들고, 만들 수 없다고 판단되면 오류 메시지를 출력하는 문제이다. 단어가 홀수인 경우와 짝수인 경우로 나누어 풀었다. 풀이 과정 1. 사전순으로 출력되게 해야하므로, 배열을 받아 정렬한다. 2. 짝수인 경우에는 for문을 돌며 i번째와 i+1번째를 비교하여 StringBuilder로 append함과 동시에 Stack에 push를 하고 두 문자가 다른 경우에는 즉시 오류 처리하며 종료하도록 했다. 오류 처리가 되지 않은 경우에는 append한 String 값에 stack을 pop하여 단어를 추가 append하여 출력하도록하였다. 3. ..
-
[백준 2847번] 게임을 만든 동준이(Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 1. 00:44
백준알고리즘 2847번 : 게임을 만든 동준이 받아온 값들을 동일한 점수가 없는 오름차순으로 만드는 문제이다. Greedy Algorithm 응용 문제를 하면서 정렬을 수행하는 것에 익숙해졌는지 냅다 정렬을 하는 실수를 범했다. 순서대로 배열로 받아 가장 마지막부터 탐색하며 깎아야 하는 숫자를 count하여 풀 수 있었다. 풀이 과정 1. 점수들을 레벨의 수 N만큼 배열로 받는다. 2. 배열을 뒤에서부터 탐색한다. 하위 level의 점수가 상위 level의 점수보다 크면 해당 점수를 깎아서 기준 점수를 재정의한다. 3. 깎은 점수의 총 합을 출력한다. 소스 ▽ 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..
-
[백준 1202번] 보석 도둑(Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 28. 16:47
백준알고리즘 1202번 : 보석 도둑 시간 초과와 RunTime Error를 반복한 끝에 성공했다. 우선순위큐(Priority Queue)의 중요성을 배운 문제이다. 이중for문(혹은 for문과 while문)을 사용하게 된다면 최대 30만*30만의 시간복잡도가 발생하게된다. 따라서 가방의 최대 무게외 보석의 정보 배열을 정렬했다고 하더라도 시간 제한이 걸리는 testCase가 발생하기 때문에.. 이 방식은 한 번 해보고 빠르게 접었다. 우선순위큐의 장점은, 내가 add한 Queue 중 최대값(혹은 최소값)을 poll할 수 있다는 점이다. 이는 인자들을 꾸준히 더하거나 빼야하는 상황이나 (특정 가방이 들수 있는 보석들을 모두 담고, 하나의 보석만 빼고 남겨둬야한다.) 인자들의 최대, 최소값을 구해야하는 상..
-
[백준 1543번] 문서 검색(Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 23. 13:39
백준알고리즘 1543번 : 문서 검색 문서내에 특정 단어가 몇번이나 등장하는지 출력하는 문제이다. 처음에는 이중 for문을 사용하지 않고, 단일 for문을 이용하여 첫 글자부터 하나씩 check한 뒤에 한 글자라도 틀리면 다시 첫 글자부터 돌아가서 check하는 방식을 취했는데, 이러한 방식에는 문제가 있었다. 예를들어 단어의 길이가 길고, 뒷부분에서 틀린 글자가 발견되어 다시 첫글자부터 count를 하게되면, 문서내에 해당 단어의 패턴이 있었다고 하더라도 count를 못하게되어 찾지 못하는 불상사가 일어나게 된다. 예시로 abaabaa abaa 가 그렇다. 따라서 문서의 길이와 단어의 길이의 최댓값을 고려해도 이중 for문으로 풀어도 괜찮겠다 싶어 푸는 방식을 변경하였다. 풀이 과정 1. 이중 for문..
-
[백준 1449번] 수리공 항승 (Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 22. 16:39
백준알고리즘 1449번 : 수리공 항승 필요한 테이프의 갯수를 출력하는 문제이다. 어차피 구멍을 왼쪽부터 정렬하게되면, 무조건 왼쪽부터 커버해야하기 때문에 문제가 한결 쉬워질 것이라고 판단했다. 풀이 과정 1. 구멍의 위치를 오름차순으로 정렬한다. 2. 남아있는 테이프의 위치(왼쪽 끝, 오른쪽 끝)를 확인하고, 앞, 뒤를 다 커버가능한지 매번 체크하도록 한다 3. 커버가 불가능하다면 테이프 갯수를 하나 더 늘이고, 테이프가 커버할수 있는 위치를 초기화한다. 소스 ▽ 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.u..