전체 글1104 [자바] 백준 10979 - 가넷이나 버는게 낫지 않아요? 문제 : boj10979 이하의 질문글을 보고 궁금해서 풀어보려다가 물렸다... 결국 31회의 시도로 개인 최장 시도횟수를 찍었고, 결국 뚫긴 했다. 10시간 넘게 걸렸다. 다른 분들 시도횟수까지 포함하면 자바 제출 시도 60회 만에 첫 통과이다 ㅋㅋㅋ 1. 자바로 풀 때 이 문제를 위한 메모리 최적화 일단 이게 자바로는 Scanner는 애초에 느려서 못쓰고, 많이들 사용하는 BufferdReader로 입력받는 순간 메모리 초과가 뜬다. 이게 BufferdReader가 미리 버퍼를 두고 더 많은 양을 미리 입력받아두기 때문에 그렇다. 일반적으로는 그정도론 문제가 없는데 이 문제는 메모리 제한이 너무 낮아 일단 그것만으로도 메모리 초과가 되는 것이다. BufferedReader 생성자 중 두 번째 para.. 2022. 4. 23. 백준에서 자바로 풀려면 난이도가 매우 상승하는 문제들 발견할 때 마다 추가예정! 아는거 있는분은 알려주세요. 1. Transform the String (boj23716) 이유 - 메모리 초과 로직 자체는 브론즈라 별거 없는데, 문제는 입력받은걸 character로 유지하면 메모리 초과가 된다 ㅋㅋㅋ 즉, BufferedReader나 Scanner로 String으로 입력받으면 메모리 초과 뜬다. 2byte인 character 대신 1byte인 byte로 입력받아야 한다. 즉, 직접 DataInputStream 같은 좀 더 low한 입력 클래스로 한땀한땀 byte로 입력을 받아줘야 한다. 2. 전설 (boj19585) 이유 - 좀 더 최적화된 로직을 요구함 이건 풀이 로직에 따라 고수분이 하면 자바로 딱히 어렵다는 생각 안들고 뚫을 수도 있긴하다. 이 문제에.. 2022. 4. 23. [자바] 백준 1854 - K번째 최단경로 찾기 문제 : boj1854 다익스트라에 대한 이해를 높히고 으용하는데 매우 도움되는 문제이다. 강추! (플로이드 와샬 이해에는 23258번 밤편지 강추) 다른 문제 풀다가 2번째 최단경로를 찾아야 하는 경우가 있어 찾아보다가 이 문제도 풀게됬다. 다익스트라를 돌릴 때 1부터 n까지 가는 최소 가중치를 알려고 한다고 해보자. 이 때, n번에 처음 도착 했을 때 바로 답을 출력하면 될까? 가중치가 동일한 bfs와 달리 다익스트라는 가중치가 있을 때 사용하기 때문에 그러면 안된다. 다익스트라는 priority queue가 빌 때 까지 다 해봐야 답이 나온다. 그럼 2번째로 작은 가중치를 가지는 경로를 어떻게 구할 수 있을까? 어떠한 정점에 도달한 기록을 2개 유지하면 된다. 물론 이 때에도 마찬가지로 원하는 위치.. 2022. 4. 23. [자바] 백준 9842 - Prime 문제 : boj9842 에라토스테네스의 체로 10000번째 소수를 구할 만큼 큰 수까지의 모든 소수를 구한 후 입력받은 n번째 소수를 출력해주면 된다. 이 때, 10000번째 소수는 104,729이다. 어떻게 알았냐면 대충 15만으로 두고 돌려보니 104729까지였다.(!) 코드 : github(java) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { private static final int LIMIT = 104729; ArrayList pn = new ArrayList(); private void initPn() { boolean[] isPn =.. 2022. 4. 22. [자바] 프로그래머스 - 도둑질 (코딩테스트 연습 Lv4) 문제 : Programmers-도둑질 레벨 4라 보기엔 프로그래머스의 다른 레벨4 문제에 비해 너무 쉽다. DP가 개인적으로 내 최대 약점이라 생각하는데도 금방 점화식이 생각날 정도니 2~3정도가 적당할 것 같다. 레벨4 스킬 체크 딸 때 이거 나왔으면 더 꿀이었을 것 같다. 일단 점화식은 간단하다. dp[i]를 i번 집을 털 때 얻을 수 있는 최대 돈이라 하면 아래와 같이 세울 수 있다. 즉, 현재 i번 집을 털 때 얻을 수 있는 최대 돈은, 이전집을 털고 현재집을 털지 않는것과 이전으로 2번째 집을 털고 이번 집도 터는 것 중 max값을 선택하면 된다. 이렇게 하면 '100 1 1 100' 처럼 중간에 두 집을 건너띄고 털어야 하는 것 까지 한번에 해결된다(세 집을 건너띄는 경우는 없다. 그 경우라면.. 2022. 4. 21. 백준 11008 자바 - 복붙의 달인 (boj 11008 java) 문제 : boj11008 문제가 명확하지 않아 별로인 문제였다. 예를들어 p가 'bana'이고, s가 'babanana' 일 경우, 이 문제는 'babanana' 중간의 bana 하나만 복붙하고, 나머지 4개는 별도로 출력하여 5가 답이다. 하지만 bana를 복붙 후, 중간에서 bana를 또 붙여넣기하면 2번인걸! 이런 부분에 대한 조건이 제시되어 있지 않았고 그냥 대충 이런거 처리 안하는걸로 제출하니 통과됐다. 좀 아쉽다. 아무튼 그냥 s에서 p가 나온 부분을 세주고, 나머지 부분을 세면 된다. 좀 간단하게 처리하려면 이하 코드처럼 s에서 p를 replaceAll로 전부 문제에 제시될 수 없는 character로 변경해 준 뒤 s의 길이를 출력해주면 된다. 코드 : github import java.i.. 2022. 4. 21. 백준 15738 자바 - 뒤집기 (boj 15738 java) 문제 : boj15738 풀이 첫 줄에 강력한 스포가 있다. 혹시 아직 못 풀어서 이걸 어떻게 풀지? 생각되어 풀이를 봤다면, 이하 풀이를 보면 많이 짜증날 수 있으니 다시 한번 문제를 잘 읽어보고 직접 도전해보는걸 추천한다. ------- 풀이 : 애초에 배열 A가 아무런 의미가 없다 ㅋㅋㅋ 그냥 입력받은 n과 k만 가지고 각 m개의 연산에 따라 사칙연산으로 k의 위치만 바꿔주면 된다. A. i가 양수일 때 i 그리고 i-k+1로 k를 변경해주면 된다. B. i가 음수일 때 n+i+1 까지 영향을 끼치므로, 그보다 k가 작다면 무시하면 된다. -> 그리고 2*n-k+i+1로 k를 변경해주면 된다! 따라서 시간복잡도는 O(M)이다. N은 아무런 영향을 끼치지 않는다. 이.. 2022. 4. 20. 백준 1940 자바 - 주몽 (boj 1940 java) 문제 : boj1940 고유한 번호를 a라고 할 때, 결국 알아야 하는 것은 n개의 a에 대해 현재 보고 있는 a값을 기준으로 m-a가 n개 중에 존재하는지만 알 수 있으면 된다. 따라서 HashSet을 사용하면 쉽게 풀 수 있다. 이 때, 만약 '고유한 번호'가 아니라 중복되는 것이었다면 HashMap으로 개수도 체크해야 했을 것이다. 로직은 그럼 다음과 같다. A. N개를 입력받으면서 HashSet에 넣는다. B. N개를 순회하면서 m-a가 HashSet에 존재하는지 확인한다. 존재한다면 카운트를 +1 시킨다. C. 이 때 m이 짝수이고 m/2인 값이 존재한다면 m-a == a 이므로 이 경우는 빼야하니 카운트 -1 시킨다. D. 최종적으로 중복된 경우를 빼기 위해 카운트/2를 해서 출력해주면 된다... 2022. 4. 19. 코드업 4040 자바 - 펜션 (CodeUp 4040 java) 문제 : CodeUp4040 어차피 중간에 하루라도 지낼 수 없다면 조건이 만족되지 않는다. 따라서 s부터 시작해서 매번 가장 길게 지낼 수 있는 방에서 지내면 된다. 그러다가 지낼 수 없는 날이 되면 -1, t 이상이 됬다면 변경 횟수를 출력하면 된다. 증명은 간단한데, 매번 가장 길게 지낼 수 있는 방이 아닌 다른 곳에 묵었을 때 더 이득이 되는 경우가 있다면 위의 추론이 틀린 것이다. 하지만 더 짧은 기간 지낼 수 있는 방을 고르더라도 동일한 변경횟수까진 나와서 더 낮은 변경 횟수가 될 수 없음은 직관적으로 알 수 있다. 따라서 그리디하게 선택하면 된다. 그럼 해당하는 날에 어느 방이 가장 길게 묶을 수 있는 방인지 어떻게 알 수 있을까? 이건 날을 거꾸로 진행하면서 몇 일을 지낼 수 있는지 pre.. 2022. 4. 18. [자바] 프로그래머스 - 타겟 넘버 (코딩테스트 연습 Lv2) 문제 : Programmers-타겟넘버 결국 주어진 numbers를 순서대로 + 한번, - 한번씩 모든 경우를 구해보면 된다. 이 경우 O(2^n)이 된다(+,-의 2가지 경우를 n번 봐야 하므로). 예를들어 numbers가 [1, 2, 3]일 경우 다음과 같이 진행된다. 이 중 target과 동일한 경우를 세서 return해주면 된다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges */ class Solution { int cnt = 0; private void rec(int[] numbers, int target, int idx, int sum) { if (idx == numbers.length.. 2022. 4. 18. 이전 1 ··· 76 77 78 79 80 81 82 ··· 111 다음
