본문 바로가기

Algorithm

 (13)
[DP] boj 9251 - 2차원 리스트 이용하기 백준 9251은 중간 과정 값을 저장하는 리스트를 2차원으로 써야 되는 문제다. 실행 시간이 더 짧은 다른 사람의 풀이를 보니 문자열의 길이를 구하는 걸 변수에 할당한 다음 사용했다. import sys s1 = sys.stdin.readline().rstrip() s2 = sys.stdin.readline().rstrip() dp = [[0] * (len(s1)+1) for _ in range(len(s2)+1)] for i in range(1, len(s2)+1): for j in range(1, len(s1)+1): if s1[j-1] == s2[i-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) print(d..
[그래프] boj 2667, 4963 - 사방팔방을 한 칸씩 탐색하기 백준 2667, 4963은 주변 탐색 유형의 기본이다. 2667 방법 1 상하좌우 네 방향을 탐색한다. 사방으로 갈 때 각각 dx와 dy로 주어진 배열에서 같은 index를 뽑아내 쓴다. 그래프 바깥으로 넘어가지 않도록 조건을 꼭 걸어야 된다. 참고 링크 2667은 입력 그래프가 정사각형이지만 4963은 가로와 세로의 크기가 반드시 같진 않은 문제다. import sys def dfs(x, y): global cnt visited[x][y] = True if graph[x][y] == 1: cnt += 1 for i in range(4): # 네 방향 nx = x + dx[i] ny = y + dy[i] if 0 0 and g[i][j - 1] == '1': rDFS(g, i, j - 1) # 왼쪽, 바..
[DP] boj 11052 - 카드 가장 비싸게 구매하기 백준 11052는 보기엔 뭐가 많은데 DP로 하자면 그렇지 않다. 예전에 이걸 DP가 아닌 걸로 도전해본 흔적이 남아있었는데 완전 개고생이다. import sys n = int(sys.stdin.readline()) # 구매하려고 하는 카드의 개수 price = [0] + list(map(int, sys.stdin.readline().split(' '))) total = [0] * (n+1) total[1] = price[1] total[2] = max(price[2], total[1] + price[1]) for i in range(3, n+1): temp = total[1] + total[i - 1] for j in range(2, i//2 + 1): temp = max(temp, total[j] +..
[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에서 가장 큰 값을 정..
[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(..

티스토리툴바