JAVA - 백준 [BAEK JOON]/분할 정복
[백준] 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..
[백준] 1629번 : 곱셈 - JAVA [자바]
[백준] 1629번 : 곱셈 - JAVA [자바]
2021.04.07www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제는 얼핏보면 B번 거듭제곱 해주면 될 것 같지만... 왜 분할정복 카테고리에 있겠는가.. A, B, C는 각각 최대 2,147,483,647을 갖을 수 있다는 것이고, 2,147,483,647번 거듭제곱 하는 것 부터 많은 수행 과정과, C로 모듈러 연산까지 해주어야 하기 떄문에 시간초과가 날 것이 너무나 뻔하다. 하지만 문제는 그리 어렵지 않다. 우리가 모두가 배웠던 간단한 '지수 법칙'과 '모듈러 성질'만 알고 있으면 된다. 일단 지수법..
[백준] 1780번 : 종이의 개수 - JAVA [자바]
[백준] 1780번 : 종이의 개수 - JAVA [자바]
2021.04.05www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 색종이 만들기 문제와 매우 유사한 문제다. 알고리즘 [접근 방법] 이 문제는 결코 어렵지 않다. 이전에 색종이 만들기 문제를 풀어보았다면 매우 쉽게 풀 수 있었을 것이다. 기본적인 쿼드트리 방식 문제를 변형한 것인지라 혹시 접근 방법을 모르곘다면 아래 두 문제를 먼저 풀이 방법을 보고 오는 것을 추천드린다. st-lab.tistory.com/227 [백준] 2630번 : 색종이 만들기 - JAV..
[백준] 1992번 : 쿼드트리 - JAVA[자바]
[백준] 1992번 : 쿼드트리 - JAVA[자바]
2021.03.23www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 이전 문제인 색종이 만들기 문제를 풀어보셨다면 매우 쉽게 풀 수 있는 문제다. 잘 모르겠는 경우 위 링크를 통해 한 번 풀어보고 오는 것을 추천한다. 알고리즘 [접근 방법] 이진 트리(Binary Tree)는 자식 노드를 2개씩 갖는 트리였다면 쿼드 트리(Quad Tree)는 쉽게 말해서 자식 노드가 4개인 트리 자료구조를 의미한다. 이전의 문제인 색종이 문제와 접근 방식 자체는 같은 구조로 ..
[백준] 2630번 : 색종이 만들기 - JAVA [자바]
[백준] 2630번 : 색종이 만들기 - JAVA [자바]
2021.03.17www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 분할 정복의 첫 문제다. 원리만 이해한다면 그리 어렵진 않으니 차근차근 살펴보도록 하자. 알고리즘 [접근 방법] 여러분이 분할 정복 문제를 풀기 전에 기본적으로 알고있어야 할 지식이 있다. 1. 재귀에 대한 이해 2. 탐색(search)에 대한 이해 위 두 개의 기본 이해를 바탕으로 분할 정복을 풀이할 수 있다. 기본적으로, 분할 정복의 과정은 3단계로 나뉜다. 1. 현재 상태의..