Simple Explain

#9465번 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 기존의 DP문제와는 약간 다른 모습을 보여서 신기했다. 기존의 DP는 특정 조건에 맞춰서 값을 새로 추가해나가는 형태였는데 이 문제는 주어진 값들 (리스트)을 갱신해 나가는 형태로 진행하는게 효율적이었다. 풀이 1) 스티커를 떼면 상하좌우 스티커를 사용할 수 없다. 2) 그런 상황에서의 스티커 점수의 최댓값 상하좌우에 위치한 값을 선택할 수가 없다 -> 대각선 상에 ..

#2225번 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP리스트를 2차원으로 구현해야 성공할 수 있는 문제였다. dp의 구조는 dp[K][N] : K개의 수로 N이라는 수를 분해할 경우의 수 로 해석할 수 있다. dp 내부의 2차원 리스트의 길이는 입력된 수 num이 되어야한다. 예를 들어, 10을 3개의 수로 분해하는 경우의 수를 동적 계획법으로 구하는 방법은 dp[0] = [0,0,0,0,0,0,0,0,0,0,0] -> 0~10까지의 수를 0개의 수로 분해하는 경우의 수는 각각 0이다. dp[1] = [1,1,1,1,1,1,1,1,1,1,1] -> 1개..

#1699번 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net n = int(input()) dp = [x for x in range(n+1)] # 각각의 인덱스 = 수, 값 = 수(인덱스)를 구하는데 들어가는 제곱수의 합의 최소 갯수 # 일단은 1을 가지고 더했을 경우로 초기화 for i in range(1, n+1): # 1부터 제곱수의 합을 차근차근 구해줌 : DP. for j in range(1, i..

#11503 가장 긴 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 아 왜 DP에 적응을 못하는 느낌이 들까? DP의 핵심과제는 이전에 연산한 값을 재사용함으로써 효율을 높이는 것이다. 그러니까, 항상 이전 항을 불러와서 +나 - 등을 하는 코드가 필요하다. 또, 리스트에 저장되는 값을 잘 정의하는 것도 중요하다. 이걸 잘 못 한다는 느낌이... 위 문제는 주..

#10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 디피 문제를 풀다가 또 한번 막히셨단다... (지긋) 내가 생각한 점화식은 약간 이런 느낌이었다. 뭔가 야간 이런 느낌으로, 0, 9일 때는 하나씩 파생되고, 1~8일 때는 2개씩 파생되는 모양새가 다른 패턴이 있을 것 만 같은 느낌을 주긴 했다. 그래도 위에서 먼저 찾았던 점화식을 적용해 봤지만 당연히 틀림. 실버 1레벨의 문제니까 다르다 이건가 고민을 하던 끝에 검색을 했다. n = int(input()) mod = 1000000000 dp = [[0 for x in range(1..

#11727 또 다시 타일링 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이번 문제의 점화식은 내 힘으로 찾았다. (노가다) 팁? 이라 하면, An 을 An-1과 An-2등 이 전의 값으로 조합하여 찾는게 팁이 될 수 있을지도 모르겠다. 그렇게 제출 했는데 또 자꾸 틀려서 많이 화가 났다. 자꾸 출력 형식을 무시하고 제출해서 그런거였다. 그렇게 세 번을 틀렸다. 병X.... 어제도 그러더니... 실수가 반복되면 실력이랬다. 엥 근데 또 틀렸다 (100%에서) 뭐지?.....

내가 생각하는 다이나믹 프로그래밍의 핵심은 점화식을 파악하는데 있다. 그러니까 고등학교 때 봤던 확률과 통계 느낌 나는 문제들을 이해하는게 아주 중요하다. #11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net n의 변화에 따른 타일링의 경우의 수를 계산해주면 되는데 내가 처음 판단한 점화식은 이렇다. An = An-1 + (n-2) 였다. 뭐 예상한 결과다. 고민고민 하다가 결국엔 서치... 결론은 An = An-1 + An-2 였고 맞추긴 ..

#1463번 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 수학과 관련된 문제를 모두 해결하고 나니 다이나믹 프로그래밍이라는 새로운 분야를 만나게 됐다. 바로 다이나믹 프로그래밍. 동적 계획법이라고도 표현되는 이 문제는 기존에 내가 애용해왔던 재귀함수와 유사한 부분이다. def : 큰 문제를 작은 문제로 나누어 푸는 방법. 분할 정복과 비슷하지 않냐는 의견을 낼 수도 있지만, 분할 정복은 같은 형태의 계산을 반복해서 수행하지만 다이나믹 프로그래밍은 작은 문제를 해결한 결과를 재사용하는 형태이다. 동적 프로그래밍을 진행하기 위한 충분조건은 다음과..

#2089번 https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net -2 진수로 변환하는 문제이다. 기본적인 2진법은 자리수 마다 2의 제곱수를 해주는데 -2진법은 -2의 제곱수를 자리해주는 방식이다. 때문에 1,3,5,7 번째 자리 즉 홀수번 째 자리에서는 양수가 나오고, 짝수번 째 자리에서는 음수가 나온다. 이를 잘 조합해서 변환해주면 된다. 처음엔 ..

#17087 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 최소공약수가 필요한 문제인데, 난 여태 최소공약수 연산을 다음처럼 했었다. def get_gcd(num1, num2): for i in range(max(num1, num2), 0, -1): if num1%i == 0 and num2%i == 0: return i 공약수를 구하는 상황인 만큼 두 수의 약수가 아닌 수까지 loop를 돌리는 위 코드는 무조..