PS/BOJ764 [자바] 백준 1241 - 머리 톡톡 (boj java) 문제 : boj1241 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유(글 링크) 이 글을 이해했다면 쉽게 풀 수 있다. N개를 입력받으면서 HashMap 등으로 각 숫자의 존재 여부 및 몇 개 존재하는지 저장해둔다. 이후 N개를 순회하면서 각각을 A라고 하면, 1부터 sqrt(A) 사이에 존재하는 A의 약수가 B라 하자. 그럼 HashMap에서 B의 개수를 더해주고, A/B도 약수일 것이므로 그것도 HashMap에서 찾아 더해주면 된다. 이 때 주의점은 sqrt(A)로 A가 나누어 떨어질 경우 (즉, (int)sqrt(A) * (int)sqrt(A) == A 인 경우), 두 번 더해지게 되므로 한 번은 빼줘야 한다. 그럼 시간복잡도는 N명 중 가장 큰 숫자가 K라 할 때, O(N.. 2022. 4. 28. [자바] 백준 19622 - 회의실 배정 3 (boj java) 문제 : boj19622 문제 읽으면서 와.. 이거 N이 25 이하 정도가 아니라면 힘들꺼같은데 이걸 어떻게 하지 생각하면서 읽어내려오니 역시나 '임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.' 이런 조건이 있었다. 그럼 그냥 dp로 쉽게 해결 가능하다. 결국 자신의 이전과 이후와 겹칠 수 없으므로, 방향을 입력이 주어지는 순서로 제한해보자면 결국 현재 회의를 개최하지 않는다면 이전 회의가 개최했던, 안했던 상관이 없다. 그리고 현재 회의를 개최하려면 이전 회의가 개최되지 않았어야 한다. dp 배열을 다음과 같이 정의하자. dp[i][0] -> i번째 회의를 개최하지 않을 경우 i번 회의까지의 최대 인원 dp[i].. 2022. 4. 28. [자바] 백준 5670 - 휴대폰 자판 (boj java) 문제 : boj5670 너무 대놓고 Trie 써야할것같이 생긴 문제였다. 사실 플래라곤 하지만 Trie 자료구조를 알고 있다면 별 문제 없이 풀 수 있는 기본 형태의 문제이다. 예를들어 'hello, hell, heaven, goodbye'를 Trie에 담아보면 다음과 같이 생겼다. 다음과 같이 소문자 하나씩 트리 구조로 유지하는 형태의 자료구조이다(주황색은 단어의 끝이 존재함을 의미한다.). 문자열 쪽으론 유명한 알고리즘이라 검색해보면 엄청 많이 나온다. 그럼 로직을 다음과 같이 구현하면 된다. 1. N개의 단어를 Trie 자료구조에 넣는다. 2. N개의 단어를 Trie 자료구조에서 찾으면서 주어진 조건에 따라 몇 번의 입력이 필요한지 센다. 3. '2'를 전부 더한다. 좀 더 효율적으로 하려면 1. .. 2022. 4. 27. [자바] 백준 10469 - 사이 나쁜 여왕들 (boj java) 문제 : boj10469 '*'이 나온 모든 위치에서 상하좌우, 대각선으로 퀸이 없으면 valid, 있다면 invalid인 간단한 구현 문제이다. 매번 '*' 위치에서 판의 끝까지 위,아래,좌우,대각선으로 탐색하면서 '*'이 있는지 확인하면 풀 수 있다. 하지만 그냥 매번 '*'의 위치에서 brute force로 직접 탐색하며 확인하긴 심심하니 난 내 수준에서 생각할 수 있는 가장 간단하게(짧게) 찾는 방법을 사용해 풀어봤다. 설명은 코드에 주석으로 달아두었다. 그리고 맞왜틀 나기 아주 좋은 함정이 있다. '사이나쁜 여왕 퀴즈는 여덟 여왕을 8x8 체스판 위에 배치' 여덟 여왕이랬으므로 '*'의 개수가 8개가 아니면 invalid이다. 코드 : github import java.io.BufferedRea.. 2022. 4. 27. [자바] 백준 11170 - 0의 개수 (boj java) 문제 : boj11170 최악의 경우가 N=0, M=1,000,000 일 경우이다. 이 때 0부터 1000000까지 하나씩 전부 0의 개수를 확인하더라도 O(1000000*8) 이면 된다(8은 자리수의 최대치). 따라서 그냥 N부터 M까지 하나씩 증가시켜보면서, 10으로 나눠가면서 1의자리가 0인 경우를 직접 세주면 된다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new.. 2022. 4. 26. [자바] 백준 15828 - Router (boj java) 문제 : boj15828 FIFO(first-in first-out)로 처리하면 되므로 우선 큐를 만든다. 그리고 큐에 데이터가 n개이상 존재한다면 무시하고, n개 이하라면 큐에 넣으면 된다. 그리고 0이 입력으로 들어오면 큐에서 빼주면 된다. 최종적으로 큐에 들어있는 순서대로 빼면서 출력해주면 답이 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; public class Main { private void solution() throws Exception { BufferedReader br = new Buffered.. 2022. 4. 25. [자바] 백준 14721 - 성적표 문제 : boj14721 뭔가 무서워 보이는 공식이 있지만, 그냥 문제에서 제시된 대로 구현만 해보면 된다. a와 b가 100 이하이므로 a를 1~100, b를 1~100 범위 내에서 모든 쌍을 확인하면서 rss를 계산하면 된다. 즉, 입력으로 x와 y가 주어지니, 모든 a,b 쌍에 대해 (y-(a*x+b))^2의 합의 최소치를 찾으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new Buffere.. 2022. 4. 24. [자바] 백준 10979 - 가넷이나 버는게 낫지 않아요? 문제 : boj10979 이하의 질문글을 보고 궁금해서 풀어보려다가 물렸다... 결국 31회의 시도로 개인 최장 시도횟수를 찍었고, 결국 뚫긴 했다. 10시간 넘게 걸렸다. 다른 분들 시도횟수까지 포함하면 자바 제출 시도 60회 만에 첫 통과이다 ㅋㅋㅋ 1. 자바로 풀 때 이 문제를 위한 메모리 최적화 일단 이게 자바로는 Scanner는 애초에 느려서 못쓰고, 많이들 사용하는 BufferdReader로 입력받는 순간 메모리 초과가 뜬다. 이게 BufferdReader가 미리 버퍼를 두고 더 많은 양을 미리 입력받아두기 때문에 그렇다. 일반적으로는 그정도론 문제가 없는데 이 문제는 메모리 제한이 너무 낮아 일단 그것만으로도 메모리 초과가 되는 것이다. BufferedReader 생성자 중 두 번째 para.. 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. 이전 1 ··· 48 49 50 51 52 53 54 ··· 77 다음
