Algorithm
-
[BOJ-1780] 종이의 개수 PythonAlgorithm 2020. 7. 2. 18:03
cache.values(): # 파이썬의 재귀호출과 관련한 에러를 제어 import sys sys.setrecursionlimit(100000) #input_matrix=[[0, 0, 0, 1, 1, 1, -1, -1, -1], [0, 0, 0, 1, 1, 1, -1, -1, -1], [0, 0, 0, 1, 1, 1, -1, -1, -1], [1, 1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0], [0, 1, -1, 0, 1, -1, 0, 1, -1], [0, -1, 1, 0, 1, -1, 0, 1, -1], [0, 1, -1, 1, 0, -1, 0, 1, -1]] # 입력값 받기 _len = int(inp..
-
DP 동적 계획법Algorithm 2020. 7. 2. 17:35
1. 큰 문제를 작은 문제들로 나누어 해결한다 2. 작은 문제들은 결과값을 저장하여 다시 사용할 수 있도록 한다 ( 메모이제이션 ) 주로 greedy(그리디, 탐욕)알고리즘과 자주 비교된다. (공통) 둘다 전체 문제를 작은 문제단위부터 해결하여 최적점에 도달한다는 전략을 취하지만, (차이) greedy는 작은 문제단위에서 최선의 선택이 큰 문제에서의 최선의 선택과 일치되는 경우에 사용 가능하고, dp는 작은 문제단위에서 best선택을 하더라도 큰 문제에서 best가 보장되지 않을 때 사용하면 된다. 1. Top-Down 방식 : 초기의 큰 문제단위에서 작은 문제단위로 접근하며 : 재귀함수를 이용해 구현한다 1) 작은 문제들의 결과값을 저장할 변수를 만들고 모두 worst상태로 초기화한다 2) functi..