Storage Gonie

최대공약수(GCD, Greatest Common Divisor) # 한줄요약 - 최대공약수를 구할 땐 유클리드 호제법을 이용하자. # 개념 - 최대공약수는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. - 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다. - 3개 이상의 수에 대한 최대공약수를 구해야 하는 경우 GCD(GCD(A,B), C) 이런 방식으로 2개씩 묶어서 계산하면 된다. @ 최대공약수를 구하는 첫 번째 방법 => 시간복잡도 : O(N) - a와 b를 2 ~ min(a,b) 까지의 모든 정수로 나누어 보는 것. - 가장 쉬운 방법 int g = 1; // 모든 경우에 두 수는 공약수 1을 가지기 때문에 1로 초기화함 for(int i = 2; i 가장 효율적임 - 유클리드 호제..

나머지 연산 개념 # 자주 등장하는 곳 - 다이나믹 문제에서 전체 경우의 수를 구하는 문제일 때, 답을 M으로 나눈 나머지를 출력하라는 문제가 자주 등장한다. 이 때 최종 계산값에 나머지 연산을 수행한 단순 계산값을 출력하면 된다고 생각하지만 그렇지 않다. 이런 문제의 의도는 중간 및 최종 계산값이 int형의 저장범위를 넘어서기 때문에 이를 극복하여 문제를 해결하라는 것이다. - 이런 유형의 문제는 다음의 원리를 이용해 memoization 배열인 d[i]에 M으로 나눈 나머지 값을 저장함으로써 해결할 수 있다. # 사용가능한 법칙 1. (A + B) % M = ((A % M) + (B % M)) % M 2. (A x B) % M = ((A % M) x (B % M)) % M 3. (A - B) % M ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-22-DP-문제-풀이4-5-백준-No2011-암호코드 # C++ #include using namespace std; int d[5001]; int main() { string s; cin >> s; s = " " + s; // index를 1부터 사용하기 위함. int s_len = s.length() - 1; d[0] = 1; for (int i = 1; i

암호코드 문제 - https://www.acmicpc.net/problem/2011 문제요약 숫자로된 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램 A - 1, B - 2, ,,, Z - 26 ex) 25114 -> "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" (총 6가지) 해결 방법 1. D 정의 D[i] = "i번 문자까지 해석했을 때, 나올 수 있는 해석의 가지수" 암호는 두가지 중 하나이다. - 1자리 수 암호 : 1(A) ~ 9(I) -> 0 제외 - 2자리 수 암호 : 10(J) ~ 26(Z) 2. 점화식 세우기 case 1) 한자리 수의 암호로 보는 경우(....0) i번째 문자까지 해석했을 때 나올 수 있는 해석의 가..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-21-DP-문제-풀이4-4-백준-No2225-합분해?category=864321 # C++ #include using namespace std; long long d[201][201]; int main() { int n, k; cin >> n >> k; d[0][0] = 1; for (int i = 1; i

합분해 문제 * 어려워서 깊은 이해는 못하겠지만 암기는 할 수 있을 듯 하다. - https://www.acmicpc.net/problem/2225 문제요약 N과 K값이 주어지면 0~N의 수 K개로 N을 나타낼 수 있는 모든 경우의 수를 구하고 그 수를 1,000,000,000로 나눈 나머지를 출력하라. 해결 방법 1. D 정의 D[K][N] = "K개의 수를 더해서 합이 N이 되는 경우의 수" 마지막 항이 L값을 가진다면 이전 항들의 합은 N-L임 그리고 L을 분리시킨다면 K-1개의 수를 더해서 합이 N-L이 되는 경우의 수가 됨. 따라서, D[K][N]은 다음의 점화식으로 구할 수 있음 이렇게 맨 뒤의 항을 하나씩 분리시키는 과정이 반복될 때 'K'와 'N'을 입력받으면 K는 1~'K' 의 범위를 가..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-20-DP-문제-풀이4-3-백준-No9461-파도반-수열 # C++ /*방법1*/ #include using namespace std; long long d[101]; int main() { int T; cin >> T; while(T--){ int n; cin >> n; d[1] = 1; d[2] = 1; d[3] = 1; d[4] = 2; d[5] = 2; for (int i = 6; i > n; d[1] = 1; d[2] = 1; d[3] = 1; for (int i = 4; i

파도반 수열 문제 - https://www.acmicpc.net/problem/9461 문제요약 삼각형으로 나선을 만드는데 변의 길이가 1인 정삼각형에서 시작한다. 다음 삼각형은 지금까지 만들어진 나선에서 가장 긴 변에 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1) ~ P(12) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 P(N)의 값을 출력하는 프로그램을 작성해라. 해결 방법 1. D[i] 정의 생략. 2. 점화식 세우기 방법1. 직감으로 본뒤 점화식이 옳은지 확인 P(12) = 12, P(11) = 9, P(7) = 3 에서 볼 수 있듯이 P(12) = P(11) + P(7) 이다. 또한, 이러한 패턴을 다른곳에서도 보여준다. 따라서,..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-19-DP-문제-풀이4-2-백준-No2133-타일-채우기 # C++ #include using namespace std; int d[31]; int main() { int n; cin >> n; d[0] = 1; for (int i = 2; i = 0; j+=2){ if(j == 2) d[i] = 3 * d[i-j]; else d[i] += 2 * d[i-j]; } } cout

타일 채우기 문제 - https://www.acmicpc.net/problem/2133 문제요약 3 x N의 타일을 1 x2, 2 x 1 타일로 채우는 방법의 수 구하기 해결 방법 1. D[i] 정의 D[N] = "3 x i 를 채우는 방법의 수" 2. 점화식 세우기 N번째에 올 수 있는 경우의 수를 모두 조사해 봐야 한다. 길이가 2인경우, 4인경우. 6인경우, ... 모두 다른 경우의 수이다. ... ... 따라서 D[i] = 3D[i-2] + 2D[i-4] + 2D[i-6] + ... (i-k >= 0 일 동안) 이다. 타일의 모양상 i가 홀수일 때는 채우지 못하므로 i는 짝수이어야 한다. (1)시간복잡도 = for 문의 반복 횟수 (2) 구현 -> 'for문을 이용한 반복문'으로 구현 #inclu..