Category: algorithms

2018
0
computer sciencealgorithms

백준[2609] - 최대공약수와 최소공배수

문제백준 2609 문제 보기 접근 방법유클리드 호제법을 사용하여 최대공약수를 구하고 입력된 두 수의 곱에 다시 최대공약수로 나누어 최소 공배수를 구한다. 코드#include <iostream> using namespace std; int N, M; int gcd, lcm; int getGCD(int a, int b) { return b

0
computer sciencealgorithms

백준[11576] - base conversion

문제백준 11576 문제 보기 접근 방법먼저 입력된 값을 10진법으로 변환한 뒤 다시 진법을 변환한다. 코드#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; int A, B, m; vector<int

0
computer sciencealgorithms

백준[11054] - 가장 긴 바이토닉 부분 수열

문제백준 11054 문제 보기 접근 방법먼저 증가하는 부분 수열을 구하는 dp을 작성하고 뒤에서 부터 감소하는 가장 긴 부분 수열을 구하는 dp2를 구한다.따라서 dp - dp2 - 1에서 최대값을 출력한다. -1을하는 이유는 dp[2] + dp2[2]를 계산하면 2번째 인덱스가 중복 계산되기 때문이다. 코드#include <iostream> #in

0
computer sciencealgorithms

백준[2156] - 포도주 시식

문제백준 2156 문제 보기 접근 방법경우를 총 3가지로 나누어 dp로 해결한다. n번째 포도주를 마시지 않을 때와 마실 때(첫번째 잔인지, 연속된 잔인지 구분).n번째 잔을 마시지 않을 경우, n-1번째 잔은 마셧는지 안마셧는지 여부에 상관없이 최대값을 저장.n번째 잔이 연속된 첫 잔일 경우, 이전 잔은 무조건 마시지 않었어야 한다.n번째 잔이 연속된 잔

0
computer sciencealgorithms

백준[10844] - 쉬운계단수

문제백준 10844 문제 보기 접근 방법바로 앞의 수가 0과 9일때 주의해서 점화식을 세운다. 처음 제출할 때 출력할때만 나머지를 계산해서 출력되도록해서 오버플로우 발생으로 오답이 됐다.점화식은 자릿수와 바로 앞의 숫자를 인덱스로 모든 경우를 저장한다.if(앞에 저장된 숫자가 0) dp[i][j] = dp[i - 1][1];if(앞에 저장된 숫자가 9) d

0
computer sciencealgorithms

백준[11726] - 2*n 타일링

문제백준 11726 문제 보기 접근 방법bottom-up 방식의 dp를 활용해 문제 접근을 했다. 길이가 1인 타일이 추가될 때와 2인 타일이 추가될때의 경우를 계산해 식을 세웠다.점화식은 다음과 같다.dp[n] = dp[n-1] + dp[n-2] 코드#include <iostream> using namespace std; int n; int d