Simple Explain

#9251 LCS https://www.acmicpc.net/problem/9251 아.. 그제 풀었던거 오늘 포스팅 하려니까 기억이 가물가물... 단순히 dfs로 풀었다.모든 경우의 수를 탐색하는 것이다. (브루트포스?) 그리고 역시나 메모리 초과를 맞이했다. 틀린 코드s1 = input().strip()s2 = input().strip()n1 = len(s1)n2 = len(s2)visited1 = [False] * n1visited2 = [False] * n2N = max(n1, n2)result1 = {x: [] for x in range(1, n1 + 1)}result2 = {x: [] for x in range(1, n1 + 1)}def dfs(depth, s, origin, n): if..

#12865 평범한 배낭 https://www.acmicpc.net/problem/12865 과거 풀다가 해결을 못해서 버렸던 문제다.  틀린코드n, k = map(int, input().split())dp = [0] * (k + 1)obj = []for _ in range(n): w, v = map(int, input().split()) dp[w] = v obj.append([w, v])for i in range(k + 1): for w, v in obj: if i + w  왜 자꾸 틀릴까? 의문이었다..  근데 잘 생각해보니, 물품의 중복이 가능한 코드였다. 주어진 테스트케이스에서 극단적인 상황을 가정해보자.무게 1, 가치 100짜리 물건이 있다면 어떻게 될까이렇게,..

#11444 피보나치 수 6 https://www.acmicpc.net/problem/11444 제일 처음 접근했던 방식은, DP를 재귀로 돌리는 형태였다. import syssys.setrecursionlimit(10000)n = int(input())division = 1000000007dp = [0, 1]def find_fibo(n): # print(n) if n 하지만 재귀의 깊이가 너무 깊어졌다. 거의 반 포기상태로 참고자료를 봤고,점화식을 훨씬 더 함축적으로 개선해야함을 느꼈다.  최종적으로 파악한 점화식은 다음과 같다.*출처https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-11444-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%..

#11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660  역시 반복문으로 막 푸니까 시간초과가 난다. 과거에 DP를 풀었던 기억을 되내이며 고민했다.2차원으로 DP를 진행하면 된다.  import sysinput = sys.stdin.readlinen, m = map(int, input().split())maps = []dp = []# make dp and store originfor i in range(n): nums = [int(x) for x in input().split()] # store origin maps.append(nums) # make dp tmp = [] if i == 0: idx_0 = nums..

#17626 Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net DP 형태로 풀이하려다보니 잘 모르겠어서 검색했다. 풀이 과정은 이렇다. 문제에 따르면 모든 수는 4개 이하의 제곱수의 합으로 표현할 수 있다고 한다. j를 변수로 삼아 1 씩 키워나가며 j**2 과 목표값을 비교한다. dp[i-(j**2)] 부분에서는 목표값 i에서 j**2을 제외한 값의 dp값을 찾는다. 그러면 i-(j**..

#9461번 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 수열 문제인 만큼 단번에 DP임을 알아차렸다! 처음에는 주어지는 테스트 케이스를 모두 저장할 때, 정렬을 진행하면서 저장했다. 그리고 리스트 가장 오른쪽에 있는 수 (가장 큰 수)까지 dp 계산을 진행하고 각각의 케이스에 맞는 값을 출력했는데 시간초과가 났다. 그래서 단순히 최댓값을 별도의 변수에 추가로 저장하고 진행했더니 통과했다. 틀린 코드 with 정렬 (시간초과) n =..

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

#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 였고 맞추긴 ..