본문 바로가기
반응형

백트래킹3

동적 계획법 (파이썬) 기본적인 접근 방식은 분할 정복 알고리즘과 비슷하다. 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결괏값을 이용해 원래 문제의 답을 산출한다. 그러나 동적 계획법은 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시 한 번 해당 문제를 풀 때에는 저장해둔 답을 바로 산출하여 속도를 향상한 것이다. 동적 계획벅을 구현하는 방법은 2가지가 있다. 하향식으로 문제를 풀어나가는 메모이제이션(Memoization) (주의 :메모라이제이션(Memorization) 아님!!) 상향식으로 문제를 풀어나가는 타뷸레이션(Tabulation) 즉, 계산했던 걸 저장한다라는 것이 핵심인 것이다. (캐싱이라고도 불림) 말로 하면 .. 2022. 2. 7.
백준 14888 : 연산자 끼워넣기 (파이썬) 연산자 끼워넣기https://www.acmicpc.net/problem/14888풀이 코드# https://teching.tistory.com/import sysn = int(sys.stdin.readline().rstrip())nums = list(map(int,sys.stdin.readline().split()))#operator 0: +, 1: -, 2: *, 3: /operator = list(map(int,sys.stdin.readline().split()))use_operator = [0, 0, 0, 0]answerMax = -1000000000answerMin = 1000000000def solve(idx,res): global n, answerMin, answerMax if i.. 2022. 2. 5.
백준 15649 : N과 M (1) (파이썬) N과 M (1)https://www.acmicpc.net/problem/15649코드1# https://www.acmicpc.net/problem/15649# https://teching.tistory.com/import itertoolsn, m = map(int,input().split())nums = [i+1 for i in range(n)]for ln in list(itertools.permutations(nums,m)): for i in range(m): print(ln[i],end= ' ') print('')코드 2# https://www.acmicpc.net/problem/15649# https://teching.tistory.com/def bts(n, m, visite.. 2022. 2. 1.
반응형

티스토리툴바