본문 바로가기

전체 글1104

[자바] 백준 6318 - Box of Bricks (boj java) 문제 : boj6318 입력으로 들어온 n개의 hi의 합이 n으로 나누어 떨어진다고 했으므로, 잘 생각해보면 결국 모두 동일한 높이인 sum(hi)/n 으로 맞춰줘야 한다. 즉, sum(hi)/n 보다 큰 hi들에서 하나씩 빼서 sum(hi)/n 미만의 hi들에 더해줘야 한다. 이 말은 다시 말해, n개의 hi들에 대해 이하의 값을 구하면 된다. 여기서 hi_k는 k번째 hi 값을 의미하고, sum(hi)/n은 n개의 hi값의 합을 n으로 나눈 값이다(나누어 떨어진다는 조건이 있으므로 정수). 말로 설명하면, sum(hi)/n보다 큰 hi값을 초과한 값 부분만 다 더해주면 답이 된다. 코드 : github import java.io.BufferedReader; import java.io.IOExcepti.. 2022. 5. 31.
[자바] 백준 9715 - 면적 구하기 (boj java) 문제 : boj9715 이하의 예시를 확인해보자. 2 3 312 103 그림으로 그려보면 아래와 같다. 면적, 즉 다른 상자에 닿아있지 않고 공기(?)와 닿아있는 면의 수를 세면 될 것이다. 우선 어떻게 해야 면적을 구할 수 있을지 생각해보자. 우선 가장 간단한 바닥에서 위로 본 형태와, 위에서 바닥쪽으로 본 형태부터 생각해보자. 둘 다 아래와 같이 2차원 평면의 형태로 보일 것이다. 따라서 0이 아닌 위치라면 면은 항상 +2를 해주면 된다(바닥 하나 뚜껑 하나). 그럼 이제 동서남북 4개의 방향에서 공기와 닿아있는 면을 세주면 된다. 우측에서 좌측으로 보는 경우를 한번 생각해보자. 아래 그림과 같은 방향이다. 설명을 돕기 위해 판이 하나 이동하면서 본다고 해보면, 아래와 같은 두 가지 부분에서 면이 공.. 2022. 5. 31.
[자바] 백준 15881 - Pen Pineapple Apple Pen (boj java) 문제 : boj15881 아무튼 'pPAp'의 개수만 세면 되는 문제이다. 겹칠여지도 없으니 문자열만 잘 찾아주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final String PPAP = "pPAp"; private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String s = br.readLine(); int cn.. 2022. 5. 30.
[자바] 백준 1867 - 돌멩이 제거 (boj java) 문제 : boj1867 Minimum Vertex Cover 문제이다. 즉, 최소한의 정점만을 선택했을 때, 모든 간선들이 양 끝점 중 하나는 선택된 정점이어야 한다. 이 문제의 경우 열 번호와 행 번호를 각각 정점으로 두고, 돌멩이가 존재하는 위치를 간선으로 두자. 그럼 예제 입력 1의 경우 다음과 같이 그래프로 변경해볼 수 있다. 3 4 1 1 1 3 2 2 3 2 이 때 Minimum Vertext Cover는 다음과 같다. 이 때, 행과 열에 대해 이분그래프로 나타낼 수 있으므로 쾨니그의 정리(위키)를 적용해볼 수 있다. 복잡하게 써있지만 결론은 이분그래프에서 Minimum Vertext Cover는 이분 그래프의 최대유량 문제와 동일하다는 의미이다. 이분그래프의 최대유량이므로 이분 매칭(MIT .. 2022. 5. 30.
[자바] 백준 12780 - 원피스 (boj java) 문제 : boj12780 H에서 N이 몇 번 나오면 되는지 확인하면 된다. 이 때 명확하지 않은 점이 예를들어 아래와 같은 경우, 2번이 답이 될지 3번이 답이 될지였다. 애초에 문제로 파악할 수 없었으므로 그냥 제출해보고 틀리면 변경하려 했다. 결론은 후자가 맞았다. AAAA AA 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String a = .. 2022. 5. 29.
[자바] 백준 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 (boj java) 문제 : boj24480 내림차순으로 다음 정점을 선택해야 한다. 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 될 것이다. 그러니 인접 리스트로 간선을 표현하자. 이 때 내림차순으로 다음 정점을 선택해야 하므로, 미리 내림차순으로 각 정점의 간선들을 정렬시켜두면 된다. 혹은 Priority Queue 등을 사용해 다음 정점을 저장해둬도 될 것이다. 위의 내용 이외에는 기본 DFS로 구현하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util... 2022. 5. 28.
[자바] 백준 2559 - 수열 (boj java) 문제 : boj2559 이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다. 1. 누적합 (prefix sum) prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라고 하고, sumArr[i]는 arr[1]+arr[2]+...+arr[i] 라고 하자. 그렇다면 sumArr[i] = arr[i] + sumArr[i-1]이 될 것이다. 이렇게 누적합 배열을 구해둔다면, 이후 아래의 공식을 통해 각각 O(1)로 arr[i]부터 이전 K개의 합을 구할 수 있다. 따라서 O(N)으로 답을 구할 수 있다. 코드1 : github - prefix sum import java.io.BufferedReader; import java.io.In.. 2022. 5. 27.
[자바] 백준 1671 - 상어의 저녁식사 (boj java) 문제 : boj1671 문제에서 제시된 상황이 그래프로 표현 가능한 경우 그래프로 바꿔서 생각해보는 것이 이득인 경우가 많다. 이 문제의 경우에도 주어진건 상어의 크기, 속도, 지능으로 3개나 되지만, 사실 그래프의 간선으로 생각해본다면 값이야 어떻든 조건을 만족한 경우 그냥 방향이 있는 간선 하나가 추가될 뿐이다. 예시 입력 1을 그려보면 다음과 같다. 간선은 [먹는쪽 -> 먹히는쪽]으로 연결할 것이다. 5 4 5 5 10 10 8 5 7 10 8 7 7 8 10 3 그럼 동일 정점을 좌우로 둬서 다음과 같이도 그려볼 수 있다. 결국 최대한 많이 잡아먹으면 남아 있는 수가 최소가 되므로, 최대유량 문제인데 이분그래프 이므로 이분매칭을 사용해서 좌측의 상어가 우측의 상어를 먹는다고 생각해보자. 그리고 좌.. 2022. 5. 26.
인텔리제이 StringTokenizer - NoSuchElementException 문제 해결 방법 (IntelliJ 2022.1.1) 인텔리제이를 현재 기준 가장 최신버전인 2022.1.1로 업데이트 시, StringTokenizer가 정상적으로 동작하지 않는다. 복사-붙여넣기를 하면 동작하지만 직접 작성 시 아래와 같은 에러가 뜬다. 일반적으로 잘 사용하는 클래스는 아니지만, 알고리즘 문제를 푸는 사람들이라면 상당히 난감한 상황이다(인텔리제이 2022.1.1에서만 그렇고, 자바 버전을 변경해도 동일한 것으로 보아 인텔리제이에서 입력받는 로직이 뭔가 변경된 등의 문제가 있는 듯하다.) 원론적인 해결은 못했지만, 방법이 있다. 바로 직전 버전인 2022.1으로 재설치하면 된다. https://www.jetbrains.com/idea/download/other.html Other Versions - IntelliJ IDEA Get past.. 2022. 5. 26.
[자바] 백준 11660 - 구간 합 구하기 5 (boj java) 문제 : boj11660 prefix sum을 이용하는 문제이다. 1차원 배열에 대해 prefix sum을 계산해두면 1차원 배열의 모든 구간에 대한 구간합을 O(1)로 구할 수 있다. 따라서 모든 행에 포함된 열에 대해 행의 개수만큼 prefix sum을 계산해둔다면, O(MN)으로 문제를 풀 수 있다. 이렇게 짠 코드는 여기(github)에 있다. 이하 풀이는 2차원 prefix sum을 사용한 풀이이다. 2차원 배열에 대해 prefix sum을 유지한다면 O(M)으로도 가능하다. arr[a][b]를 (1, 1)부터 (a, b) 까지의 합이라고 정의하자. 그럼 arr[a][b] = '[a. b]의 값' + arr[a-1][j] + arr[a][b-1] - arr[a-1][b-1] 이라고 할 수 있다... 2022. 5. 26.

티스토리툴바