SY DevLog

1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제의 예제로 각 연주마다 가능한 볼륨을 표현하면 다음과 같다. 연주가 반복될 때마다 위의 그래프처럼 가지가 증가하므로 뒤로 갈수록 계산해야 하는 양이 많아진다. N의 범위가 최대 100이므로, N번째에는 2의 100승에 가까운 경우의 수를 검사해야 한다. -> 메모리 초과 혹은 시간 초과 다른 방법을 생각하다가 M+1크기의 배열을 생성하고, 다음과 같이 의미를 부여했다. int[] arr = new int[M+1]; arr..

1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 풀었다. 좌우대칭인 한 결과는 동일한 것으로 간주해야 한다는 점에서 처음에 점화식을 세우기 어려웠다. 만약 좌우대칭을 신경쓰지 않는다면 점화식을 다음과 같이 세울 수 있다. dp[n] = dp[n-1] + dp[n-2] * 2 타일의 가로 길이가 n일 때의 가능한 경우의 수는 ① 타일의 가로 길이가 n-1일 때에서 2x1짜리 타일을 하나 추가한 경우 -> dp[n-1] ② 타일의 기로 길이가 n-2일 때에서 2x2짜리 ..

1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 동적 계획법을 통한 최장 공통 수열을 구하는 문제이다. 보통은 두 문자열의 LCS를 구하는데, 이 문제는 세 개의 문자열의 LCS를 구해야 한다. 아래는 LCS(Lowest Common Subsequence)를 구하는 방법에 대한 글이다. lotuslee.tistory.com/39?category=964787 LCS(Longest Common Subsequence) LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장..

동적 계획법(Dynamic Programming) 동적 프로그래밍, 다이나믹 프로그래밍 이라고도 한다. 동적 계획법이란 하나의 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이다. 동적 계획법에서 가장 중요한 개념은 메모이제이션(Memoization)과 점화식이다. 메모이제이션(Memoization) : 동일한 계산이 반복될 때, 이전에 계산한 결과를 메모리에 저장하여 동일한 계산을 반복하는 것을 피하는 방법이다. 이전에 계산한 결과를 메모리에 저장하기 때문에 중복된 계산을 할 필요가 없으므로 속도가 빠르다는 장점이 있다. 그리고 동적 계획법에서는 이 메모이제이션을 위해 점화식을 세우는 과정이 필요하다. 동적 프로그래밍하면 가장 대표적인 예시가 바로 피보나치 수열이다. 피보나치 수열은 앞의 두 항의..

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리에서 다이나믹 프로그래밍을 이용하여 푸는 문제다. dfs방식으로 루트노드에서부터 리프노드까지 top - down 으로 내려간 후, 다시 리프노드에서부터 위로 올라가면서 dp배열을 업데이트한다. dp배열은 이차원 배열로 생성하여서 n번 마을이 우수 마을인 경우와 그렇지 않은 경우로 나누었다. dp[n][0] : n번 마을이 우수 마을이 아닐 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합 dp[n][1] : n번 마을이 우수 ..

LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장 긴 부분문자열"을 찾는 알고리즘 여기서 subsequence는 꼭 연속하지 않아도 되는 부분문자열이다. * 문자열에서 substring 과 subsequence의 차이 * 문자열 A가 있을 때, - substring : 문자열 A의 연속하는 부분 문자열 - subsequence : 문자열 A에서 연속하지 않은 부분 문자열(연속해도 되고, 연속하지 않아도 됨) 즉, 다시 한번 짚고 넘어가면 LCS 알고리즘은 두 개의 문자열에서 subsequence를 찾는 알고리즘이다. LCS 알고리즘은 DP(Dynamic Programming : 다이나믹 프로그래밍)을 이용한다. LCS 알고리즘은 예제를 보면서..