1. 문제 두 문자열 $X = x_{1}x_{2}x_{3}...x_{n}$와 $Y = y_{1}y_{2}y_{3}...y_{m}$이 주어진다. 여기서 $x_{i}$와 $y_{j}$는 하나의 문자를 나타낸다. 여기서 문자열의 부분문자열(Subsequence)은? "원래 문자열에서 순서를 유지한채로 문자 몇개를 제거한 문자열"로 정의한다. 예를 들어 'ABCBDAB'라고 한다면... ABC도 부분문자열이지만, ABBAB도 부분문자열이 된다. 가장 긴 공통 부분문자열(Longest Common Subsequence) 문제는 K개의 문자열이 주어질때, 모든 문자열의 공통 부분문자열 중에서 가장 긴 공통 부분문자열을 구하는 문제이다. K가 변수이면 다항시간내에 풀 수 없는 NP-hard문제임이 증명되어있다. 가장..
1. 문제 24463번: 미로 (acmicpc.net) 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 입구에서 출구로 가는데, 최단 경로가 아닌 경로는 모두 @로 바꿔서 표시하는 문제 2. DFS 풀이 최단 경로가 아닌 경로를 찾는게 그냥 찾을려하면 생각보다 까다롭다 아이디어의 핵심은 이동할 수 있는 모든 위치 .을 먼저 @로 바꿔놓는다 n,m = map(int,stdin.readline().split()) maze = [list(stdin.readline()...
1. 기본적인 $O(n^{2})$ 알고리즘 기본 알고리즘을 다시 한번 생각해보자. 수열 s를 처음부터 순회하면서, i번째 원소를 읽었을때, 0~i번째 원소까지 최장 증가 부분수열의 길이는... i보다 작은 인덱스 j에 대하여, dp배열의 0~j까지 모두 순회해서, j번째 숫자가 i번째 숫자보다 작다면, 그러한 j번째 숫자가 만드는 최장 증가 부분수열에 i번째 숫자를 포함시키면 된다 이렇게 찾은 최장증가부분수열의 길이들의 최댓값이 i번째 원소가 들어가는 최장 증가 부분수열의 길이였다 다익스트라 알고리즘에서 최단거리를 역추적하듯이 생각해보면 아주 심플하다 역추적을 위한 배열 p를 생각해서 현재 i번째 원소에 대한 dp값이 1이라면.. 최장 길이가 1이라는 뜻이니까 자기 자신이 최장 증가 수열의 시작점이니 p..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
