tony9402

문제 : 별찍기-11 문제 유형 : 분할 정복, 구현 별 찍는 규칙을 잘 찾아 별을 찍으면 되는 말로는 간단한 문제이다. 구현은 매우 간단하지만 삼각형의 규칙을 찾는게 어려웠다. 일단 예제 있는 걸로 규칙을 파악해보자. n이 24일때 별의 모양은 아래와 같다. 문제를 잘 읽어보니 n은 항상 (k는 10이하의 음이 아닌 정수) 인 수가 들어온다는 조건이 있다. 이를 보고 삼각형의 높이(세로)의 길이와 밑변(가로)의 길이를 세보았다. 그랬더니 세로은 24즉 이고 가로은 (k=3)이라는 것을 알게 되었다. (여기서 가로에 별 5개와 띄어쓰기를 하나로 묶은 것이다.) 이제 가로를 4등분 하고 세로를 2등분 해보자. 여기서 n=24일때와 닮은 프렉탈 모양 3개가 보일 것이다. 이를 박스로 구분해보자. 맨 위에 있..

문제 : 돌 게임 3문제 유형 : 다이나믹 프로그래밍 이 문제는 숭실대 알고리즘 대회에서 비슷한 문제가 나왔던 문제랑 거의 똑같다. (그 문제에는 승리, 패배만 있는게 아니라 무승부까지 있다.) 하지만 문제 푸는건 거기서 거기다. 두명이 다 최선을 다하여 게임을 한다는 가정과 돌을 1개, 3개, 4개 중 하나를 가지고 갈 수 있다는 조건이 있으므로 이 조건에 맞게 한번 DP 테이블을 채워보자. 가로에 써져 있는 건 현재 돌이 몇개 남았는지 뜻하는것이고 세로줄에는 SK이가 할 차례, CY가 할 차례를 표현한것이다. 표를 채울때 1과 -1을 사용할 것이다. 1은 자신이 승리한다는 뜻이고 -1은 자신이 패배한다는 뜻으로 사용할 껏이다. (1과 0으로 해도 상관없다.)돌이 1개, 3개, 4개가 남았을땐 누가 시..

문제 : 1로 만들기문제 유형 : 다이나믹 프로그래밍 이 문제의 핵심은 입력 받은 수를 최소 횟수로 1로 만드는 것이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. X에서 1을 뺸다. 위 세가지를 이용해서 1로 만들어야 하는데 이를 어떻게 할까? 다이나믹 프로그래밍 문제를 풀 땐 너무 복잡하게 생각하면 오히려 안풀린다. 다이나믹 프로그래밍 문제를 풀기 위한 방법은 탑다운 방식과 바텀업 방식이 있다. 나도 공부하는 입장이니 두 가지 방법으로 설명하겠다. 1. 탑다운(Top-down) 방식 현재 수를 X라 하자. X가 3으로 나눠떨어진다면 X/3을 만드는 횟수는 X 만든 횟수에 한번더 연산을 한 것이기 때문에 X를 만든 횟수에 +1을 해주면 된다.이..

문제 : 파도반 수열 문제 유형 : 다이나믹 프로그래밍 이 문제는 규칙을 찾기만 하면 되는 문제이다. 난 두가지 점화식으로 풀었다. 1. 점화식1 일단 가장 먼저 풀었던 방식을 설명하자면, 소용돌이처럼 이어지는 수를 한 줄로 써보았다. 1 1 1 2 2 3 4 5 7 9 12 ... 이것을 보고 규칙이 바로 보였다. 지금 현재 위치에서 왼쪽으로 2칸 떨어진 것과 같은 방향으로 3칸 떨어진 것의 합이 현재 위치의 값과 같다는 점화식을 발견했다. 이를 식으로 쓰자면 아래와 같다. 이 식을 가지고 초기값만 잘 넣어주면 쉽게 맞추는 문제이다. 또한 n이 커지면 int형의 범위가 벗어나니 맞왜틀 했던 사람들은 int를 long long으로 바꿔보기 바란다. - 소스코드 123456789101112131415161..

문제 : 1,2,3 더하기 6유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다. 어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지.....

문제 : 1,2,3 더하기 5문제 유형 : 다이나믹 프로그래밍 일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자. 처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다. 3 + 11 + 32 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1 여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.이를 어떻게 풀까.......? 정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 1. 3 + (n - 3)2. 2 + (n - 2)3. 1 + (n - 1) 1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.3 + 1 + (n -..

문제 : 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를 가지고 예..

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 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..

알고리즘 분류 : 다이나믹 프로그래밍(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..