고양이 두 잔

문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자. 피보나치 수 재귀호출 의사 코드는 다음과 같다. fib(n) { if (n = 1 or n = 2) then return 1; # 코드1 else return (fib(n - 1) + fib(n - 2)); } 피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다. fibonacci(n) { f[1]

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 조금 헷갈리지만 일단은 동적 계획법 문제이다. 그걸 몰랐으면 순열로 모든 부분수열을 순회하려고 했을 것 같다. 문제를 보고 이게 뭘로 풀 때 더 효율적인 유형인가 판단하는 것도 능력일 듯. 어쨌거나 주어진 두 문자열에 대해서 각각 처음부터 끝까지 순회하며 ..

문제 두 전봇대 A와 B 사이에 하나둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄 을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로..

문제 수열 S가 어떤 수 Sk를 기준으로 S1 SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 동적계획법의 유명한 문제라고 알려진 가장 긴 증가하는 부분수열(LIS - Longest Increasing Subsequence) 문제이다. 예전에 한 번 풀었던 풀이를 보니 탑다운 방식으로 구성..

동적 계획법이란 미리 구해뒀던 답을 이용해 하나의 연산은 한 번만 하도록 하는 프로그래밍 패러다임이다. 지난 글에서 알아본 그리디 알고리즘이 그때그때 최적의 값을 찾아가는 방법이라면, 동적 계획법은 문제를 쪼개 모든 경우의 수를 살펴본 뒤 답을 구한다. 다만 연산 속도의 향상을 위해 이미 계산한 값을 저장해두는데, 이때 사용되는 메모리를 캐시(Cache)라고 한다. 동적 계획법이 적용될 수 있는 조건은 두 가지가 있는데, Overlapping Subproblem - 큰 문제를 중복되는 작은 문제로 나눌 수 있다. Optimal Substructure - 나눠진 작은 문제에서 구한 답을 이용해 전체 문제의 답을 구할 수 있다. 가 그것이다. 가장 쉬운 예로 피보나치수열을 들 수 있는데, 재귀 함수만을 이용..