본문 바로가기

BOJ737

백준 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.
백준 10819 자바 - 차이를 최대로 (BOJ 10819 JAVA) 문제 : boj10819 N이 최대 8밖에 안된다. 8개의 수로 만들 수 있는 모든 경우를 확인해봐도 O(N!) 이므로 그냥 모든 경우를 확인해보면 된다. 재귀나 스택을 사용한 dfs로 짜면 완전탐색(=brute force)을 쉽게 짤 수 있다. 단순 반복문으로 짜려고 하면 최대 8중첩 반복문이 필요하다 ㅋㅋ 재귀에 익숙치 않다면 방문체크가 어려울 수 있다. 다음 수를 선택하기 전에(내부에서 dfs를 다시 부르면서 cnt+1 해주는 부분이 다음 수를 선택하기 위한 부분이다.) 방문체크를 하고, 반환된 후에 다시 방문체크를 해제해줘야 모든 경우를 볼 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; impor.. 2022. 1. 1.
백준 2491 자바 - 수열 (BOJ 2491 JAVA) 문제 : boj2491 1. 연속해서 커지는 경우(같은 것 포함)만 일단 생각해보자. 주어지는 N개의 숫자에 대해서, 숫자가 작아진 경우 카운팅을 1로 되돌려보자. 그럼 다음과 같이 증가(같은 것 포함)하는 경우에 대해 각 구간에서 얼마나 긴 길이를 가지는지 알 수 있다. 2. 그럼 감소하는 경우도 마찬가지다. 값이 이전보다 커지는 경우 카운팅을 1로 되돌리면서 계속 세어나가면 된다. 이 문제의 경우엔 커지거나, 작아지는 수열 중 답을 구해야한다. 하지만 다를건 없다 그냥 하나씩 입력받으면서 증가하는 경우의 카운팅과, 감소하는 경우의 카운팅을 따로따로 해주면 된다. 한번에 세지 못하고 따로따로 세줘야 하는 이유는, 모든 수가 동일한 구간이 포함된 경우 (e.g. '1 1 1 1 1 1')를 제대로 판단하.. 2021. 12. 31.
백준 2225 자바 - 합분해 (BOJ 2225 JAVA) 문제 : boj2225 1. 0부터 N까지에서 '0부터' 부분 때문에 좀 헷갈렸다. '덧셈의 순서가 바뀐 경우는 다른 경우로 센다' 라는 부분 때문에, 예를들어서 N이 1이라 해도 K가 5라면 1+0+0+0+0 / 0+1+0+0+0 / ... / 0+0+0+0+1 이 가능해진다 ㅋㅋㅋ 0의 더하는 순서라니 인지적으로는 좀 이상하긴 하지만, 사실 문제 푸는데는 상관없다! '2'를 보면 알겠지만, 그냥 1부터 N까지라고 해도 점화식이 달라질 뿐이다. 2. K-1개의 수를 합해 만든 어떠한 값이 있다. 이 값에 0부터 N까지의 정수를 더한다면 K-1개의 수로 만든 합에 1개의 정수를 더 더한 것이므로, K개의 수를 사용해 만든 어떠한 합이 될 것이다. 그렇다면 0부터 N까지의 정수를 사용해서, X개의 수를 합.. 2021. 12. 30.

티스토리툴바