본문 바로가기

dp

 (10)
[ BOJ / 파이썬 ] 14501.퇴사 공부의 참맛을 느껴가는 중... 아 기분 좋다 진짜 ..🤸‍♀️ 해당 문제는 현재 한국 코테 바이블 이코테에 수록되어 있는 문제인데 대학 다니면서 처음 코딩테스트에 대해 접한 초반에 풀어보고 진짜 이해가 도통 되지 않아 좌절했던 문제다. 풀이가 이해된 뒤에도 뒤에서부터 인덱스를 접근해야만 이 문제를 풀 수 있나..? 싶어서 계속 의아했었는데 드디어 내 사고방식에 근거해서 이 문제를 풀 수 있었다. n = int(input()) T = [] P = [] total = [0] * (n+1) for i in range(n): time, price = map(int, input().split()) T.append(time) P.append(price) for i in range(n): if i > 0: tota..
[ BOJ / 파이썬 ] 9461. 파도반 수열 dp 좋다.. 감이 잡히니까 확실히 내 타입 문제란 걸 알겠다. 원래도 규칙성 있는 걸 좋아해서 수열 문제 좋아했는데, DP자체가 일반항 세우는거라 불규칙성 속에서 규칙 찾아내는 게 핵심이라 수열 문제가 많은 것이었다. 그래서 DP가 비교적 난이도가 쉬운 문제도 많이 분포하는 것이었다. 그러니까 DP문제는 사실상 DP테이블을 만드는 자체가 힘든게 아니라 DP테이블, 즉 메모제이션(탑다운 방식)을 차용할 생각만 떠올리면 되는것이고, 그 규칙을 찾아내느냐가 핵심인 경우가 많았다. 물론 내가 문제를 아직 많이 못 접해서 DP테이블을 어렵게 사용하는 걸 모르기 때문에 하는 얘기일 수도 있다. 어렵게 내려면 엄청 어려워질 수 있다고 한다. 뭐 이거야 계속 하다보면 늘겠지.. 하여간 해당 문제는 이게 수열이라는걸 ..
[ BOJ / 파이썬 ] 1932. 정수삼각형 오.. 이제 DP는 어느정도 감 잡아가는 느낌이다 이예에 ~ 진짜 몇 달 전에 이 정도 문제도 감이 안 잡혔었는데... 정말 난독증이었던걸까.. 🙄😥 하여간 데이터 배열 자체에 메모제이션으로 해결할 수 있는 간단한 문제였다. 대신 핵심포인트는 해당 열의 첫 값과 끝 값을 예외처리해줘야 함. n = int(input()) triangle = [list(map(int, input().split())) for _ in range(n)] for i in range(1, n): row = triangle[i] triangle[i][0] += triangle[i-1][0] for j in range(1, len(row)-1): triangle[i][j] += max(triangle[i-1][j], triangle[..
[ BOJ / 파이썬 ] 1003. 피보나치 함수 너무 흔한 재귀 함수 문제인 줄 알았는데 시간제한이 빡빡해서 최대값 40을 찍어보니 아 역시.. 어차피 바텀업 느낌으로 가는 문제이고 하위 문제를 상위에서 갖다 쓰는거라 중복을 최소화할 방법을 찾고자 했다. 그냥그냥 DP로 풀 수 있었다! 피보나치 자체가 n >= 2 부터 fibo(n) = fibo(n-1)+fibo(n-2)의 식을 갖고, 3까지 찍어보니 정말 그 아래 값들의 0과 1등장횟수를 각각 더해주면 된다. 처음에는 피보나치 함수 자체에서 해당 테이블을 갱신하려고 했으나, 일단 일반식을 얻어낸 이상 그냥 dp 테이블 정의하고 for문 돌려 착착 순서대로 채우면 되는거였다. tc = int(input()) for testCase in range(tc): result = [0, 0] n = int(i..
[ BOJ / 파이썬 ] 1912 연속합 으 .. 아직 DP연습량이 안 쌓인건 알았지만, 이렇게 DP아이디어가 아예 안 떠오를 줄은 몰랐다. 심지어 1시간 지나고 포기한 이제야 아 이게 DP문제라서 풀려고 선택한 문제지.. 라고 풀이유형이 이제 생각난다. 진작에 생각 났어도 몰랐겠지만.. ㅎ 계속 경험치 쌓자. 1차 아이디어. 쭉 가다가 감소 나오면 일단 끊는다. 그리고 이전에 끊긴 양수값과 비교해 큰 값을 남겨놓는다. => 문제 로직에 안 맞음. 2차 아이디어. 나름 참신하게 한다고 했는데 그냥 1차 아이디어를 뒤에서부터 접근하는 식이 되었다. 각 값에 이어지는 최댓값을 따로 테이블에 적어줄 뿐이었다. 메모제이션스럽게 한다고 흉내낸 생각인데 스스로 반례 발견해서 포기. 애초에 잘못된 접근인걸지도. 3차 아이디어. 일단 전체 데이터 쭉 훑으면서..
[ BOJ / 파이썬 ] 11659 구간 합 구하기 4 아 나는 확실히 PS를 잘 못 풀고 있었던 것일까? 아니면 시간을 들였기 때문에 이제야 문제 푸는 느낌나게 푸는건가? 이제야 뭔가 로직이 로직답게 만들어지는 것 같다. 0) 문제 정의 n개의 문자 배열 중에 i , j 받았을 때 i~j 범위의 문자 배열 값들의 합 1) DP테이블 정의 dp[n]은 n까지의 num들의 합 dp[j] = dp[j-1] + num[j] 2) 점화식 구하기 보통 순차적인 합이 있을 때, 특히 DP테이블의 누적 합이므로 dp [j] ~ dp[i] = dp[j] - dp[i-1] 3) 초기값 dp[0] = 0으로 해주고, num에 따라서 합을 누적해서 넣어서 dp테이블 채우기. / 첫 번째 제출 / import sys input = sys.stdin.readline n, m = m..
[ BOJ / 파이썬 ] 11726 2xn 타일링 사실 수학적 센스가 필요한 문제라 처음 만나면 풀어낼 자신은 없다. 대신 해설을 보고나면 구현 자체는 어렵지 않다. DP문제는 많이 풀어보는 것이 힘! 코딩테스트는 경험이 힘! 해당 문제는 일단 DP로 풀 수 있다는 것을 알아채기도 까다로운 것 같다. 그런데 점화식을 세우는게 진짜 아리송하다. 다만 우리에게 주어진 경우의 수가 사실은 몇 개 되지 않는다는 사실, 배치가 중복된다는 사실을 파악하면 되는 문제다. 2 x 1 1 x 2 를 놓는데, dp테이블을 dp[i] 가 2 x i 를 채우는 방법의 수라고 할 때, dp[1] = dp[n-1] 이다. 왜? 2 x n 바닥에서 2 x 1을 뺐으니 남은 건 2 x (n-1) 바닥이기 때문에. 2 x (n-1) 바닥을 채우는 수와 같기 때문. 1 x 2 의 경우..
[ BOJ / 파이썬 ] 1149 RGB거리 import sys input = sys.stdin.readline n = int(input()) R = [] G = [] B = [] for i in range(n): r, g, b = map(int, input().split()) R.append(r) G.append(g) B.append(b) d = [[0] * 3 for _ in range(n)] d[0][0] = R[0] d[0][1] = G[0] d[0][2] = B[0] for i in range(1, n): d[i][0] = min(d[i-1][1], d[i-1][2]) + R[i] d[i][1] = min(d[i-1][0], d[i-1][2]) + G[i] d[i][2] = min(d[i-1][0], d[i-1][1]) + B[i] pri..
[ BOJ / 파이썬] 2579 계단 오르기 정말 간만에 PS문제 푸니까 또 재밌고 할 만한 것 같다. 그리고 조금 원리를 이해해서 푸는 느낌이 나니 문제 풀이력이 느는 느낌이 확실히 든다. 역시 일이 진행되다가 너무 답도 없이 고여버리면 잠시 쉬고 오는 것도 ( 노는게 아니라 비슷한 다른 일 ..^^) 좋은 것 같다. 사담은 여기까지 하고, 우선 해당 문제가 DP라는 정보를 알고 부딪힐 수 있었다. 그래서 더 답에 빠르게 가까워진 것 같다. 1. DP테이블을 어떻게 구성할 지, 어떤 내용을 담을 지를 결정하고, 2. 점화식을 세우고 3. 초기값을 셋팅하는 식으로 풀어라 라고 배웠다. 되게 초보자 티 내는 듯이, DP테이블을 무조건 1차형으로 사용해야한다고 생각했다. 문제 풀이 경험의 부족 때문일 것이다. 이 값을 갖는 계단이 n개 있으므로 1줄의..
[ BOJ / 파이썬 ] 1463 1로 만들기 지금 피곤해서 그런지 솔직히 DP 개념이 잘 머리에 안 들어온다. 그래서 DP문제치고 굉장히 쉬운 편에 속하는 해당 개념도 인식이 잘 안 됐다. 30분 책상에 엎드려서 자고 왔다. import sys input = sys.stdin.readline x = int(input()) dp = [0]*(x+1) for i in range(2,x+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i],dp[i//3] + 1) if i % 2 == 0: dp[i] = min(dp[i],dp[i//2] + 1) print(dp[x]) 다른 분의 코드를 보니 코드 자체는 이해 가는데, 이걸 내가 습득한 개념처럼 안 다가온다. 조금 쉬고 다시 보자. 1. 테이블 정의하기 :..

티스토리툴바