본문 바로가기

전체 글

 (82)
[DP] boj 11057 - 오르막 수 백준 11057은 재귀로 풀면 recursion 에러가 난다. 호출 제한을 걸어둔 게 있기 때문에 그런데, 아래 코드로 제한을 늘릴 수 있다. import sys sys.setrecursionlimit(10000) 이렇게 해서 풀긴 했는데 재귀가 아닌 방법으로 다시 풀어야겠다. 재귀로 푼 방법 import sys sys.setrecursionlimit(10000) def calc(num, __cache = {1:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]}): if num in __cache: return __cache[num] __cache[num] = [] for i in range(1, 11): __cache[num].append(sum([calc(num-1)[j-1] for j in r..
[DP] boj 2133 - 복잡한 점화식 백준 2133은 점화식을 완전히 이해하는 데 시간이 걸렸다. 가장 도움 된 참고 링크 점화식 설명 n일 때의 결과를 f(n)이라고 쓰면 1. n은 짝수 : 3xn을 1x2와 2x1로 채우려면 n은 반드시 짝수여야 된다. 2. f(n-2) * f(2)는 기본으로 깔고 간다 : f(n)을 f(n-2)의 우측에 빈 바닥 3x2가 생겼다고 보는 관점. 3. 특이 케이스를 왼쪽만 계산했기 때문에 우측도 세야 된다 : 빈 바닥이 우측이 아니고 좌측에 생겼다면 이 때 2번과 다른 경우가 없는지 확인이 필요하다. 대부분의 경우는 중복이겠지만, 특이케이스와 연관된 경우는 그림이 다르니 더해줘야 된다. n = 8일 때를 예로 들자면, f(8-6) * (n = 6일 때의 특이케이스 2가지) + f(8-4) * (n = 4일..
[DP] boj 11053, 11054, 11055, 11722 - 가장 긴 증가하는 부분 수열(LIS) 백준 11053, 11054, 11055, 11722 문제는 LIS(Longest Increasing Subsequence) 유형이다. 11053 숫자 범위 전체를 배열로 만들고 slicing을 사용하는 방법이 있다. 참고 링크 이분탐색으로도 가능하다. 참고 링크 지금 찝은(i) 기준 원소의 좌측에서 보다 작은 값이 있는지 찾고, 그 작은 값이 갖고 있는 증가 수열의 최대값을 가져옴. 좌측의 원소를 다 검사해서(for j in range(i)) 그 중 유효(원소 값이 기준 원소보다 작은)하면서 가장 긴 증가 수열의 길이(tempMax)를 가져오고, 1을 추가해 지금 기준 원소 포함, 이걸 끝으로 하는 증가 수열의 최대 길이를 저장한다. 증가 수열의 최대 길이만 저장해둔 tempArr에서 가장 큰 값을 정..
[DP] boj 11726, 11727 - 2xn 타일링 + 연결 문제 2133 백준 11726, 11727은 점화식으로 해결할 수 있다. 현재 값과 이전 값들이 어떤 관계를 갖는지 찾는 게 점화식인데, 이 개념을 단순한 숫자 간의 계산보다 그림으로 이해하게 해주는 문제들이다. 너비 i를 채울 수 있는 경우의 수는 직전의 너비 i-1에서 가장 오른쪽에 생긴 빈칸 1x2를 채우는 경우의 수 + 너비 i-2에서 가장 오른쪽에 비워둔 빈칸 2x2를 채우는 경우의 수의 합이다. for문을 도는 대신 재귀 함수를 선언하고 이전에 계산한 값을 보존하는 방법을 찾았다. 이를 이용하는 게 더 빠르다. 메모리 차이는 아직 모르지만... 11726 방법 1 import sys n = int(sys.stdin.readline()) dp = {1:1, 2:2} for i in ra..
[DP] boj 1912 - 연속합 백준 1912는 판단할 값을 입력 배열과 index를 맞춘 배열로 저장해서 해결한다. 참고 링크 방식은 같은데 속도가 더 빠른 풀이를 발견했다. 변수를 하나 없앴고 배열을 초기화하는 방법이 다르다. 참고 링크 성공한 방법 import sys n = int(sys.stdin.readline()) inputArr = list(map(int, sys.stdin.readline().split(' '))) temp = [0 for _ in range(n)] maxVal = -1001 for i in range(n): temp[i] = max(temp[i-1]+inputArr[i], inputArr[i]) maxVal = max(maxVal, temp[i]) print(maxVal) 실패한 방법 시간 초과 - O(..

티스토리툴바