본문 바로가기

전체 글

 (84)
[DP] boj 9465 - 2행 배열에서 점화식 구하기 백준 9465는 이제까지의 dp 문제와 조금 다르게 입력값이 2행으로 존재하는 배열이다. 초기화할 때 1차원 리스트는 dp = [0] * n 이렇게 하면 되는데, 2행짜리 2차원 리스트는 dp = [ [0] * n ] * 2 또는 dp = [ [0] * n for _ in range(2) ] 형태로 만들어야 된다. 여기서 속도를 더 높이려면 함수화하거나 참고 링크처럼 dp를 따로 선언하지 않고 입력 배열에 더해나가야 될 것 같다. import sys t = int(sys.stdin.readline()) for _ in range(t): n = int(sys.stdin.readline()) matrix = [list(map(int, sys.stdin.readline().split(' '))) for _ i..
[그래프] boj 2331 - 반복수열 백준 2331은 DFS로 풀었다. 연산 방식에 변화가 없기 때문에 수열에 이미 존재하는 수가 다시 등장한다면 반복이 확실하다. 이 생각을 가져야 풀 수 있는 문제 같다. 스터디 이후 생각: str으로 변환해서 새 변수에 넣고, 그 변수 째로 for문을 돌았다면 코드 가독성을 높일 수 있었다. [i : i+1] 대신 for x in string의 x import sys def calcNew(n): temp = 0 for i in range(len(str(numbers[n-1]))): temp += int(str(numbers[n - 1])[i:i + 1]) ** p return temp a, p = map(int, sys.stdin.readline().split(' ')) n = 0 numbers = []..
[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에서 가장 큰 값을 정..

티스토리툴바