일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- 버킷리스트
- 일상탈출
- HelloWorld
- opcode
- extends
- 보안
- bytecode
- Transition
- abstract
- 회피
- 여행계획
- Recylcer
- 심리학
- Shared Elements
- throws
- Interface
- Navigation Component
- static
- 보안취약점
- jvm
- bytecode 분석
- 취약점
- ㅇ
- 여행
- javap
- Android
- IMPLEMENT
- 치유
- 심리여행
- 일상회피
- Today
- Total
목록Algorithm/baekjoon (41)
패스트터틀
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net https://sudeky.tistory.com/126 (Baekjoon) brute-force - (1) 부분수열의 합( + 부분집합 출력) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N..
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 부분수열의 합을 구하기전에 부분집합을 출력하는방법을 할줄 알아야한다. 부분집합을 출력하는방법은 visited로 표현할수있는데 예를들어서 1,2,3,4 를 가지고 부분집합을 구성할때 visited가 1000 이라면 1 visited가 1110 이라면 123 visited가 0011 이라면 34 ... 의 식으로 표현하면 모든 부분집합을 표현할수 있다. pac..
https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net dp(n) = 2*dp(n-1) + 3*dp(n-2) + 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 위의 그림과 같은 과정을 통해 위의 점화식을 도출할수 있다. 그리고 코드를 짜서 제출할경우 시간초과를 겪는데 그러한 이유를 살펴보면은 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 부분에서 계속 구한값을 다시 계산하고 다시계산하는것을 알수있다. 이부분 또한 동적프로그래밍 기법을 적용하여서 한번구한값은 다시 구하지 말자라는 방식을 써야..
https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net D(n) = 3*D(n-2) + 2*(D(n-4) + D(n-6) +..... + D(0)) package dp; import java.io.IOException; import java.util.Scanner; public class _2133{ static int result = 0; static int..
https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net dp문제의 가장 기본이 되는 피보나치이다. 점화식을 재귀함수로 어떤식으로 표현할수있느냐도 알수있는 핵심문제이다. A(n) = A(n-..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 우선 외판원 문제는 현재 나온 이론으로는 풀수없지만 그나마 가장 나은 방법으로 푸는것이 DP방법이다라는 사실을 알고있어야한다. N! 를 n^2*2^n 으로 줄였다는 사실만 알자. 비트마스크 복습 dp[3][1011] 의 뜻은 3번째도시에서 2 번째도시까지 가는 최소한의 수 dp[2]..
https://www.acmicpc.net/problem/12813 12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net bitmask 문제에 앞서서 손풀기 package etc; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; public class _12813{ public static void main(String args[]) throws IOException{ Buffered..
https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 우선 내가 주어진 문제가 시험문제이고 DP라는 가정이 있다면 위와같은 가정으로 추론으로 점화식을 풀수있다. 하지만 점화식이 최적의 답인지 아니면 그리디알고리즘에서 더 빨리 찾는법이 있는지 아니면 그외에 더 최적의 알고리즘이 있는지는 경험이 늘어나봐야 알것같다. package dp; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class _11727{ s..