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, ..

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/14501 나의 접근법 상담 일정 전체를 탐색하는 반복문 안에 일정이 가능한지 확인하며 일정과 T를 확인하며 N+1이 넘어갈 때까지 while로 체크하며 해결하려고 했습니다. 하지만 이렇게 할 경우 예제1 은 1일 -> 4일 -> 5일은 찾지만 예제 4의 1일 -> 6일 -> 7일은 찾았지만 1일 -> 6일 -> 8일의 경우는 못 찾았습니다. 이 문제점을 찾았더니 DFS와 백트래킹이 생각나서 바로 구현 방식을 틀고 다음과 같이 작성하였습니다. 첫번째 코드 def dfs(startDate, period, pay): global ans # 상담하면 퇴사날이 넘어 가는 경우 for i in range(startDate+period, N+1)..

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

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