본문 바로가기

백준756

백준 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.
백준 14248 자바 - 점프 점프 (BOJ 14248 JAVA) 문제 : boj14248 문제 자체의 정의에 따라 i번째 정점에서 i-Ai, i+Ai 로의 간선이 생긴다. 이에 대해 단순히 방문 가능한 위치만 찾으면 되므로 dfs 혹은 bfs로 더이상 진행 불가할때까지 진행해보면서 방문한 곳의 개수를 세면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { boolean[] v; int cnt = 0, n; int[] arr; private void dfs(int s) { if (sn||v[s]) return; v[s] = true; cnt++; dfs(s+arr[s]); dfs(.. 2022. 1. 11.
백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA) 문제 : boj11060 N이 1000까지이고, Ai가 최대 100이라 대충 돌려도 O(NA = 100000) 이라 널널한 문제이다. 가장 좌측지점부터 시작해서 dp 개념을 살짝 섞은 브루트포스로 풀면 된다. 각 입력값에서 갈 수 있는 모든 곳을 가보면서 최소로 갈 수 있는 수치로 갱신해가면 된다. dp[x]는 x위치까지 갈 수 있는 최소 점프 횟수가 된다. 점화식은 Ai에서 i=x에서 시작해 우측으로 이동한 경우이고 현재 y (x+1 2022. 1. 10.
백준 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.

티스토리툴바