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 방법은 다음과 같은 과정을 반복합니다. 이를 슈도코드는 다음과 같..

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 크기의 행렬 모양의 게..

문제 : 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/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/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..