본문 바로가기

PS/BOJ752

백준 2331 자바 - 반복수열 (BOJ 2331 JAVA) 문제 : boj2331 무작정(brute force) 계속 D[n]을 구해나가면서 이전에 이미 나왔던 결과가 다시 나오는지 확인만 하면 된다. 이 때, 중복된 값은 해싱을 통해 찾으면 빠르게 찾을 수 있다. 추가로 중복값이 나왔을 때 해당값의 위치가 몇번째였는지를 알아야 남게되는 수들의 개수를 출력할 수 있다. 따라서 HashMap을 사용해서 이미 나왔던 수와 해당 수가 몇번째에 나왔는지를 기록해두면 이후 중복된 값이 계산되었을 때 바로 남은 수의 개수를 알 수 있다. (중복값이 나온 위치 이전의 모든 값들이 남은 수들이 된다.) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Hash.. 2022. 1. 9.
백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8.
백준 20949 자바 - 효정과 새 모니터 (BOJ 20949 JAVA) 문제 : boj20949 원하는 방식으로 정렬하는 방법만 알면 쉽게 풀 수 있는 문제이다. 이 문제의 경우 쿼리로 따지면 ORDER BY [W^2+H^2 값] DESC, IDX ASC 인 셈이다. 이 때 W^2+H^2은 W와 H가 모두 최대 3만이므로 두 합은 최대 18억으로, int형으로 표현 가능한 수치이다. 당연하게도 문제에서 square root가 있다고 루트 씌우고 계산하면 소수점 오차때문에 틀릴 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Monitor implements Co.. 2022. 1. 6.
백준 1298 자바 - 노트북의 주인을 찾아서 (BOJ 1298 JAVA) 문제 : boj1298 기본 형태의 이분매칭 문제이다. 그러니 푸는법을 모르겠다면 이분매칭에 대해 구글링해보면 풀 수 있다. 얼핏 이분 그래프가 아닌 것 같아 이분매칭을 적용하지 못한다고 생각할 수 있으나, 제시된 N이 결국 N명의 사람과 N개의 노트북 두개 모두를 뜻하므로 N개의 사람 정점과 N개의 노트북 정점이 이분 그래프를 이루게 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { StringTokenizer st; B.. 2022. 1. 6.
백준 2188 자바 - 축사 배정 (BOJ 2188 JAVA) 문제 : boj2188 완전 기본형태의 이분 매칭 문제이다. 이분 그래프임이 직관적으로 드러나므로 이분매칭 개념을 알고있다면 기본형 문제로 풀어볼만 하다. '예제 입력 1'을 그려보면 다음과 같다. 이분 매칭된 결과 중 최대로 매칭 시킬 수 있는 경우의 예시는 다음과 같다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { ArrayList[] edges; private int[] matched; private boolean[] .. 2022. 1. 5.
백준 1017 자바 - 소수 쌍 (BOJ 1017 JAVA) 문제 : boj1017 애초에 해결을 위한 키 아이디어도 일반적으로 찾기 쉽지 않을듯하고, 거기에 네트워크 플로우에서 이분 그래프의 최대 유량을 구하는 이분매칭 알고리즘에다가 소수 판정(에라토스테네스의 체)에다가 값 압축(이건 필수는 아님)까지 들어간 플래3에 손색이 없는 문제였다. 구현이 다소 복잡했어서 틀리면 예외찾을 엄두가 안났었는데 다행히 운좋게 한방에 통과했다. 오랜만에 한방에 통과한게 찐텐으로 기뻤다ㅋㅋ 1. 일단 브루트포스로 모든 경우를 살펴본다면 50C2번에 걸쳐 더해서 소수쌍이 되는걸 구하고, 모든 소수가 되는 쌍에 대해 모든 N개가 서로 겹치지 않고 선택되는 경우를 살펴야 한다. 대강 모든 쌍의 합이 소수가 된다면 O((50C2)!) 정도가 될 것이므로 통과할 수 없다. 서로 최대한 쌍.. 2022. 1. 4.
백준 18511 자바 - 큰 수 구성하기 (BOJ 18511 JAVA) 문제 : boj18511 N이 최대 1억이고, K의 각 원소는 1부터 9 까지이므로 어쨌든 8자리 수 이내로 모든 답이 나온다. 그리고 K는 최대 3개까지이므로 모든 경우를 봐도 최대 O(3^8) 이다. 따라서 따로 다른 방법 생각해볼 것 없이 브루트 포스로 풀면 된다. 약간의 백트래킹을 넣어서 예를들어 이미 N보다 큰 값이라면 더이상 볼 것 없이 종료하는 식으로 하면 된다. 백트래킹 개념을 넣지 않아도 시간내에 통과 가능한 간단한 문제이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private int max =.. 2022. 1. 3.
백준 10867 자바 - 중복 빼고 정렬하기 (BOJ 10867 JAVA) 문제 : boj10867 중복 제거만 하고 정렬만해도 풀 수 있는 간단한 문제이다. 해시로 중복체크하면서 list에 넣고 정렬 후 출력만 해줘도 된다. 또 다른 방법은 그냥 TreeSet에 넣으면 중복이 알아서 제거되므로 순서대로 꺼내면 된다. 내 경우엔 어차피 값이 -1000~1000 까지의 정수이므로 2000개짜리 배열에 어떤 수가 존재하는지 기입한다. 그럼 중복은 알아서 제거되고, 배열 순서대로 출력만 해주면 된다. 배열을 2001개 잡아두고 0~1000은 음수가, 그 이상은 양수가 사용하게 해도 되고, 그냥 음수 따로 양수 따로 1000개씩 배열을 만들어줘도 된다. 내 경우엔 후자로 진행했다. 예를들어 '-5 4 4 -1 -5 3 0'이 있고, 값이 -5~5 까지 가능했다고 한다면(그리기 쉽게) .. 2022. 1. 2.
백준 10465 자바 - Rolling Encryption (BOJ 10465 JAVA) 문제 : boj10465 1. 우선 문자열에서 k개를 그대로 출력한다. 이후 각 character마다 그 이전 k개의 문자열 중 가장 많이 나온 문자를 찾는다. 그리고 가장 많이 나온 문자(동일한 수가 나온게 있다면 알파벳에서 먼저 나오는걸로)만큼 쉬프트 시킨다(a면 1번, b면 2번, ..., z면 26번) 2. 문제만 보면 간단히 구할 수 있을 것 같은데, 문제는 k가 최대 10000이고 문자열의 길이가 최대 100000이므로 단순하게 각 character마다 이전 k개를 보게된다면 O(10000 * 100000)이 필요하므로 시간초과가 나게 된다. 이 경우 소문자는 총 26개이므로 별도 배열로 각 문자에 대해 세보면 더 효율적으로 가장 많이 나온 문자를 찾을 수 있다. "abbaabbac"에 대해 .. 2022. 1. 2.
백준 6588 자바 - 골드바흐의 추측 (BOJ 6588 JAVA) 문제 : boj6588 1. 홀수인 소수란 말은 그냥 2를 제외한 소수라는 의미이다. 2 말곤 전부 홀수인 소수이다. 아무튼 그러니 100만 이하의 소수를 모두 구해준다. 에라토스테네스의 체를 사용해 입력받기전에 미리 구해두면 각 케이스에 대해 해당 소수들을 써먹을 수 있으니 효율적이다. 그리고 여러 방법이 있겠으나, 시간복잡도를 좀 손해보더라도 편하게 코드를 짜기 위해 TreeSet에 찾은 소수를 넣어두었다. 시간 복잡도에 중점을 두려면 소수를 hashSet에 넣고, 추가로 소수 순서대로 배열에 넣어두면 된다. 어차피 시간이 널널한 문제라 뭘 쓰던 상관없다. TreeSet은 set이므로 a+b = n을 찾을 때 a가 정해지면 b가 존재하는지 contains(n-a)로 확인할 수 있다. 또한 hashSe.. 2022. 1. 1.

티스토리툴바