devbelly

문제 www.acmicpc.net/problem/9520 알고리즘 DP 풀이 $k$번째 도시를 방문할 때, 그보다 낮은 번호의 도시들은 이전에 다 방문하거나 그 이후에 방문해야 합니다. 모든 도시를 방문할 때 필요한 최소거리를 묻고 있습니다. 1번 도시부터 방문한다고 해봅시다. 순차적으로 2번도시를 처리하게 된다면 다음과 같은 행동을 통해 위 조건을 만족할 수 있습니다. 1. 1번 도시의 오른쪽에 2번도시를 배치한다 2. 1번도시의 왼쪽에 2번 도시를 배치한다. 위 행동 다음 3번 도시를 배치할 때 또한 지금까지 배치한 도시들의 맨 왼쪽, 또는 맨 오른쪽에 도시를 배치한다면 낮은 번호의 도시를 이후에 방문하거나 이전에 방문하는 것을 처리할 수 있습니다. 즉 부분 문제가 성립하므로 다이나믹 프로그래밍으로 ..

문제 https://www.acmicpc.net/problem/2300 알고리즘 동적 계획법 풀이 기지국들을 하나의 통신 범위로 묶을 때, $x$ 좌표를 정렬한 후 묶어야 함을 알 수 있습니다. 건물$i$와 건물$j$를 하나의 통신 범위 안에 넣을 때, 사용하는 길이는 두 건물의 $x$좌표 차와 그사이에 있는 빌딩들의 $y$좌표*2 중 최댓값이 되어야 합니다. $cache[i]$= 현재 건물 $i$부터 세워나갈 때, 필요로 하는 최소 길이 $solve()$ 함수는 최대 $N$번 호출되고 함수 내부에서 $for$은 최대 $N$번 반복하므로 시간 복잡도는 $O(N^2)$입니다. 코드 #include #define rep(i,n) for(int i=0;i> x >> y; vt.emplace_back(x, ab..

문제 https://www.acmicpc.net/problem/10710 알고리즘 동적 계획법 풀이 날씨가 궂으면 쉬고, 좋으면 현재 도시에서 다음 도시로 가는 그리디한 해는 금방 반례가 나오게 됩니다. 현재 날씨가 좋지 않더라도 나중에 거리가 짧은 도시 사이를 좋은 날씨로 가게 되는 케이스가 있다면 걸리기 때문입니다. 즉 모든 상황을 고려할 수 있는 동적 계획법으로 해결하도록 합시다. $cache[i][j]$= $i$날에 $j$ 도시에 위치할 때, 얻게 되는 최소 피로도 ++ $cache$ 값을 갱신할 때, 우리가 필요로 하는 정보는 직전 날에 대한 정보뿐 입니다. 2일 전, 3일 전 정보가 필요가 없습니다. 슬라이딩 윈도우를 통하여 $cache[2][1000]$로 메모리를 최적화할 수 있습니다. 코드..

문제 https://www.acmicpc.net/problem/1796 알고리즘 Dynamic programming 해설 $cache[i][j]$ = $i$번째 알파벳부터 해결해야 하고, 현재$idx$위치가 $j$ 일 때 필요한 최소 이동 횟수 현재 커서 위치에서 다음 단계의 알파벳으로 가기 위해선 현재 해결해야하는 알파벳의 $lo$ 위치와 $hi$ 위치를 들러야 합니다. 두 위치를 들른다면, 그 사이에 있는 현재 단계의 알파벳은 모두 해결 가능함을 알 수 있습니다. $dist(a,b,c,d)$= 현재 위치 $a$에서 $c$와 $d$를 들른 후 $b$까지 가기 위해 필요한 커서 거리 $dist$함수를 통해 현재 단계에서 필요한 최소 커서 이동거리를 구할 수 있고, 다음 단계로 나아가 문자$z$까지 처리를..

문제 https://www.acmicpc.net/problem/1787 알고리즘 KMP, 동적 계획법 풀이 추정할 수 있는 문자열의 길이가 가장 길기 위해선 일치하는 prefix와 suffix가 가장 짧아야 함을 알 수 있습니다. 우리가 실패함수를 만들게 되면 일치하는 prefix와 suffix가 가장 긴 길이가 담겨 있게 됩니다. 문제에서 요구하는 것과는 정반대입니다. prefix와 suffix가 일치하는 길이가 1 이상인 가장 짧은 길이를 얻는 것은 동적 계획법을 통해 해결 가능합니다. $cache[i]$ = 문자열의 길이가 $i+1$ 일 때, 동일한 prefix와 suffix의 길이중 0을 제외한 가장 짧은 값 현재 문자열의 길이를 $k$라 할 때, 일치하는 가장 긴 길이는 $fail[k-1]$ 이..

문제 https://www.acmicpc.net/problem/2401 알고리즘 KMP, 동적 계획법 풀이 직관적인, 나이브한 방법으로 생각을 해봅시다. 짧은 문자열들을 긴 문자열의 각 위치마다 일일이 매칭을 시도해보는 방법을 떠올릴 수 있습니다. 긴 문자열 $L$에서 짧은 문자열$I$이 시작할 수 있는 위치를 찾는데 한 개가 아닌 $N$개의 문자열에 대해서 해야 합니다. 우리는 이 방법을 최적화할 수 있는 방법을 알고 있습니다. 긴 문자열에서 짧은 문자열을 찾는 알고리즘. 즉 KMP입니다. 매칭은 빠르게 했으니 일일이 시도하는 문제는 동적 계획법을 통하여 풀 수 있습니다. 시간 복잡도는 $O(N(L+I)+NL)$입니다. 매칭한 결과를 저장할 수 있는 효율적인 방법을 생각해보도록 합시다. 처음에 저는 벡..