알고리즘124 가장 큰 증가 부분 수열[백준 11055] - python import sys input = sys.stdin.readline def BOJ11055() : N = int(input()) array = list(map(int, input().split())) memo = list(array) for index in range(1, len(array)) : max_point = 0 for j in range(index) : if array[j] < array[index] and max_point < memo[j] + array[index] : max_point = memo[j] + array[index] memo[index] = max(memo[index], max_point) print(max(memo)) BOJ11055() 접근 방법 0. 다이나믹 프로그래밍 .. 2022. 1. 2. LCS [백준 9251] - python def BOJ9251() : first = input() second = input() array = [[0] * (len(second) + 1) for _ in range(len(first) + 1)] for i in range(1, len(first) + 1) : for j in range(1, len(second) + 1) : if first[i-1] == second[j-1] : array[i][j] = array[i-1][j-1] + 1 else : array[i][j] = max(array[i-1][j], array[i][j-1]) print(array[len(first)][len(second)]) BOJ9251() 접근방법 : 1. 이차원 배열로 접근 2. 비교하는 문자열이 같다면 대각선에서.. 2022. 1. 1. 파도반 수열[백준 9461] - python import sys input = sys.stdin.readline def BOJ9461() : T = int(input()) dp = [0] * 102 dp[0] = 1 dp[1] = 1 dp[2] = 1 for i in range(3, 102) : dp[i] = dp[i-3] + dp[i-2] for _ in range(T) : n = int(input()) print(dp[n-1]) BOJ9461() 접근방법 1. 점화식만 찾아내면 문제는 끝난다.(dp 문제들의 핵심인것 같다) 2. 문제에서 다행히 예시를 잘 보여주어서 점화식 찾기가 어렵지 않았다. https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫.. 2021. 12. 31. 01타일 [백준 1904] - python 정답코드 import sys input = sys.stdin.readline def BOJ1904() : dp = [0] * 1000001 dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 5 n = int(input()) for i in range(5, n+1) : dp[i] = (dp[i-2] + dp[i-1]) % 15746 print(dp[n]) BOJ1904() 접근 방법 1. 점화식만 떠올리면 끝이다. 2. 나머지 연산을 까먹지 않고 적용하자! https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이.. 2021. 12. 30. 파이프 옮기기 1 [백준 17070] - python import sys input = sys.stdin.readline def BOJ17070() : N = int(input()) graph = [] for _ in range(N) : graph.append(list(map(int, input().split()))) answer = [[[0] * N for _ in range(N)] for _ in range(N)] answer[0][0][1] = 1 for x in range(0, N) : for y in range(2, N) : # 가로, 세로 if graph[x][y] == 0 : answer[0][x][y] = answer[0][x][y-1] + answer[2][x][y-1] answer[1][x][y] = answer[1][x-1][y] + a.. 2021. 12. 29. 가장 긴 증가하는 부분 수열 5[백준 14003] - python 접근 방법 : https://dkrnfls.tistory.com/114 가장 긴 증가하는 부분 수열 4 [백준 14002] - python import sys from bisect import bisect_left input = sys.stdin.readline def BOJ14002(): N = int(input()) A = list(map(int, input().split())) dist = [-1000000001] index = [0] * (N + 1) for i in range(l.. dkrnfls.tistory.com 이 문제에서의 접근방법과 같다!! 장애물 이였던 것 : 0. 값의 범위를 살펴보자 -10억 부터 10억 까지이다. 1. 거리 배열의 맨처음 초기값을 0으로 넣어주면 안된다. -10.. 2021. 12. 27. 이전 1 ··· 11 12 13 14 15 16 17 ··· 21 다음
