일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
- 라우터
- 서버구축
- 탐욕법
- Algorithm
- Router
- 동적프로그래밍
- url parsing
- 완전탐색
- nodejs
- 자료구조
- 스터디
- 리액트
- AWS
- react
- 토이프로젝트
- 알고리즘
- ELB
- spring
- BFS
- 정렬
- 브루트포스
- EC2
- mysql
- EventListener
- java
- 다익스트라 알고리즘
- sort
- 백준
- 백준알고리즘
- Spring Boot
- Today
- Total
목록2020/06 (18)
공부하는 블로그
9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열(Longest Common Subsequence, LCS)를 찾는 문제이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str1 = sc.next(); String str2 = sc.next(); sc.clo..
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 주어진 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)을 찾는 문제이다. LIS란 주어진 수열이 {10, 20, 50, 20, 30, 40, 60, 10, 80} 이라면 {10, 20, 30, 40, 60, 80}을 뜻한다. import java.util.Scanner; public class Main { public static ..
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 배낭의 무게와 물건들의 가치와 무게가 함께 주어진다. 주어진 물건들을 이용하여 배낭의 값어치를 최대로 채우는 문제이다. import java.util.Scanner; public class Main { static int[][] items; static int[][] bag; public static void main(String[] args) { Scanner sc = new Scanner(Sys..
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 동적 프로그래밍을 이용해서 계단 수의 개수를 찾는 문제이다. package p10844; import java.util.Scanner; public class Main { static int[][] dp = new int[101][10]; static final int mod = 1000000000; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); for (int i = 1; i < 10; i++) { dp[1][i] = 1; ..
9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 동적 프로그래밍을 활용하여 점화식을 해결하는 문제이다. import java.util.Scanner; public class Main { static long[] memory; public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int t = sc.nextInt(); for (int i = 0; i < t;..
동적 프로그래밍과 탐욕법은 문제를 해결하여 최적의 해를 구하는 방법이다. Dynamic Programming? 동적 프로그래밍(Dynamic Programming)은 큰 문제를 하위의 작은 문제들로 나누어 풀어 최적의 해를 구하는 기법이다. 이러면 분할정복 기법과 다를게 없어 보인다. 하지만 분할정복 기법은 작은 문제들을 풀다보면 같은 작은 문제를 반복해서 푸는 경우가 생기게 된다. 이 때, 작은 문제를 매번 다시 계산하지 않고 값을 배열에 저장(Memoization)해두었다가 재사용하는 것이 동적 프로그래밍이다. 동적 프로그래밍을 이용하여 풀 수 있는 대표적인 문제는 피보나치 수열, 최장 공통부분 수열문제, 배낭 문제 등이 있다. 간단하게 피보나치수열 문제를 풀어보자. package fibonacci;..
10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬의 거듭 제곱을 구하는 문제이다. import java.util.Scanner; public class Main { static int N; static int[][] A; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); A = new int[N][N]; long B = sc.nextLong(); for (int i = 0; i < N; i++) { f..
2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 행렬 곱셈을 하는 간단한 문제이다. import java.util.Scanner; public class Main { static int N; static int M; static int K; static int[][] A; static int[][] B; public static void main(String[] args) { // 입력 Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = ..