[묘공단]파이썬 스터디 12주차
동적 계획법
전체문제를 한번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법.
- 점화식 세우기와 동적계획법
- 문제를 해결하는 해가 이미 있다고 가정.
- 종료 조건 설정.
- 과정 1,2를 활용해 점화식 세우기
점화식 구현: 재귀 활용
def fact(N):
if N == 1:
return 1
else:
return fact(N-1) * N하지만, 스택 메모리에 함수 호출 정보가 많이 쌓이므로 메모리 한계로 런타임 오류가 발생할 수 있음. 따라서 재귀 호출을 해서 문제가 생겼거나, 생길 거 같을 때 취할 수 있는 방법은 다음과 같다.
- 재귀 호출 자체를 쓰지 않는 법 : 반복문
- 재귀 호출의 횟수를 줄이는 법 : 메모이제이션
- 재귀 호출의 횟수를 줄여주는 메모이제이션
재귀 호출의 횟수를 줄이는 방법. 반복 연산 횟숫를 줄여 알고리즘의 성능을 올려줌.
점화식 구현: 재귀+메모이제이션 활용
1) 메모이제이션을 위한 저장소 생성 : 이미 구한 해를 저장할 공간을 생성.
2) 재귀 함수 정의 : 점화식을 재귀로 표현할 함수를 정의한다. 이때 함수의 세부 구현은 고려하지 않는다.
3) 재휘 함수의 종료조건을 정의
4) 재귀 함수의 일반 연산 처리
fibodata = [0] * (N + 1)
def fibo(N):
if fibodata[N] != 0:
return fibodata[N] # 메모이제이션 활용
if N <= 2:
fibodata[N] = 1 # 메모이제이션, 종료조건
else:
fibodata[N] = fibo(N-1) + fibo(N-2) #메모이제이션, 일반항
return fibodata[N]
- 최장 증가 부분 수열
부분 수열이란?
주어진 수열 중 일부를 뽑아 새로 만든 수열.
최장 증가 부분 수열이란?
부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열.
LTS의 길이 동적 계획법으로 구하기
길이가 가장 긴 증가하는 부분 수열 찾기.
LTS의 특징
- 숫자가 점점 증가함.
- 원소 간의 전후 관계는 유지함.
- 최장 공통 부분 수열( LCS )
특정 순서로 숫자를 나열하는 것. 두 수열이 어떤 기준에 따라 양쪽에서 공통으로 발견 할 수 있는 가장 긴 부분 수열을 의미.
LCS 길이 점화식 생각하기
- 두 문자열의 특정 문자가 같은지
- 같다면 찾은 두문자의 위치가 이전에 찾은 문자의 다음에 있는지
문제풀이
- 가장 큰 정사각형 찾기
0 1 1 1 0 1 1 1
1 1 1 1 1 2 2 2
1 1 1 1 1 2 3 3
0 0 1 0 ....
처음 작성한 코드에서 난 에러 (case1 실패) :
1*1 정사각형을 고려해서 그 부분을 따로 처리해줘야함. case1이 그런 경우인듯함.
처음 작성한 코드는 자꾸 case 1에서만 실패가 나옴.
def solution(board):
answer = 0
row_num = len(board)
col_num = len(board[0])
# 주어진 board를 돌면서 가장 큰 정사각형 찾기
for i in range(1, row_num):
for j in range(1, col_num):
if board[i][j] == 1:
left = board[i-1][j]
left_up = board[i-1][j-1]
up = board[i][j-1]
# 주변의 왼쪽, 왼쪽위, 위 값 중 최솟값 + 1을 현재 값으로 갱신
board[i][j] = min(left, left_up, up) + 1
# print(type(board[i][j]))
answer = max(answer, board[i][j])
# 정사각형의 넓이 반환
return answer ** 2
def solution(board):
answer = 0
row_num = len(board)
col_num = len(board[0])
if row_num == 1 and col_num == 1: # 1*1정사각형의 경우
return board[0][0]
# 주어진 board를 돌면서 가장 큰 정사각형 찾기
for i in range(1, row_num):
for j in range(1, col_num):
if board[i][j] == 1:
left = board[i-1][j]
left_up = board[i-1][j-1]
up = board[i][j-1]
# 주변의 왼쪽, 왼쪽위, 위 값 중 최솟값 + 1을 현재 값으로 갱신
board[i][j] = min(left, left_up, up) + 1
answer = max(answer, board[i][j])
return answer ** 2
초반에 if 문 사용안하고 answer를 현재 배열에서 가능한 가장 큰 정사각형의 크기로 설정하고, 나중에 갱신하는 방식
def solution(board):
row_num = len(board)
col_num = len(board[0])
# 주어진 board를 돌면서 가장 큰 정사각형 찾기
answer = max(map(int, board[0])) # 첫 번째 행에서 가능한 가장 큰 정사각형 크기로 초기화
for i in range(1, row_num):
for j in range(1, col_num):
if board[i][j] == 1:
left = board[i-1][j]
left_up = board[i-1][j-1]
up = board[i][j-1]
# 주변의 왼쪽, 왼쪽위, 위 값 중 최솟값 + 1을 현재 값으로 갱신
board[i][j] = min(left, left_up, up) + 1
answer = max(answer, board[i][j])
return answer ** 2