[Gold V] 내려가기 - 2096문제 링크성능 요약메모리: 50928 KB, 시간: 324 ms분류다이나믹 프로그래밍, 슬라이딩 윈도우제출 일자2024년 12월 5일 04:15:08문제 설명N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는..

[Gold V] LCS - 9251문제 링크분류다이나믹 프로그래밍, 문자열문제 설명LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 및 코드풀이는 아래에 LCS 알고리즘과 함께 정리해두었습니다.[Computer Science/Algorithm] - 최장 공통 부분 수열 (LCS; Longest common subsequ..

최장 공통 부분 수열 (LCS; Longest common subsequence problem)부분 수열(subsequence)은 시퀀스의 원소를 순서를 유지한 채 몇 개를 골라낸 것을 말한다.최장 공통 부분 수열은 두 시퀀스(문자열 또는 배열)간 공통된 부분 수열 중 가장 긴 것을 찾아내는 문제이다. 예시) 문자열 `ABCBDAB`와 `BDCABA`의 LCS는 `BCBA`이다. 보통 LCS 문제를 해결하기 위해 주로 동적 계획법(DP;Dynamic Programming)을 사용한다.이 글에서도 DP를 이용한 LCS 알고리즘을 설명하고자 한다.  LCS 길이 구하기동작 원리동적 계획법은 문제를 작은 부분 문제로 나누고 그 해를 이용해서 전체 문제를 해결하는 방식이다.때문에 문제 정의와 점화식, 초기 조건..

[Silver I] 스티커 - 9465문제 링크성능 요약메모리: 147556 KB, 시간: 692 ms분류다이나믹 프로그래밍제출 일자2024년 11월 21일 23:00:48문제 설명상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b..

[Silver I] 정수 삼각형 - 1932문제 링크성능 요약메모리: 33988 KB, 시간: 404 ms분류다이나믹 프로그래밍제출 일자2024년 11월 21일 01:13:47문제 설명 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, ..