목록분류 전체보기 (122)
tony9402
문제 : 1,2,3 더하기 4 문제 유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자. 4를 1,2,3더하기로 표현해보면 3+1 2+2 1+3 2+1+1 1+2+1 1+1+2 1+1+1+1 이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자. 3+1 (1+3) 2+2 2+1+1 (1+2+1, 1+1+2) 1+1+1+1 이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까? 1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다. 한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다. 4를 가지고 예..
[백준 15988] 1,2,3 더하기 3
알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 3 위 문제는 1, 2, 3 더하기 문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다. 1234567891011121314151617181920212223242526272829#include long long dp[1000001] = {0, 1, 2, 4 }; const long long mod = 1000000009; long long DP(int n){ if (n
[백준 12101] 1,2,3 더하기 2
알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 2 이 문제는 1,2,3 더하기 문제를 이용해서 풀었다. 먼저 4를 본다고 하면 DP[3] + DP[2] + DP[1]를 더한게 DP[4]의 값이다. 아래 그림을 보며 이해를 하자. 4는 3 + 1, 2 + 2, 1 + 3인 경우의 수를 알 수 있고 이를 사전 순으로 정렬하면 1 + 3, 2 + 2, 3 + 1이렇게 된다. 따라서 4를 간단한 규칙으로 정리하면 1부터 DP[4-1]까지는 1로, DP[4-1] + 1부터 DP[4-1] + DP[4-2] 까지는 2로, DP[4-1] + DP[4-2] + 1부터 DP[4-1] + DP[4-2] + DP[4-3] 까지는 3으로 채워진다. 이런 방식으로 계산을 하면 원하는 구간에서 값을 계속 vect..
[백준 9095] 1, 2, 3 더하기
알고리즘 분류 : 다이나믹 프로그래밍(DP) 문제 : 1, 2, 3 더하기 이 문제는 계산을 어떻게 할껀지 점화식을 세우면 금방 푸는 문제이다. 난 이 문제를 풀면서 재귀적인 풀이를 생각하며 풀었다. 5라는 숫자가 있을 때, 여기서 1, 2, 3을 뺀 숫자들 4, 3, 2가 1, 2, 3의 합으로 나타내는 경우의 수를 다 더하면 된다는 것을 발견하였다. 이를 수식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]이다. 여기서 n을 1, 2, 3을 빼다 보면 DP[0]인 경우가 나온다. 이럴 때, DP[0]의 값을 뭐로 하면 좋을까? 간단한 예를 보자. 2라는 숫자가 있다. 2라는 숫자는 보자마자 1 + 1와 2로 경우의 수가 나온다. 이를 내가 푼 방식으로 한번 보자. 2는 1, ..
1806번 부분합 이 문제는 투 포인터 문제로 실수 없이 코딩하면 쉽게 맞는 문제이다. 하지만 난 폰코딩을 한 문제라 실수가 좀 많았다. 알고리즘 이름대로 투 포인터(두 군데를 잡고) 쭈욱 보면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344//폰코딩#include#include using namespace std; typedef long long ll;vector vc; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll n,k,input; cin >> n >> k; for(int i=0;i>input; vc.push_back(inp..
단순 구현 문제이다. 한 문장에서 정수를 뽑고 비교연산자를 뽑아서 계산하면 된다. input data를 보면 규칙이 있다. 3 != 3을 보면 '3' + ' ' + '!' + '=' + ' ' + '3'이다. -3 > 3을 보면 '-' + '3' + ' ' + '>' + ' ' + '3'이다. 이 두 가지를 잘 보면 문장을 처음부터 읽을때 -가 나오거나 숫자가 나오면 그건 숫자라는 것을 알 수 있다. 이 숫자의 끝은 숫자가 나오다가 띄어쓰기가 나온다면 그 숫자가 끝난 부분이다. 그 다음엔 비교 연산자를 읽어야 하는데 그것은 단순히 '!', '>', ''}; int main(){ bool check = false; bool ans = false; int count = 1; int ml, mr; while ..
쉬운 문제인데 엄청난 뻘짓을 해서 계속 제출 했던 문제 그냥 모든 경우의 수를 다 돌리면 된다. 123456789101112131415161718192021222324252627#include#include using namespace std; vector vc; int sum(int n, int k, int max, int s){ int cal = s + vc[n]; int ans = (cal == k); for (int i = n + 1; i > n >> k; vc.resize(n); for (auto &i : vc)cin >> i; for (int i = 0; i
보호되어 있는 글입니다.
차수 표기법 및 차수에 대한 정의 - Big O ( O ) - Omega ( Ω ) - Theta ( Θ ) - Small o ( o ) 1. Theta ( Θ ) N 이상의 모든 정수 n에 대해서 다음 부등식이 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다. 주어진 복잡도 함수 f(n)에 대해서 다음과 같이 정의한다. 2. Big O ( O ) 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재 하는 복잡도 함수 g(n)의 집합이다. 3. Omega ( Ω ) 주어진 복잡도 함수 f(n)에 대해서 은 N 이상의 모든 n에 대해서 다음 부등식을 만족하는 양의..
