본문 바로가기

전체 글

 (152)
[백준] 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..
[백준] 1915 가장 큰 정사각형 DP / python 골4 https://xn--acmicpc-lw16a.net/problem/1915 DP를 이용 뭔가 BFS같이 생겼는데, 아니었다 처음에는 정사각형을 판별하려면 2차원 배열을 돌아가면서 뭘 봐야 할까...하다가현재 원소의 아래한칸 원소와 오른쪽한칸 원소를 보면 정사각형 여부를 알 수 있을까? 하면서 탐색했다하지만 정사각형을 판별하는 방법이 되지는 못했고... 알고보니 현재 원소의 위쪽 한칸 원소와 왼쪽 한칸 원소, 대각선 왼쪽 위 원소를 봐야했다  현재 원소가 0이 아니라면왼쪽, 대각선 왼쪽 위, 위쪽 원소 3개를 보고,세 값의 min 값을 현재 원소에 더해준다 일단 정사각형이 형성 가능하려면,현재 원소의 왼쪽, 왼쪽 위, 위쪽으로 같은 값만큼 확장이 되어야 하기 때문에최대값을 고려하면, 그게 정사각형이 아니..

티스토리툴바