For Programmer

설명을 잘해놓은 블로그가 있어서 해당 블로그의 주소를 남겨놓겠다. https://grini25.tistory.com/110 [BOJ] #13023 _ ABCDE [ABCDE] https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 처음에는 문제를 이해하기 어려웠다. 문제를 해석하면.. grini25.tistory.com import sys input = sys.stdin.readline N, M = map(int, input().split()) relationship = [[] for _ in range(N)] visited = [False] * N res..

*개인적으로 연속합 1 문제에서 코드가 한줄 추가되는 거지만 생각하기가 굉장히 까다로웠다. 우선 dp를 2중 리스트로 선언하여 2가지 dp를 비교를 하면서 큰 값을 찾는 문제이다. 우선 dp를 다음과 같이 초기화 해야한다. dp : 연속합을 구하기 위한 누적합 - dp[0][i] : 특정 원소를 제거하지 않은 경우 - dp[1][i] : 특정 원소를 제거한 경우 N이 1보다 클 경우 dp를 찾으면 되는데 1. 특정 원소를 제거하지 않은 경우 dp[0][i] = max(dp[0][i - 1] + input_array[i], dp[i]) : 아무런 원소를 제거하지 않고 일반적인 연속합으로 구하는 경우이다. 2. 특정 원소를 제거하는 경우 dp[1][i] = max(dp[0][i - 1], dp[1][i - ..

사실 이 문제는 앞선 가장 긴 증가하는 혹은 감소하는 부분수열문제에서 약간 꼬아낸 문제이다. 우선 이 문제를 해결하기 위해서는 2가지를 생각할 수 있어야 한다. 1. 입력받은 수열의 각 원소마다 '앞에서' 몇번째로 증가하는 부분 수열 인지 확인(이전의 가장 긴 부분수열을 구하는 알고리즘과 동일) 2. 입력받은 수열의 각 원소마다 '뒤에서' 몇번째로 증가하는 부분 수열인지 확인(입력받은 수열을 거꾸로 뒤집고 구해도 됨) -> 예를 들어 위 예제 입력에서 1 5 2 1 4 3 4 5 2 1 이있다고 치자. 그렇다면 1 2 3 4 5 는 증가하는 수열이며 5 2 1 은 감소하는 수열이다. 즉 8번째 '5' 를 기준으로 앞에서는 5번째 증가 부분수열이며 뒤에서 3번째로 증가하는 부분 수열이다. 총 배열 길이는 ..

import sys input = sys.stdin.readline N = int(input()) input_array = list(map(int, input().split())) dp = [x for x in input_array] for i in range(N): for j in range(i): if input_array[i] > input_array[j]: dp[i] = max(dp[i], dp[j] + input_array[i]) print(max(dp)) -> 간단히 리스트를 모두 돌면서 각 원소보다 앞에 있는 작은 숫자들만 계속해서 더해가면서 그 합을 dp에 저장해나가면 된다. 그 후 가장 큰값을 출력하면 된다.

import sys input = sys.stdin.readline n = int(input()) input_array = [0] for _ in range(n): input_array.append(list(map(int, input().split()))) for i in range(2, n + 1): for j in range(len(input_array[i])): if j == 0: # 인덱스가 0일 때는 -1의 인덱스가 없기 때문에 비교할 필요 없다. input_array[i][j] = input_array[i][j] + input_array[i - 1][j] elif j == len(input_array[i]) - 1: # 인덱스가 마지막일 때도 비교할 필요 없다. input_array[i][j]..

(사실 해당 문제가 30분 내에 DP라는 것도 생각하기 힘든데 점화식까지 구할려고 하니 머리가 터지는 줄 알았다... 답을 볼 수 밖에 없었지만 생각보다 이해하기는 어렵지 않았다.) 6잔의 포도주가 있다.( 6, 10, 13, 9, 8, 1) 이 있는데 점화식을 구할때는 바로바로 dp[0] 부터 생각을 해보는 것이 좋다. dp[0] 은 당연히 0이고 dp[1] 일때 최댓값은 와인이 1개 밖에 없으므로 wine[1] 이 될것이다.(wine 인덱스가 1부터 시작한다고 생각) dp[2] = wine[1]+wine[2] 까지는 불변이다.(wine의 양이 음수일 수 없으므로) 그럼 여기서 우리는 dp[3] 부터는 식으로 찾아야한다는 말이 된다. 어떻게 생각할 수 있을까? 우선 dp[3] 즉, 와인이 3개있을 때 ..

이 문제는 10844번 - 쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 의 문제와 굉장히 유사하다. dp[ N 자리의 수 ][ N 자리 숫자에서 맨 앞에 오는 수 ] 라고 생각해보자. dp[1][0] ~ dp[1][9] = 1 이다. N이 2부터는 다음과 같은 식이 성립한다. dp[2][0] = dp[1][0] + dp[1][1] ... dp[1][9] 이다. dp[2][1] = dp[1][1] + dp[1][2] ... dp[1][9] 이다. dp[2][2] = dp[1][2] + ... dp[1][9] 이다. 즉 앞자리에 0이 올때는 뒷자리에 0~9이 모두 올 수 있기 때문에 0~9가 오는경우의 수를 모..

이 문제의 풀이방식은 2가지가 있다. 우선 첫번째는 무식하게 N이 0일때부터 구해보는 것이다. 문제에서 하나도 배치하지 않는 경우도 1이라고 했기에 DP[0] =1 그 이후 타일을 그려보면서 구했다. DP[1] = 3, DP[2]=7, DP[3] = 17 .. 여기서 규칙하나를 발견했다. DP[i] = DP[i-2] + DP[i-1] * 2 이다. 꽤나 쉽게 구해서 이렇게 쉽게 풀 문제가 아닌데 라고 생각하면서 정답을 봤더니 역시나 조건을 분기하여 경우의 수로 구하는 것이었다. DP = [[0 , 0 , 0] ,....] 와 같이 DP에 2중리스트로 우선 저장한다. 그 이유는 DP[i][0] 값에는 이전 타일의 왼쪽에 사자들이 있는 경우 DP[i][1] 은 이전 타일의 오른쪽에 사자들이 있는 경우 DP[..