[Algorithm] 백준 1912 연속합 | 파이썬 (DP, Dynamic Programming)
※ 1912 연속합https://www.acmicpc.net/problem/1912 문제 해결 TIP현재값이 큰지, 이전 dp값과 현재값을 더한 값이 큰지 비교해야 한다. dp의 상태는 다음과 같이 변화한다. 최종 dp의 max값을 출력하면 된다. 전체 코드 n = int(input())number = list(map(int,input().split()))#number = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]dp = [-10000]*(n+1)dp[0] = number[0]for i in range(1,len(number)): dp[i] = max(dp[i-1]+number[i],number[i])print(max(dp))
2024. 7. 10.
[Algorithm] 백준 18353, 이코테 병사 배치하기, 최장 증가 부분 수열 | 파이썬 (DP, Dynamic Programming)
※ 18353 병사 배치하기https://www.acmicpc.net/problem/18353 문제 해결 TIP최장 증가 부분 수열이란?예를 들어 다음 수열이 주어졌다고 하자.3 5 7 9 2 1 4 8위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.3 7 9 1 4 8 (5, 2 제거)7 9 1 8 (3, 5, 2, 4 제거)3 5 7 8 (9, 2, 1, 4 제거)1 4 8 (3, 5, 7, 9, 2 제거)위와 같이 일부, 혹은 전체가 오름차순인 수열을 '증가 부분 수열'이라고 한다. 그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다. 즉, 위의 수열의 집합에선 부분수열 3 5 7 8이 LIS이다. O(N^2) 알고리즘으로 구현할 수 있다. 새로운..
2024. 7. 7.
[Algorithm] 이코테 금광 | 파이썬 (DP, Dynamic Programming)
[문제]n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.만약 다음과 같이 3 x 4 크기의 금광이 존재한다고 가정합시다.가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) → (3, 2) → (3, 3) → (3, 4)의 위치로 이동하면 총 19만큼의 금을 ..
2024. 7. 6.
[Algorithm] 프로그래머스 멀리 뛰기 | 파이썬 (DP, Dynamic Programming)
※ 멀리 뛰기https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 TIPn이 1일 때부터 생각해보자. dp[1] = 1, 2라면 1씩 2번, 2씩 1번 총 2이다. dp[3]은 (1,1,1),(2,1),(1,2) 3이다. dp[4] = 5, dp[5] = 8이므로 피보나치 수열이 떠오른다. 전체 코드def solution(n): if n == 1: return 1 else: dp = [0] * (n+1) ..
2024. 7. 5.
