OSNIM

LCS (Longest Common Subsequence)이란? 2개 이상의 문자열에서에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미합니다. LCS은 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나 무선 서명을 통해 휴대폰에서 사용자를 인증할 때 사용됩니다. LCS 예시 두 문자열 X, Y가 다음과 같이 주어질 때 LCS(X, Y)는 다음과 같습니다. X: ACAYKP, Y: CAPCAK LCS(X, Y) = 4 1. Top-down 방법 (재귀적 풀이) 문자열 X, Y가 X = [x1, x2, x3, x4, .... , xm], Y = [y1, y2, y3, .... , yn] 일 때, LCS의 Top-down 방법은 다음과 같은 과정을 반복합니다. 이를 슈도코드는 다음과 같..

문제: https://www.acmicpc.net/problem/11660 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, ..

문제: https://www.acmicpc.net/problem/11659 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 첫번째 제출 코드 (정답) import sys n, m = map(int, sys.stdin.readline().split()) arr = list(..

2022 KAKAO BLIND RECRUITMENT 6번 문제 : https://programmers.co.kr/learn/courses/30/lessons/92344?language=python3 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] N x M 크기의 행렬 모양의 게..

Level 4, DP 문제: https://programmers.co.kr/learn/courses/30/lessons/42897# 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 설명 접한 두 집을 털면 경보 처음과 마지막이 연결된 원형 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값 출력 제한사항 3

문제 : https://www.acmicpc.net/problem/2096 첫번째 제출 코드 (메모리 초과) import sys def solve(): MAX = 0 MIN = 0 for i in range(1, N): for j in range(3): if j == 0: dp[i][0] = arr[i][0] + max(dp[i-1][j], dp[i-1][j+1]) elif j == 1: dp[i][1] = arr[i][1] + max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) else: dp[i][2] = arr[i][2] + max(dp[i - 1][j], dp[i - 1][j - 1]) MAX = max(dp[-1]) for i in range(1, N): for j i..

DP, Level 3 문제 : https://programmers.co.kr/learn/courses/30/lessons/42898 문제 설명 물에 잠기지 않은 지역을 통해 등교 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1) 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n) 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수 m과 n이 모두 1인 경우는 없음 물에 잠긴 지역은 0개 이상 10개 이하 집과 학교가 물에 잠긴 경우는 없음 주의사항 웅덩이의 좌표는..

DP, Level 3 문제 : https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 첫번째 제출 코드(오답) def solution(N, number): answer = 0 dp = [9] * 32001 check = [N] dp[N] = 1 cnt = 1 while cnt

문제 : https://www.acmicpc.net/problem/2293 정답 코드 import sys def solve(): for coin in arr: for j in range(coin, K+1): dp[j] += dp[j-coin] print(dp[K]) return if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) arr = [int(input()) for i in range(N)] # dp[1]는 1개만 골랐을 때 경우의 수 # dp[0]은 하나의 동전만으로 k원 만드는 경우의 수를 의미 = 1 dp = [1] + [0]*K solve() 결과 및 정리 전형적인 DP 문제 메모리가 4MB라..

문제 : https://www.acmicpc.net/problem/2038 골룽 수열은 1이 1개, 2가 2개 있으니 2번, f(3) = 2 이므로 3이 2번 나타나는 단조 증가하는 수열입니다. 수열을 숫자로 풀면 다음과 같습니다. [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8..] 첫번째 제출 (시간초과) import sys def solve(dp): left = 1 right = 0 k = 3 while len(dp) < n: dp = dp + [k]*(dp[left]) left += 1 k = k+1 print(dp[n-1]) return if __name__=="__main__": n = int(sys.stdin.read..

문제 : https://www.acmicpc.net/problem/2225 import sys def solve(): arr = [[0] *(N+1) for i in range(K+1)] for i in range(1, K+1): for j in range(1, N+1): if j == 1: arr[i][j] = i elif i == 1: arr[i][j] = 1 else: arr[i][j] = arr[i-1][j] + arr[i][j-1] return arr[K][N] if __name__ == "__main__": input = sys.stdin.readline N, K = map(int, input().split()) print(solve()%1000000000) arr의 행은 K(정수의 개수)를 ..

문제 : https://www.acmicpc.net/problem/12865 정답 코드 import sys def knapsack(N, capacity): for i in range(1, N+1): W = weight[i-1] V = value[i-1] for j in range(1, capacity+1): if W > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(V+dp[i-1][j-W], dp[i-1][j]) return dp[N][capacity] if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) #행은 아이템의 개수 #열은 가방의 최대 무대 #dp[i][j] ..

문제 : https://www.acmicpc.net/problem/2011 제출 코드 def solve(): code = list(map(int, input())) dp = [0] * (len(code)+1) dp[0] = 1 dp[1] = 1 if code[0] == 0: print(0) return N = len(code) code = [0] + code for i in range(2, N+1): one = code[i] if one > 0: dp[i] += dp[i-1] two = code[i-1]*10 + code[i] if 10

문제 : https://www.acmicpc.net/problem/2133 풀이 N 일때 dp[N]의 위 그림 오른쪽처럼 3개로 나누어 집니다. 1. dp[N] = dp[N-2] x 3 2. dp[N] += i는 2부터 N-4 까지 dp 값에 2를 곱하고 모두 더한 부분 3. N이 2씩 증가할 때 마다 나타나는 새로운 타일 배열 : +2 제출 코드 def solve(): n = int(input()) dp = [0] * (30+1) dp[1] = 0 dp[2] = 3 for i in range(4, n+1): if i%2 == 1: continue dp[i] = dp[i-2]*3 for j in range(0, i-2, 2): dp[i] += dp[j]*2 dp[i] += 2 print(dp[n]) re..

문제 : https://www.acmicpc.net/problem/2579 첫번째 풀이 (재귀, 시간초과) start: 시작 인덱스, seq: 연속 2개 선택하는 것 판단 result: 현재까지 선택한 계단의 합 def dfs(start, seq, result): global ans if seq > 2: return if start > N: return if start == 5: ans = max(ans, result) return if start + 1 < N: dfs(start + 1, seq+1, result+a[start+1]) if start + 2 < N: dfs(start + 2, 1, result+a[start+2]) N = int(input()) a = [] ans = 0 for i in..

문제 출처: https://www.acmicpc.net/problem/11055 오답 정리 이 문제의 점화식과 규칙은 11053 문제의 유형과 너무 비슷했기 때문에 빠르게 찾을 수 있었다. 하지만 사소한 실수로 인해 시간을 너무 많이 뺏기고 문제를 풀지 못하는 불상사가 발생했습니다. 어디가 문제였는지 틀린 코드와 맞은 코드를 한눈에 비교하면서 분석해보도록 하겠습니다. 위 그림에서 차이점을 찾을 수 있나요? 저는 처음에 큰 문제가 없을 줄 알고 왼쪽처럼 코딩을 했습니다. 하지만 이렇게 코딩을 한 경우 예제는 커버가 되지만 모든 tast case를 만족 시킬수 없었습니다. 그럼 어디서 문제가 발생하였을까요? 다름 아니라 dp의 초기값에서 문제가 발생했습니다. 저는 DP문제를 풀 때 무의식적으로 dp = [0..

동적 프로그래밍, 동적 계획법 (Dynamic Programing) 다이나믹(Dynamic)의 유래 다이나믹 프로그래밍에서 다이나믹의 의미는 동적할당의 다이나믹과 다릅니다. 동적할당에서 다이나믹은 프로그램이 실행되는 도중에 메모리를 동적으로 할당하는 자료구조 기법으로 메모리 공간을 낭비하지 않기 위해 사용합니다. 하지만 다이나믹 프로그래밍에서 다이나믹의 의미는 크게 의미를 부여하지 않습니다. 다이나믹 프로그래밍을 먼저 만든 사람도 이름이 단지 멋있어서 다이나믹을 붙였다고 합니다. DP의 장점 다이나믹 프로그램이은 메모리 공간을 사용하여 연산속도를 높이는 장점이 있습니다. DP의 방식 2가지 탑-다운 (Top-Down) DP의 대표적인 문제인 피보나치 수열을 간단하게 탑 다운 방식으로 코드를 작성하면 다음..

문제 출처: https://www.acmicpc.net/problem/2156 접근 방법 각 잔의 순서를 a1 a2 a3 a4 a5 a6 ai (현재 i = 7) 이라고 하면, 포도주를 마시는 경우의 수는 다음 3개의 경우의 수만 존재합니다. 이를 점화식으로 나타내면 다음과 같습니다. n = int(input()) array = [0]*(n+1) dp = [0]*(n+3) for i in range(1, n+1): array[i] = int(input()) dp[1] = array[1] MAX = 0 for i in range(1, n+1): dp[i] = max(dp[i-1], dp[i-2]+array[i], array[i-1]+ array[i] + dp[i-3]) print(dp[n]) 문제점, 시간..