11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 예제 9 ans : 55 문제를 처음 봤을 때 바로 dp로 풀어야겠다 생각한 건 아니고 완전 탐색으로 셀 수 있나 생각을 해 봤다. 타일을 완전 탐색으로 채우는 것 자체가 힘들어 보여서 일단 손으로 보드를 채워보면서 문제를 파악했다. 딱 정확히 이 사진의 흐름대로 2*3에서도 2*2와 2*1을 이용해서 채운 느낌이 들었고 2*4 블록을 채울 때 확신이 생겼다. 2*k 블럭을 예로 들자면, 세로로 긴 블록을 하나 먼저 세우면 나머지 k-1열 2*k-1 블록을 채우는 방법과 정확히 똑같다..

LCS(최장 공통부분 수열) 알고리즘은 두 개의 문자열에서 가장 긴 공통부분 수열을 찾는 알고리즘이다. 예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK로 길이는 4이다. LCS 알고리즘은 동적 프로그래밍으로 효율적으로 구현할 수 있다. dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 LCS 값이다. 알고리즘의 동작 단계는 다음과 같다. 1. 초기 조건 설정 각 문자열 앞에 0을 두어서 초기 조건을 설정한다. 이런 식으로 초기 조건을 설정하는 이유는 효율성이나 안정성 같은 측면에서는 영향이 없지만, 가독성과 코드 이해에 도움이 된다. dp [0][j] = 0, dp [i][0] = 0으로 설정한다. 초기 조건을 설정함으로써 다음에 나올 점화식을 초기 조건 ..