Algorithms, Data Analytics

문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

n, s, m = map(int, input().split())
v = list(map(int, input().split()))

res = [[0] * (m + 1) for _ in range(n + 1)]
res[0][s] = 1

for i in range(n + 1):
    
    for j in range(m + 1):
        
        if (not res[i - 1][j]):
            continue
            
        if j - v[i - 1] >= 0:
            res[i][j - v[i - 1]] = 1
            
        if j + v[i - 1] <= m:
            res[i][j + v[i - 1]] = 1

result = -1

for i in range(m, -1, -1):
    
    if res[n][i] == 1:
        
        result = i
        break
        
print(result)

처음에는 볼륨값을 변수로 잡아두고 해결하려고 했다.

하지만 조절할 수 있는 볼륨의 값에 따라 연주할 수 있는 볼륨이 여러개가 되기 때문에 이 방법은 안된다고 생각했다.

그냥 표에다가 표시하면 되는데 왜 볼륨값을 변수에 잡아두려고 했을까

표시만 하고 조건에 맞게 가져오기만 하자

잡아두려고 하지말자

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

x = input()
y = input()
res = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]

for i in range(1, len(x) + 1):
    
    for j in range(1, len(y) + 1):
        
        if x[i - 1] == y[j - 1]:
            res[i][j] = res[i - 1][j - 1] + 1
            
        else:
            res[i][j] = max(res[i][j - 1], res[i - 1][j])
            
print(res[len(x)][len(y)])

전에 풀었던 문제 중에 가치와 무게가 주어지고 최대 가치로 담는 가방 문제가 있었다.

그 문제와 상당히 유사하다.

하지만 처음 마주한 다면 문제해석이 난해할 수 있다.

문제 해석하는데 난해했다 ㅋㅋㅋㅋ

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

n = int(input())
array = list(map(int, input().split()))
res = [1] * n

for i in range(1, n):
    
    for j in range(0, i):
        
        if array[j] < array[i]:
            res[i] = max(res[i], res[j] + 1)
            
print(max(res))

i를 기점으로 0부터 j 까지 i와 비교한다는 생각을 하기가 힘들었다.

이런 유형은 외워야하나?

바로 생각을 떠올리기 힘들었음.