JAVA - 백준 [BAEK JOON]
[백준] 2805번 : 나무 자르기 - JAVA [자바]
[백준] 2805번 : 나무 자르기 - JAVA [자바]
2021.09.12https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 이 전의 랜선 자르기 문제와 매우 유사한 문제다. 만약 직전 문제를 안풀어보셨다면 먼저 풀고오는 것을 추천한다. 그러면 이 문제도 자연스럽게 바로 풀릴 것이다. 알고리즘 [접근 방법] 이 번 문제는 앞서 언급했듯 랜선 자르기 문제와 풀이 방식이 거의 같은 문제다. 이 문제를 풀기 전에 되도록이면 아래 글을 먼저 보고 오시는 것을 추천한다. 모두 다 연계..
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
2021.08.31https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 이분 탐색의 응용 문제다. 알고리즘 [접근 방법] 일단, 이 번 문제를 풀기 전에 이분 탐색 중 Upper Bound 에 대해 이해하고 있어야 한다. 그러니, 해당 원리를 이해하기 위해 아래 포스팅을 먼저 보시고 오시기를 바란다. https://st-lab.tistory.com/267 [백준] 10816번 : 숫자 카드 2 - JAVA [자바] https://ww..
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
2021.08.06https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 직전 문제랑 비슷하지만, 이분 탐색을 활용해야 할 경우 조금 고려해야 할 부분이 있는 문제다. 알고리즘 [접근 방법] 이 문제 자체는 그리 어렵지 않다. 사실 이분 탐색을 쓰지 않고도 카운팅 정렬 형식을 사용하여 풀 수도 있다만, 그래도 이분 탐색 카테고리에 있는 만큼 한 번 이분 탐색 풀이 방식을 통해 풀이를 해보도록 하자. 일단, 이분 탐색의 경우 구간의..
[백준] 1920번 : 수 찾기 - JAVA [자바]
[백준] 1920번 : 수 찾기 - JAVA [자바]
2021.07.16https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 새 카테고리인 이분 탐색의 첫 번째 문제인 수 찾기다. 알고리즘 [접근 방법] 일단, 풀이 방법을 알아보기 전에 이분 탐색(Binary Search)에 대해 알아보자. 이 전 문제까지 우리가 분할 정복을 살펴보았다. 분할 정복 방식의 경우에는 문제가 주어지면 해당 문제를 둘 이상으로 나누면서 나눠진 부분문제에 대해 풀렸다면 해당 부분은 끝내고,..
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
2021.06.26https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 문제 이 번 문제는 분할 정복 카테고리의 마지막 문제인만큼 조금 많이 어려운 문제다. 분할 정복 방식 자체는 이전 문제인 히스토그램에서 가장 큰 직사각형과 접근 방식은 유사하나 조금 더 신경써야할 부분들이 존재하므로 같이 알아보도록 하자. 알고리즘 [접근 방법] 이 번 문제의 경우 일반적인 분할 정복 방식과 스윕 라인 방식 이렇게 두 가지 풀이 방식이 존재한다. 일..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]
2021.06.18https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 히스토그램 내의 가장 큰 넓이를 구하는 문제는 엄청 유명한 문제라 알고리즘을 많이 접해보았다면 한 번쯤은 접해보았을 문제다. 알고리즘 [접근 방법] 이 번 문제의 경우 풀이 방법 자체는 대표적으로 두 가지 방식이 있다. 먼저 이 문제의 카테고리 처럼 분할정복으로 풀이하는 방식, 그리고 스택 자료구조를 이용한 풀이 방식이 있다. 이 번에..
[백준] 11444번 : 피보나치 수 6 - JAVA [자바]
[백준] 11444번 : 피보나치 수 6 - JAVA [자바]
2021.05.27https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 번 문제는 단계별로 차근차근 풀었었다면 여러 번에 걸쳐 피보나치 수를 구하는 문제들을 풀어왔기 때문에 그렇게 어렵지는 않았을 것이다. 그동안 풀어왔던 피보나치 수와 관련된 문제들은 다음과 같다. 피보나치 수 5 (재귀) 피보나치 수 2(동적계획법) 다만 문제는 똑같더라도 주어지는 입력의 범위는 엄청 다르다. 이 번 문제의 경우 n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이기 때문에 동적계획법으로 풀이하더라도 그동..
[백준] 10830번 : 행렬 제곱 - JAVA [자바]
[백준] 10830번 : 행렬 제곱 - JAVA [자바]
2021.05.24https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 번 문제는 이전에 분할정복 카테고리에서 풀었었던 1629번 : 곱셈 문제를 풀어보았다면 그리 어려운 문제는 아니다. 만약 풀어보지 않으셨다면 위 문제부터 풀고 오신다면 수월하게 이 문제도 풀 수 있으니 한 번 보고오시는 것을 추천드린다. 위 곱셈문제 풀이와 같게 행렬의 지수(exponential)를 절반으로 잘라가면서 분할정복을 해주면 된다. 좀 더 자세하게 말하자면 다음과 같다..
[백준] 2740번 : 행렬 곱셈 - JAVA [자바]
[백준] 2740번 : 행렬 곱셈 - JAVA [자바]
2021.05.05www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 문제 이 문제가 원래 생각없이 일반적인 행렬 곱셈 방식으로 풀어서 통과했지만.. 분할 정복 카테고리에 들어있어서 어떻게 분할정복으로 풀이해야 할지 많이 고민했던 문제다. 알고리즘 [접근 방법] 문제 자체는 어렵지 않을 것이다. 행렬 곱셈을 그대로 구현해주어도 통과가 되니... 근데 이를 어떻게 분할정복으로 풀지? 라는 고민으로 찾아오신 분들도 꽤 많을 것이다. 필자도 똑같은 고민을 했는데, 알..
[백준] 11401번 : 이항 계수 3 - JAVA [자바]
[백준] 11401번 : 이항 계수 3 - JAVA [자바]
2021.04.23www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 이 전에 풀었었던 정수론 및 조합론 카테고리의 이항 계수 2 문제를 풀었다면 크게 어려움 없이 풀었을 것이다. 알고리즘 [접근 방법] 이 문제는 이 전에 이미 설명해줬기 때문에 내용이 거의 중복될 것이다. 일단 문제를 풀이하기 전에 아래 글을 읽고 오시는 것을 추천드린다. st-lab.tistory.com/162 [백준] 11051번 : 이항 계수 2 - JAVA [자바] www.acmicpc.net/problem/11051 1..