수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/2631

정답 풀이 

주어진 배열을 오름차순 정렬하기 위해 움직여야하는 최소 원소의 개수를 출력하는 문제

다이나믹 프로그래밍으로 주어진 배열에서 len(배열) - len(가장 긴 증가하는 부분수열)를 구하면 된다. 

가장 긴 증가하는 부분 수열의 원소들은 그대로 두고, 속하지 않는 원소들만 움직이면 최소한으로 원소를 움직일 수 있기 때문이다. 

풀이 과정

1. dp는 i번째 원소가 속하는 증가하는 부분수열의 최대 길이를 저장한다. 부분 수열에는 원소 개수가 최소 1개는 있으므로 1로 배열을 초기화한다. 

2. 주어진 원소를 순회하면서 arr[i](i번째 원소)와 arr[j] 원소([1, i - 1])에 대해 arr[i] > arr[j]인 경우에 대해 연산을 진행한다. 

    2-1. arr[i]> arr[j] 이므로 arr[i]는 이전의 arr[j]가 포함된 증가하는 부분수열에 포함될 수 있다. 그런데 이때 arr[i]가 다른 부분 수열에 속해있을 수 있으므로 dp[i]와 dp[j] + 1 중 최댓값을 dp[i]에 저장한다. 

dp[i] = max(dp[i], dp[j] + 1)

3. 이렇게 구한 dp의 값 중 최댓값이 가장 긴 부분수열의 길이이므로 이 값을 n에서 뺀다. 

n - max(dp)

n = int(input())

arr = [0]
for _ in range(n):
    arr.append(int(input()))
    
dp = [1] * (n + 1) # 원소가 하나인 부분 수열 있을 수 있기 때문
for i in range(1, n + 1):
    for j in range(1, i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

            
# 배열 길이 - 가장 긴 증가하는 부분 수열 길이
print(n - max(dp))

Reference

https://velog.io/@soobin519/Python-%EB%B0%B1%EC%A4%80-2631-%EC%A4%84%EC%84%B8%EC%9A%B0%EA%B8%B0

-문제:https://www.acmicpc.net/problem/14002

DP 2차 복습 끝. 몇 문제는 다시 푸니까 잘 풀렸지만, 아직 많은 문제들을 답지 보고 풀어야하는 상태이다. 

다시 봐야할 문제들 위주로 다시 풀어보려고 한다 

-정답 풀이: 

윗 부분은 기존 풀이랑 동일하다. 

수열에 해당하는 숫자는 거꾸로 가면서 ans 문자열에 추가해주면 된다 

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n

for i in range(n):
    for j in range(i+1):
        if data[i]>data[j] and dp[i]<dp[j]:
            dp[i]=dp[j]            
    dp[i]+=1
now=max(dp)
ans=''
for i in range(n-1,-1,-1):
    if dp[i]==now:
        ans=str(data[i])+' '+ans
        now-=1
    
print(max(dp))
print(ans)

-정답풀이 2:

이렇게 수정하니까 또 정답이다. 시간은 위의 풀이보다 2배 정도 더 걸렸다. 

아무래도 idx를 구하는데 문제가 있었던 것 같다 

n=int(input())
data=list(input().split())
dp=[[""]*n,[0]*n]

for i in range(n):
    for j in range(i+1):
        if int(data[i])>int(data[j]) and dp[1][i]<dp[1][j]:
            dp[0][i]=dp[0][j]
            dp[1][i]=dp[1][j]
    dp[0][i]+=(data[i]+" ")
    dp[1][i]+=1

now=max(dp[1])
idx=dp[1].index(now)
print(now)
print(dp[0][idx])

-시도해본 풀이:

부분 수열에 해당하는 숫자들을 따로 저장한 뒤 그거를 불러오는 로직을 생각했는데, 

계속 틀렸다. 아무래도 이 방법은 아닌 것 같다 

n=int(input())
data=list(input().split())
dp=[['']*n,[0]*n]

for i in range(n):
    for j in range(i+1):
        if int(data[i])>int(data[j]) and dp[1][i]<dp[1][j]:
            dp[0][i]=dp[0][j]
            dp[1][i]=dp[1][j]
    dp[0][i]+=(' '+data[i])
    dp[1][i]+=1

for i in range(1,n):
    if len(dp[0][i])>len(dp[0][i-1]):
        idx=i
answer=dp[0][idx]       
print(max(dp[1]))
print(answer[1:])

-문제: https://www.acmicpc.net/problem/10942

문자의 시작과 끝이 같은지 계속 비교해가면서 모두 같으면 팰린드롬이다. 

각자하면 시간이 오래 걸리므로 2차원 행렬을 만들어서 행은 시작점, 열은 끝점으로 지정한다음 

길이별로 팰린드롬 여부를 입력한다. 

여기서도 문자 길이가 1인지,2인지 3 이상인지에 따라 팰린드롬을 확인하는 여부가 다르기 때문에 

경우에 대해 잘 생각해야한다. 

자세한 풀이는 이 게시물을 확인하면 된다.

-정답풀이: 

import sys
input=sys.stdin.readline

n=int(input())
data=list(map(int,input().split()))
m=int(input())
dp=[[0 for _ in range(n)] for _ in range(n)]

for num_len in range(n): #문자열의 길이
    for start in range(n - num_len): #문자 시작 위치
        end= start + num_len 
        
        #문자 길이가 1임 -> 무조건 팰린드롬
        if start == end: 
            dp[start][end]=1
            
        #문자 길이가 2이상이고, 끝점이 같은 경우
        elif data[start]==data[end]:
            #문자 길이가 2인 경우
            if start+1 == end:
                dp[start][end] = 1
            #양 끝 숫자가 같고, 안에 숫자도 같은 경우
            elif dp[start+1][end-1] == 1:
                dp[start][end] = 1                
            
for _ in range(m):
    s,e=map(int,input().split())
    print(dp[s-1][e-1])

-시도해본 풀이

값이 입력될 때마다 완전 탐색으로 양끝을 비교한다.

이렇게 하면 시간초과한다 

n=int(input())
data=[0]+list(map(int,input().split()))
m=int(input())
flag=True

for _ in range(m):
    s,e=map(int,input().split())
    for i in range((e-s)//2 +1):
        if data[s+i] != data[e-i]:
            flag=False
    if not flag:
        print(0)
    else:
        print(1)

-문제: https://www.acmicpc.net/problem/1915

-정답 풀이:

값 입력 받을 때 주의하기 

띄어쓰기 없이 주어지고, 모양이 0100이므로 이진수로 읽힐 수 있어서 이를 list로 받아야한다 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
data = []
dp = [[0] * m for _ in range(n)]

for _ in range(n):
    data.append(list(map(int,list(input().rstrip())))) # 여기 split아님. 주의하기
    
answer = 0
for i in range(n):
    for j in range(m):
        if i == 0 or j == 0:
            dp[i][j] = data[i][j]
        elif data[i][j] == 0:
            dp[i][j] = 0
        else: 
            dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        answer = max(dp[i][j],answer)
        
print(answer ** 2)

-시도해본 풀이(틀림)

주변 값 중 최댓값을 사용해야한다고 생각했음. 

그리고 특정 위치 주변의 값들이 모두 같고, 0이 아닌 경우에 정사각형이 성립된다고 생각함. 

n,m=map(int,input().split())
dp=[]
for _ in range(n):
    dp.append(list(map(int,list(input().rstrip()))))
for i in range(1,n):
    for j in range(1,m):
        if dp[i][j]!=0 and dp[i-1][j-1]!=0:
            if dp[i-1][j]==dp[i][j-1] and dp[i][j-1]==dp[i-1][j-1]:
                dp[i][j]+=dp[i-1][j-1]
            else:
            #이 경우에 대해서는 생각 안하는 것 같기도
                dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
             
for i in range(n):
    answer=max(dp[i])
print(answer**2)