본문 바로가기

PS/BOJ764

백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) 문제 : boj1450 1. 문제 접근 딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다. 1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다. 1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이.. 2022. 1. 22.
백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA) 문제 : boj2252 1. 그래프로 생각해보자. 이런식으로 A에서 B로 향한다던지, A와 B가 연관되었다든지 하면 일단 그래프로 생각해보는게 이해하기 편하다. 이 문제에서는 'A가 학생 B의 앞에 서야 한다'에 대해 A에서 B로의 간선을 긋는 방향 그래프로 생각해보자. 그럼 다음과 같은 경우를 보자. 5 3 1 2 2 3 4 5 위의 경우를 그래프로 나타내보면 다음과 같다. 위와 같은 경우는 간단하다. 이 문제의 경우 1->2->3을 먼저 가던지, 4->5를 먼저 가던지, 심지어 1->4->2->3->5 이렇게 가던지 상관없다. 서로 섞여있더라도 아무튼 모든 경우에서 A가 B보다 먼저 나오기만 하면 된다. 그렇다면 M개의 A, B를 입력받으면서, A에 나타났으면서 B에는 등장하지 않은 1과 4어디에서든.. 2022. 1. 21.
백준 2467 자바 - 용액 (BOJ 2467 JAVA) 문제 : boj2467 1. 당연히 모든 쌍을 확인해보면 O(N^2)이 걸릴 것이므로 통과가 불가하다. 이 문제는 투 포인터 알고리즘으로 풀 수 있는 기본형 문제이다. 또는 안풀어보긴 했으나 이분탐색으로도 문제없이 풀 수 있을 것 같다(N개를 TreeSet에 넣어둔 후 N개의 값을 순회하며 해당 값에 -1을 곱한 값에 대해 TreeSet에서 ceilling과 floor를 확인해 그 중 작은 수를 택하면 될 듯함). 2. 이미 정렬되어 들어온 데이터 이므로 정렬과정 필요 없이 첫번째 값을 s로 가르키고, 맨 뒤의 값을 e로 가르켜보자. 이제 s와 e가 가르키는 값을 합쳐가며 이 중 0과 가장 가까운 값을 찾으면 된다. s와 e를 변경하는 규칙은 다음과 같다. arr[s]+arr[e] == 0 -> 바로 출.. 2022. 1. 20.
백준 13547 자바 - 수열과 쿼리 5 (BOJ 13547 JAVA) 문제 : boj13547 문제에 비해 필요한 아이디어 및 구현과정은 상당히 복잡한 문제이므로 간단한 부분부터 차례대로 생각해보자. 1. 우선은 단건의 쿼리를 해결할 방법을 생각해보자. [Ai, Aj]에 존재하는 서로다른 수의 개수를 알 수 있어야 한다. 여러 방법이 있겠으나, 각 값을 표현할 메모리가 충분하다면 값의 최대 크기에 해당하는 배열을 만들어 해당 수가 나왔는지 체크하는 방법이 가장 효율적이다. 이 문제에서는 N개의 값 각각의 최대값은 1,000,000이므로 100만개짜리 boolean 배열만 있으면 된다. 100만개짜리 배열 arr이 있고, cnt라는 변수를 뒀다고 해보자. 각 쿼리에서 i와 j를 입력받았을 때 Ai부터 Aj까지 순회하며 배열에 체크한다. 이미 체크되어 있던게 아니라면 cnt를.. 2022. 1. 19.
백준 9753 자바 - 짝 곱 (BOJ 9753 JAVA) 문제 : boj9753 100000일 때 100001이 답이란걸 문제 예시에서 보여줬으므로 사실 100000이하의 소수 곱에 대해서만 신경쓰면 된다. 그리고 어차피 가장 작은 소수가 2 이므로 50000까지만 보면 된다. 따라서 5만 이하의 모든 소수를 우선 에라토스테네서의 체로 구한다. 그리고 소수의 곱을 모든 쌍을 보면서 모두 구한다. 이 때 10만이 넘어간다면 제외해도 된다. 구한 값은 어차피 10만까지만 알면 되므로 배열에 넣어도 되고, 내 경우엔 더 큰 수를 빨리 구해보려고 TreeSet에 넣었다. 이후 하나씩 입력받으면서 TreeSet의 ceiling을 출력하면 된다. '2'의 과정을 배열에 했다면 입력받은 값 이상을 순회하며 가장 작은 소수를 출력하면 된다. 코드 : github import.. 2022. 1. 18.
백준 10373 자바 - Buffcraft (BOJ 10373 JAVA) 문제 : boj10373 1. 문제 정의 상당히 문제가 불친절하다. 예제라도 의미 있을 예제를 들어주면 좋을텐데 ㅡㅡ; 상당히 별로인 문제이다. 1.1 'The following line must contain n different numbers', 'The last line of the output must contain m different numbers' 에 따라 출력을 해줘야 하는데, 그럼 following line이 0이라 출력할 게 없으면 줄을 띄워야 되나 말아야 하나라는 문제점이 있다(second, third line이라고 하던지.. 저렇게 하면 사실 following line이 last line이 되기도 하므로 애매하다.). 원래 문제대로라면 줄을 띄워야 맞지만(해당 대회 문제 채점 데이터.. 2022. 1. 17.
백준 8807 자바 - Przedziały (BOJ 8807 JAVA) 문제 : boj8807 1. 다음과 같은 입력을 생각해보자. 1 5 1 2 2 2 3 5 7 8 10 10 이 문제의 경우 만약 모든 범위를 한 선에 겹쳐그릴 수 있다면 쉽게 답을 구할 수 있을 것이다. 그럼 어떻게 각 범위를 합칠 수 있을지 생각해보면 된다. 우선 가장 간단한 방식으로, 모든 범위에 해당하는 배열을 만들고 입력을 받으며 범위를 채운 후, 마지막에 모든 범위에 대해 확인해서 개수를 세는걸 생각할 수 있다. 다만 이 문제의 경우 이렇게되면 모든 범위가 -10억~+10억이 되므로 모든 범위 확인만해도 대략 20초정도 걸린다. 2. 다른 방법을 생각해보자. 사실 각 A,B에 대해 범위를 순회만 해도 최대 20억번 해야하므로 시간초과가 확실하다. 따라서 아예 다른 방식으로 생각해봐야 한다. OR.. 2022. 1. 16.
백준 3518 자바 - 공백왕 빈-칸 (BOJ 3518 JAVA) 문제 : boj3518 문제는 참 직관적이고 간단한 구현문제인데, 생각보다 꾸현이 까다롭긴 하다. 나온 설명대로 문자열 파싱만 잘 하면 되서 딱히 알고리즘적으로 설명할 건 없다. 주의점은 좀 있다. 첫째로 다음과 같은 경우를 보자. abc def zzz ggg 이미 문제에서 제시된 방식되로 잘 배치되어 있지만, '사전순으로 가장 앞서는 것'을 출력해야 하므로 공백을 1칸으로 줄여야 한다. abc def zzz ggg 두번째로 각 출력문의 마지막에 추가 공백이 있으면 안된다. 딱 출력해야 되는 문장에서 추가 공백 없이 그것만 출력해야 된다. 그 이외에는 백준에서 '출력 형식이 잘못되었습니다'이 뜬다. 코드 : github import java.io.BufferedReader; import java.io.I.. 2022. 1. 15.
백준 17245 자바 - 히스토그램 (BOJ 17245 JAVA) 문제 : boj17245 일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해봤다. 1. 우선 높이(h)가 같거나 증가하는 경우이다. 이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다. 즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다. 2. 다음은 높이(h)가 감소하는 경우이다. 이번엔 좌측에서 우측으.. 2022. 1. 13.
백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12.

티스토리툴바