본문 바로가기

전체 글

 (138)
[백준] 1520 내리막길 / DP / Python / 골3 부제: 무한 런타임 에러 해결하기 처음에 접근하려고 했던건   일단 현재 위치가 0이 아니어야 어딘가로부터 이동경로를 받을 수 있다는 뜻그래서 0이 아닌 경우에만 탐색함 상하좌우에서 현재 위치로 이동하는 경우에상하좌우에서 받을 수 있는 max값을 현재 위치의 이동 가능 경로로 세팅해둠 그리고 현재 위치에서 상,하,좌,우로 이동할 때 현재 수보다 이동한 위치의 수가 작으면 내리막길이니까이동 가능 경로 개수를 업데이트 해주고 싶음각 상하좌우로 이동했을 때 위치에다가현재 위치의 이동 경로 개수를 그대로 받는 경우 또는... 이동한 위치의 이동 경로 개수+1 값을 비교해서max값으로 업데이트를 해줬음  m,n = map(int,input().split())arr = [list(map(int,input().spl..
[백준] 10942 팰린드롬? / DP / Python / 골4 https://www.acmicpc.net/problem/10942 부제: 시간초과와의 싸움너무 정직하게 구현했더니 시간초과 뜸질문에 따라 주어진 배열을 list[s:e+1]로 끊어서그 배열을 for문 돌려서 팰린드롬인지 검증했는데, 이렇게 하니까 시간초과 뜸dp를 쓰는 방법을 고민하자 n = int(input())l = list(map(int, input().split()))l.insert(0,0)m = int(input())for i in range(m): s,e = map(int,input().split()) temp = l[s:e+1] leng = len(temp) if leng==1: print(1) continue for j in range(..
[백준] 9251 LCS / DP / Python / 골5 최장 공통 부분 수열 LCS를 구현하는 문제이다 LCS 개념은 이분이 굉장히 잘 설명해 두셨음https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest..

티스토리툴바