본문 바로가기

dp33

[BOJ][Python]1005 풀이 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net import sys; ssr = sys.stdin.readline sys.setrecursionlimit(10000) def f(node): if dp_delay[node] == -1: results = [] for child in build[node]: child_delay = f(child) results.append(child_delay) dp_delay[node] = delays[no.. 2023. 11. 24.

[BOJ][Python]17070 풀이 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net import sys; ssr = sys.stdin.readline def f(cur_r, cur_c, cur_dir): global ans if cur_r == n-1 and cur_c == n-1: ans += 1 return else: if cur_dir == 0 or cur_dir == 1: if cur_c+1 < n and board[cur_r][cur_c+1] !.. 2023. 10. 30.

[Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드 이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다. 사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다. .. 2023. 10. 5.

[BOJ][Python]11054 풀이 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net def f(n, arr): dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면 if dp[i] < dp[j]+1: dp[i] = dp[j]+1 return dp n = int(input()) a = list(map(int, input().split())) dp = f(.. 2023. 10. 4.

[BOJ][Python]2096 풀이 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net import sys ssr = sys.stdin.readline def max_dp(): scores = [board[0][0], board[0][1], board[0][2]] dpos = (-1, 0, 1) for r in range(n): if r == n-1: break tmps = [i for i in scores] scores = [tmps[i]+board[r+1][i] for i in range(3).. 2023. 8. 22.

[BOJ][Python]1904 풀이 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net n = int(input()) if n == 1 or n == 2 or n == 3: print(n) else: dp = [0 for _ in range(n+1)] dp[1], dp[2] = 1, 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2])%15746 print(dp[n]) 뻔한 dp 문제입니다. n 범위 때문에 index 에러가 나니까 예외처리를 하.. 2023. 7. 11.

[BOJ][Python]2193 풀이 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net n = int(input()) t = [0 for _ in range(91)] t[1] = 1 for i in range(2, 91): t[i] = 1 + sum(t[:i-1]) print(t[n]) 뻔한 dp 문제입니다. 조건 1과 2에 의해서 앞의 두 자리는 10으로 고정되기 때문에 사실상 3번째부터 n번째 까지 가능한 조합을 따지는 건데 그 조합들은 이미 앞에서 구한게 있으니 그대.. 2023. 3. 3.

[BOJ][Python]11660번 풀이 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net import sys ssr = sys.stdin.readline n,m = map(int, ssr().split()) num = [list(map(int, ssr().split())) for _ in range(n)] dp = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): dp[i][0] = .. 2022. 7. 31.

[BOJ][Python]9465번 풀이 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net import sys ssr = sys.stdin.readline t = int(ssr()) for _ in range(t): n = int(ssr()) sticker = [list(map(int, ssr().split())) for _ in range(2)] dp = [[0 for _ in range(n)] for _ in range(2)] dp[0][0], dp[1][0] = stic.. 2022. 7. 30.

[BOJ][Python]1932번 풀이 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net import sys ssr = sys.stdin.readline n = int(ssr()) t = [list(map(int, ssr().split())) for _ in range(n)] dp = [[0]*(i+1) for i in range(n)] dp[0][0] = t[0][0] for i in range(1,n): for j in range(i): dp[i][j] = max(dp[i-1][j]+t[i][j], dp[i][j]) dp[i][j+1] = dp[i-1].. 2022. 7. 28.

이전 1 2 3 4 다음

티스토리툴바