동적계획법 - 몸풀기 문제

문제 70 LCS 길이 계산하기

주어진 두 개의 문자열 str1과 str2에 대해 최장 공통 부분 수열의 길이를 계산하는 함수 구현

def solution(str1,str2):
	m=len(str1)
    n=len(str2)
    
    # 1부터 시작하니까 1씩 더해주어야 함
    dp=[[0]*(n+1) for _ in range(m+1)]
    
    for i in range(1,m+1):
    	for j in range(1,n+1):
        	
            # 코드에서는 0부터 시작해야하니까 -1씩 해줌
        	if str1[i-1]==str2[j-1]:
            	dp[i][j]=dp[i-1][j-1]+1
            else:
            	dp[i][j]=max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]            
            

문제 71 LIS 길이 계산하기

정수 배열 nums에서 LIS의 길이를 찾는 함수 구현

def lis(nums):
	n=len(nums)
    
    # dp[i]는 nums[i]를 마지막으로 하는 LIS의 길이를 저장하는 배열
    dp=[1]*n
    
    # 현재 위치를 하나씩 확인
    for i in range(1,n):
    	# i 이전의 모든 값 확인
    	for j in range(i): 
        	if nums[i] > nums[j]:
            	dp[i]= max(dp[i],dp[j]+1)
    return max(dp)            
   

문제 72 조약돌 문제

3행 N열의 가중치가 있는 배열 arr이 주어짐
다음 규칙을 준수하면서 조약돌을 놓을 때 최대 가중치의 합을 반환하는 함수 구현

• 각 열에 조약돌은 적어도 하나 놓아야 함
• 각 조약돌에 바로 인접한 위치 (상하좌우)에 조약돌을 놓을 수 없음
  
  문제에서 "상하좌우 인접 금지"라는 제약이 있기에, 특정 열의 최적 배치는 바로 이전 열의 배치와만 연관