https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=javascript코드function solution(sequence) { let answer = Number.NEGATIVE_INFINITY; let odd = 0; let even = 0; for (let i = 0; i 처음에는 1로 시작하는 펄스 수열을 곱하는 경우와 -1로 시작하는 펄스 수열을 곱하는 경우 2가지로 나누어서 투포인터 알고리즘을 사용하려고 했는데, 20점만 맞고 틀렸다...다시 생각해보다가 모르겠어서 찾아보니 카데인 알고리즘을 사용하면 된다고 나왔다. 카데인 알고리즘에 대한 자세한 설명은 아래에 있다. Kadane’s Algorithm (카데..
문제풀이/DP
https://school.programmers.co.kr/learn/courses/30/lessons/12913코드function solution(land) { let answer = 0; const n = land.length; const dp = Array.from(new Array(n), ()=>new Array(4).fill(0)); for(let i = 0;i 땅따먹기는 행을 하나씩 차례로 밟으면서 내려와야 한다. 그 말은 k번째 행으로 오기 위해서는 k-1행을 무조건 거쳐야 한다는 말이다. 이런 경우에는 이전에 저장된 값을 이용하여 연산 횟수를 줄이는 DP(Dynamic Programming)을 사용하면 시간 복잡도를 작게 만들어서 풀 수 있다. 2차원 배열 `dp`는..
https://www.acmicpc.net/problem/16400코드n = int(input())def prime_number(n): is_prime = [True]*(n+1) is_prime[0] = False is_prime[1] = False prime = [] for i in range(2, n+1): if is_prime[i]: for j in range(i*2, n+1, i): is_prime[j] = False prime.append(i) return primeprime = prime_number(n)dp = [0]*(n+1)dp[0] = 1for p in prime: for..
https://www.acmicpc.net/problem/14267코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())boss = [0]+list(map(int, input().split()))compliments = [0]*(n+1)for _ in range(m): i, w = map(int, input().split()) compliments[i] += wfor i in range(2, n+1): compliments[i] += compliments[boss[i]]print(*compliments[1:]) 해당 문제는 트리디피 알고리즘으로 풀 수 있는 문제에 속하긴 하지만, 문제의 조건이 쉬워서 DP만으로도 풀 ..
https://www.acmicpc.net/problem/17208코드import sysinput = sys.stdin.readlinen, m, k = map(int, input().split())orders = []for _ in range(n): x, y = map(int, input().split()) orders.append((x, y))dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]answer = 0for order_idx in range(1, n+1): now_burger, now_fry = orders[order_idx-1] for burger in range(m+1): for fry in range(..
