Algorithm4 [DP] 백준 실버3 11726, 11727번 2xn 타일링, 2xn타일링2 문제https://www.acmicpc.net/problem/11726https://www.acmicpc.net/problem/11727정답11726번 정답은 더보기더보기package BOJ.DP.이곱하기n타일링_11726.insub2004_241110;import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { // 점화식 // 규칙이 있었다. // d(n) = d(n-2) + d(n-1) public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStr.. 2024. 11. 13. [DP] 백준 실버3 1463번 1로 만들기 문제https://www.acmicpc.net/problem/1463정답정답은 더보기더보기import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { private static int[] array = new int[1000003]; public static void main(String[] args) throws Exception { // array[1] = 0; array[2] = 1; array[3] = 1; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2024. 11. 11. Dynamic Programming DP = 다이나믹 프로그래밍DP문제나 다이나믹 프로그래밍 과 같은 단어를 들었을 때, 너무 어렵게 느껴져서 알아보기 꺼려졌다.그런데 요즘 기업 코테를 보거나 코테 사이트에서 레벨업을 하고 싶을 때 DP문제가 빠지질 않았다....이제는 물러설 곳이 없기 때문에 빠른 시일 내에 DP에 대해 이해해보고 정복해보려고 한다. 다이나믹 프로그래밍이 먼데?다이나믹이라는 단어를 듣자마자, 무언가가 엄청 막~ 화려하게 동작하게끔 코딩을 해야하는 줄 알았다.하지만 그런 뜻이 아니라, 다이나믹 프로그래밍은 아래 한 문장으로 설명할 수 있을 것 같다.메모리(배열or자료구조)를 사용해서 중복 연산을 줄이고(연산한 결과를 배열or자료구조에 담는다) 중복 연산을 줄여서 수행시간을 줄이자. 그래서 DP문제를 풀때는 아래 문장을 기억.. 2024. 11. 10. 유클리드 호제법(Euclidean Algorithm) 최대공약수 구할 때 사용하는 유클리드 호제법에 대해서 남기려고 한다. 최대공약수 GCD(Greatest Common Divisor) 최소공배수 LCM(Least Common Multiple) 두 수가 작은 수라면 소인수분해를 통해서 gcd와 lcm을 구할 수 있지만 숫자가 크다면 다른 방식으로 구해야한다. 유클리드 알고리즘이란 2개의 자연수(a,b)의 최대공약수를 구하는데 "자연수 a, b가 있을 때 (a>b, a!=b) a를 b로 나눈 목을 q 나머지를 r이라고 했을 때 a = qb+ r이다. GCD(a,b) = GCD(b,r)이며 r이 0일 때 b가 최대공약수이다." 만약 r=0이 아니면 a에는 b를 b에는 r을 넣어서 r=0이 나올 때까지 반복한다. 라는 원리이다. 그림으로 표현해보겠다. mod연산.. 2022. 11. 28. 이전 1 다음 728x90 반응형
