devbelly

문제 www.acmicpc.net/problem/3257 알고리즘 다이나믹 프로그래밍 풀이 문자열 A,B와 그들을 섞은 C가 주어졌을 때 C의 문자들이 A에 속한 문자인지 B에 속한 문자인지 찾는 문제입니다. 단 C에서 문자열 A와 B는 원래 문자열의 순서를 유지합니다. C에서 A와 B가 원래 순서를 유지하므로 C[1:]로 문제가 작아졌을 때 주어진 A,B 또한 A[1:],B 또는 A,B[1:]로 좁혀나갈 수 있습니다. 부분구조가 성립하므로 다이나믹 프로그래밍을 사용하도록 합시다. $cache[i][j]$ = A문자열을 $i$번째까지 해결하고 B문자열을 $j$번째까지 해결했을 때, 해야하는 선택 즉 $cache[i][j]$값에 1이 들어있다면 $cache[i-1][j]$에서 A를 선택한 것이고, 반대로 ..

문제 www.acmicpc.net/problem/15678 알고리즘 세그먼트 트리 + DP 풀이 $N$개의 발판이 주어지고 각 발판마다 점수가 있을 때, 얻을 수 있는 점수의 최댓값을 묻고 있습니다. 흔한 다이나믹프로그래밍 주제입니다. $dp[i]$를 $i$번째 발판까지 밟았을 때, 얻을 수 있는 최댓값이라고 하겠습니다. 각 i번째 발판마다 자신의 최댓값을 구하기 위해서는 $dp[i-D]$ ~ $dp[i-1]$ 사이의 최댓값을 얻으면 $dp[i]$를 구할 수 있습니다. 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간초과입니다. 눈에 띠는 것은 구간값 중 최대값을 요구하고 있습니다. 반복문을 통해 선형시간에 해결하는 것 말고도 세그먼트 트리를 활용하면 구간값을 $O(logN)$에 구할 수 있습니다. 입..

문제 www.acmicpc.net/problem/1219 알고리즘 벨만포드 풀이 벨만포드는 은근히 생각해야할 것이 있는 주제라고 생각됩니다. 최대로 벌 수 있는 돈을 구하는 문제입니다. 시작지점과 도착지점이 하나씩 있는 문제는 다익스트라 또는 벨만포드를 전략으로 고려할 수 있습니다. 음의 사이클이 존재할 때, 다익스트라를 사용하지 못하므로 벨만포드를 사용하도록 합시다. 벨만포드의 기본적인 아이디어는 루프를 $N$번 돌며 마지막반복에서 업데이트가 일어난다면 음의 사이클이 존재한다고 판단하는 것입니다. 물론 $N$번미만 루프안에서 업데이트가 더이상 일어나지 않는다면 종료함으로써 불필요한 루프를 도는 것을 그만할 수 도 있습니다. 유의해야할 것 중 첫번째는 $dist$ 배열의 타입입니다. 돈과 교통비의 최댓값..

문제 www.acmicpc.net/problem/1866 알고리즘 DP 풀이 헬리콥터는 본점에서 지점으로만 배송이 가능하고 트럭은 본점에서 지점 배송뿐만 아니라 지점에서 지점 사이의 배송이 가능할 때, 최소의 택배비용을 묻고 있습니다. 일단 택배들을 정렬합시다. 10위치의 택배가 2개 있고 30위치의 택배가 하나 있다면 거리 순서대로 처리하는 것이 최적이기 때문입니다. 그 후 $dp[i]$ 가 1번 택배물 부터 $i$번 택배까지 배송했을 때 드는 최소비용이라고 정의합시다. 아마 이전 지점까지의 택배를 모두 해결한 상태인 $dp[i-1]$ + 본점에서 $i$지점까지 트럭으로 배달하는 상태까지는 처리하셨을 겁니다. 문제는 헬리콥터가 $i$지점에 영향을 미치는 경우입니다. $i-1$지점의 택배를 처리할 때 헬..

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

문제 www.acmicpc.net/problem/1507 알고리즘 플로이드-와샬 풀이 도시를 잇는 최소한의 다리를 구할 때, 해당 다리들을 지나가는데 걸리는 시간의 총합을 묻는 문제였습니다. 문제에서 제시한 $N$제한이 작기 때문에(400 이하) 일일히 시도해보는 브루트포스를 사용할 수 있습니다. 그 중에서도 플로이드 와샬을 통해 구현하면 간단하게 구현이 가능합니다. 플로이드를 사용하는 중 $k$를 거쳐서 단축되는 도시가 존재한다면, 즉 모순이 발생한다면 -1을 출력하도록 합시다. #include #define rep(i,n) for(int i=0;i N; rep(i, N) rep(j, N) { cin >> dist[i][j]; sum += dist[i][j]; } rep(k, N) rep(i, N) r..

문제 www.acmicpc.net/problem/2517 알고리즘 세그먼트 트리, 좌표압축 풀이 현재 달리는 사람의 순서가 주어질 때, 자신의 최대등수를 출력하는 문제입니다. 자신보다 능력이 뛰어난 사람이 앞에 달리고 있으면 앞지를 수 없지만, 자신보다 능력이 낮은 사람이 앞에 달리고 있으면 앞지를 수도 있습니다. 쿼리는 달리는 순서대로 세그먼트트리를 업데이트 하며 그 순간 자신보다 앞에 있는 사람의 수를 묻고 있습니다. 누적합으로 자신앞에 있는 사람의 수를 알 수 있으므로 펜윅트리를 활용합시다. 유사한 문제가 많지만 그 문제들과 다른점은 주어지는 능력값이 굉장히 큰 수 라는 것입니다. 이는 좌표압축을 통해 해결가능합니다. 각 쿼리당 요구하는 시간복잡도는 $O(logN)$ 이므로 시간복잡도는 $O(Nlo..

문제 www.acmicpc.net/problem/1321 알고리즘 세그먼트트리 풀이 부대원의 숫자가 계속해서 바뀔 때, 몇번째 병사가 어디 부대에 들어있는지 묻는 문제입니다. 누적배열을 만들어 나이브하게 해결해봅시다. 부대원이 변경될때마다 누적배열을 변경하는데에 최대 $O(N)$의 복잡도를 요구하게됩니다. 업데이트를 더 빠르게 할 수 있는 세그먼트 트리를 요구합니다. 세그먼트 트리를 사용하면 업데이트와 쿼리가 $O(logN)$에 해결가능합니다. 남은 문제는 누적배열에서 몇번째에 해당하는$K$가 어디에 속한지 찾는 문제입니다. 누적배열은 오름차순의 형태를 띠고 있고 이는 이분탐색을 통해 접근할 수 있다는 의미입니다. 펜윅트리에서 쿼리는 누적합을 리턴하므로 펜윅트리 + 이분탐색을 통해 문제를 해결할 수 있습..