본문 바로가기

java9

백준 알고리즘 21단계 이분 탐색 - 가장 긴 증가하는 부분 수열2 (12015번) Java 이번에 풀어볼 문제는 가장 긴 증가하는 부분 수열2이다. 해당 문제 링크는 아래에서 확인할 수 있다. https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. 문제 확인 2. 문제 풀이 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int max=0;.. 2021. 5. 25.
백준 알고리즘 20단계 분할 정복- 행렬 곱셈 (2740번) Java 이번에 풀 문제는 행렬 곱셈 문제이다. 해당 문제 링크는 다음과 같다. https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 1. 문제 확인 2. 문제 풀이 3. 결과 2021. 5. 18.
백준 알고리즘 13단계 백트래킹 - N과 M (2) (15650) Java 1. 문제 확인 www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1부터 N까지의 수 중 오름차순이고, M의 길이까지 나열 가능한 수열 2. 문제 풀이 array 배열에 i가 들어가면서, 다음 for문에서 i+1 부터 탐색하도록 하였다. 또한 depth도 +1하면서 재귀호출을 해준다. 그럼 다음 재귀에서는 start는 이전 재귀보다 +1의 상태가 되고, 반복문에서 결과적으로 이전 값보다 큰 수부터 탐색하게 된다. 2020. 11. 3.
백준 알고리즘 13단계 백트래킹 - N과 M (4) (15652) JAVA 1. 문제 확인 2. 문제 풀이 3. 결과 2020. 10. 6.
백준 알고리즘 19단계 분할 정복 - 행렬 곱셈 (2740) Java 1. 문제 확인 2. 문제 풀이 행렬곱에서는 첫 번째 행렬의 열과 두 번째 행렬(B)의 행(M)이 일치해야 한다. 그리고 N * M 와 M * K의 행렬 곱의 결과는 크기 N * K인 행렬이 된다. 행렬 곱셈 점화식 C[i][j] += A[i][k] * B[k][j] 3*2인 행렬 A와 2*4인 행렬 B를 예로 들어본다면. AXB인 행렬 C는 3*4인 행렬이 될 것이다. 그래서 이걸로 알고리즘을 짜면, 1. A의 1행 1열에 담긴 값을 B의 1행 1열에 담긴 값들과 곱한다. (1번 수행) [for문 1번 수행] 2. A의 1행 {2열, 3열, 4열}도 B의 1행 {2열, 3열, 4열}과 곱하므로, 1번의 과정을 4번 반복한다. [for문 1번 수행] 3. 2번의 과정을 2행에도 진행해야하므로, 총 2번 .. 2020. 9. 29.
백준 알고리즘 12단계 정렬 - 좌표 정렬하기2 (11651) Java 1. 문제 확인 2. 문제 풀이 3. 결과 2020. 9. 29.