남남이루의 고군분투 🌳

백준 9184. 신나는 함수실행 문제 요약 : 재귀함수로 돌리면 너무 오래 걸린다! 어떻게 할까? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b..

2차원 DP를 푸는 게 아직 너무 어색하다, 어려웠던 점 누적합 데이터를 쌓아가는 부분 누적합 그래프를 바탕으로 일부 값을 계산하는 식을 짜는 부분 참고한 블로그 [python/파이썬] 백준 11660 구간 합 구하기 5 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경 sodehdt-ldkt.tistory.com [백준] 11660 구간 합 구하기 5 (python) - 누적 합 (2차원) 정리 문제 링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의..

문제 링크 보석 사이의 함정, 경보장치를 고려해 최대 가치의 보석을 구해라 함정 : 보석 줍다가 뒤로 못가 경보 : m개 이상을 연속으로 주워야 빠져나올 수 있음 => 보석 줍기 시작하면 m개 이상 주워야 함 import sys input = sys.stdin.readline n,m = map(int, input().split()) dia = [0]+[int(input()) for _ in range(n)] dp = [0]*(n+1) for i in range(1,n+1): tot += dia[i] if 0

문제 https://www.acmicpc.net/problem/10211 최대 합을 가진 연속 부분집합 구하기. 주의할 점은, 그냥 합이 큰 부분집합아니고 연속 집합이어야 한다는 점..! 핵심 코드 i 인덱스까지 왔을 때, 끊고 가는게 크냐, 합이 크냐. dp[i] = max(dp[i-1] + x[i] , x[i]) 최종적으로 dp중에 max 찾아주면 가장 큰 부분집합의 합이 들어있는 value를 찾을 수 있다. 참고 원소 합이 가장 컸을 때를 구하기만 하면 되는 거면 dp[i] = max(dp[i-1] + x[i] , dp[i-1]) 을 통해 i 인덱스의 값을 합에 포함할 지 아닐지를 판단해주면 된다. 근데 위 문제는 앞에 달린 애들을 버릴거냐 말거냐이다.. 한끝 차이네. 최종 코드 t = int(in..

10844 쉬운 계단 문제를 풀면 dp 배열을 2차열로 활용하는 게 나온다. 이 원리를 그대로 적용할 수 있겠다 싶었다. 자리수에 대한 관계를 점화식으로 표현할 수 있다는 게 공통점이었기 때문이다. import sys input = sys.stdin.readline l = int(input()) d = [[0]*10 for _ in range(l+1)] for k in range(10): d[1][k] = 1 for i in range(2,l+1): for j in range(10): d[i][j] = sum(d[i-1][j:]) print(sum(d[l])%10007) sum을 두 번 쓰는 게 낯설었는데, 나열해보면 그 이유를 알 수 있었다. # d[2][0] # d[2][4] = d[1][4::-1]..

바텀업으로 배열을 채우고, 인덱스 n에 해당하는 값을 출력하는 식으로 품 d의 기본 배열을 각 인덱스로 채우는 게 다른 DP문제랑 다른 점이었고, ( 1**2로만 더한 횟수가 최대이므로, 3 = 1**2 + 1**2 + 1**2 , 3에 대해 최대 횟수가 3임 ) 이중 반복문, 제곱근까지는 생각했는데, 이걸 식으로 구현하는 게 어려웠다. 뺄셈으로 해결하신 분의 코드를 참고했다. 11을 예시로 원리를 설명해보자면, 11은 제곱의 항들로 표현되는 가짓수들의 일부는 이렇다. 11 = 1**2 + 1**2 + ... 11 = 2**2 + 2**2 + 1**1 + 1**1 + 1** 1 11 = 3**2 + 1**2 + 1**2 (최소 횟수) 어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가..

풀이 과정 1. 점화식으로 표현해보기 2. 작은 수부터 일일이 계산해 규칙 찾아내기 3. 바텀업으로 풀어보기 >>> 런타임 에러 4. 생략된 규칙 추가하기 (%15746) >>> 메모리 초과 5. %15746의 위치를 출력 구문이 아닌, 입력 부분으로 옮김 >>> 런타임 에러 ------ 계속해서 index 에러가 나고 있었다. 다른 분들의 코드를 참고한 결과, 가장 큰 차이점은 빈 배열을 만드는 부분이었따. 나는 d = [0] * (n+1)로 했는데, 다른 사람들은 아예 배열의 길이를 N의 최대값인 1000000+1로 고정해뒀더라. 그걸 수정하니, 정답처리 되었다. 아직 왜 그런지는 모르겠다. import sys input = sys.stdin.readline n = int(input()) d = [0..

DP란, 피보나치처럼 작은 문제로 분할하여 현재의 값을 구하는 문제에 대해 메모리 공간을 활용함으로써 속도를 비약적으로 줄이는 기법이다. 점화식으로 표현되는 문제들을 DP기법을 활용할 경우 효율적으로 답을 구할 수 있다. 점화식이란, 인접한 항들 사이의 관계식을 의미한다. 예를 들어 수열에서의 각 항을 An이라고 부를때, 우리는 점화식을 이용해 현재의 항을 이전항에 대한 식으로 표현할 수 있다. DP로 해결할 수 있는 가장 대표적인 유형인 피보나치의 점화식은 A(n+2) = A(n+1) + An 으로 표현할 수 있다. 프로그래밍과 점화식 n번째 피보나치수를 f(n)이라고 표현할 때, f(4)를 구하고자 할 때 f(2)와 f(1)은 항상 1이므로 이때는 호출을 정지하는 코드를 넣어 재귀함수로 풀 수 있다...