4354-문자열 제곱 정말 오랫동안 고민하다가 생각이 안 나서 결국 풀이를 흘깃 쳐다본 문제이다. 정답은 허탈하리만큼 간단했다. 그냥 실패함수를 구한 다음에, 특정한 공식에 대입만 하면 그게 답이다. 그 공식이라는 것도 복잡하지 않다. 이렇게 생겼다. len은 문자열의 길이이고 fail[len-1]은 마지막 글자의 실패함수 값이다. 위의 분수 값이 정수여야만(분자가 분모로 나누어 떨어져야만) 정답으로 유효하고, 그렇지 않다면 답은 1이다. 다만 아직은 직감적으로 와닿지는 않는다. 이런 문제일수록 처음에 풀었을 때 이해를 제대로 하고 넘어가야지 다음에 비슷한 유형의 문제를 만났을 때 풀 수 있다. 현재까지 분석한 지점은 은 ptn의 길이를 의미한다(답으로서 유효한 경우에만). 이 문제는 ptn이 총 몇 번..
2624-동전 바꿔주기 동전1,2 문제보다 더 까다롭다고 생각하는 문제이다. 이 문제는 동전 1처럼 목표 금액을 만들 수 있는 경우의 수를 구하는 문제인데 차이점은 동전의 개수가 제한되어 있다는 점이다(동전1 문제는 동전의 개수가 무한대라고 가정했다). 따라서 동전1의 문제에서 살짝 꼬아서 낸 문제라고 생각하면 된다. dp테이블의 의미는 동전1과 동일하지만, 1차원이 아닌 2차원 배열이 필요하다. 그 이유는 곧 설명한다.dp[a][b]=c : a번째 동전까지 봤을 때, b원을 만들 수 있는 경우의 수=c가지아래의 코드에서 반복문의 변수 j가 바로 동전의 개수가 제한되어 있기 때문에 (동전1의 코드와 비교해서)새롭게 추가된 for loop이다. j는 최대 cnt[i]만큼 증가한다. 2차원 dp가 필요한 이..
12865-평범한 배낭 전형적인 Knapsack문제이다. 각 물품마다 무게와 가중치가 주어지고 정해진 무게 안에서 가중치의 합이 최대가 되도록 만들면 된다. dp테이블의 의미는 dp[a][b]=c : a번째 물품까지 봤을 때, b이하의 무게로 만들 수 있는 최대 가중치의 합=c 이다. 물품은 모두 1개씩 밖에 존재하지 않기 때문에 2차원 dp로 디자인 해야 하는 것 같다. 문제의 디스크립션은 조금 다르지만 동전시리즈 문제랑 비슷한 느낌이다. 현재 i번재 물품까지 보고 있을 때, 현재 무게(b)로 최대의 가중치를 구하기 위해서는 기존의 (i-1)번째 까지의 물품으로 만들 수 있는 가중치의 합과 이번에 i번째 물품을 이용해서 새롭게 만들어 낼 수 있는 가중치의 합 중에서 큰 값을 dp배열에 저장하면 된다. ..
2294-동전2 역시 동전 문제이다. 동전1 문제는 a원을 만들수 있는 모든 경우의 수가 관심사였다면, 이번 문제는 최소 개수를 묻고 있다. 동전 금액과 목표 금액이 있고 동전 개수는 무한대라는 가정까지는 동전1과 같으나, 이번에는 목표 금액을 만드는 동전의 최소 개수를 묻는 문제이다. 따라서 dp테이블의 의미가 달라지는데 바로 'dp[a]=b : a원을 만들기 위해 필요한 동전의 최소 개수 b개'이다. 이러면 문제의 정답은 dp[k]가 된다.테스트케이스의 입력처럼 1,5,12원의 동전으로 총 15원을 만들 수 있는 최소 동전 개수를 알아보자. 단순하게 생각해보면 1원*15개 , 5원*3개 , 12원*1+1원*3개 ....가 있을텐데 정답은 5원*3개가 정답이다. 그럼 왜 이게 정답인지 역추적을 해보자...
2293-동전1 동전 시리즈 문제가 여러 종류가 있는데 이 문제는 동전의 개수가 무한하다는 전제 하에 목표 금액을 만들 수 있는 경우의 수를 묻는 문제이다. 테스트케이스에 나와있는 1,2,5원 3종류의 동전으로 목표 금액 10원을 만들어보자. dp테이블은 'dp[a]=b : a원을 만들 수 있는 경우의 수 b가지' 라고 정의하자. 그러므로 최종 정답은 dp[k]가 될 것이다. 초기 상태는 dp[0]=1로 두자. 0원을 만들기 위해서는 아무 동전을 사용하지 않는 경우를 1가지라고 생각하면 된다. 그 다음 현재 coin[i]원의 종류로 j원을 만들려고 한다면 그 경우의 수는 어떻게 계산해야 할까. 일단 이전 상태인 (i-1)번째까지 구했던 경우의 수에다가 이번에(i)번째를 통해서 새롭게 만들 수 있는 경우의..
2098-외판원 순회 비트마스크DP를 이용한 대표적인 문제이다. 먼저 비트마스크의 원리에 대해서 간단히 설명하자면 숫자를 통해서 메모이제이션 한다는 것이다. 이게 가능한 이유는 컴퓨터에서 정수는 0과 1의 이진수 형태로 저장되기 때문이다. 만약 메모이제이션의 수단으로 배열을 사용하게 된다면 call by reference 방식이므로 함수가 연속해서 호출되는 dfs방식에는 적절하지 않다. 반면에 int자료형은 call by value 방식이므로 함수가 여러번 호출되어도 안정성이 보장된다. 단 비트마스크를 항상 사용할 수 있는 것은 아니고 int형을 사용한다면 int는 32개의 비트로 이루어져 있으므로 n이 그보다 작아야 한다. 일반적으로 '1'은 방문함, 0'은 방문하지 않음으로 통용된다. 비트마스크에서 ..
ㄴ1102-발전소 외판원 순회 문제와 비슷한 유형인데, 차이점이라면 외판원 순회 문제는 반드시 모든 노드를 방문해야 했었다면 이 문제는 방문할 필요가 없는 노드(이미 가동되어 있는 발전소)가 존재하고, 또 p값이 n보다 작을 수 있다. 이 말은 곧 모든 노드를 방문할 필요가 없다는 뜻이다. 외판원 순회 문제의 dfs함수 구조와 dp배열이 다르다. 그 이유는 모두 '현재 위치가 어디인지 상관 없기'때문이다. 외판원 순회 문제의 경우에는 현재 자신이 어느 노드에 위치해있느냐에 따라서 갈 수 있는 지점이 달라지는 반면에, 이 문제는 가동되어 있는(visited에서 1인)노드라면 어디든지 도달 가능하기 때문이다. 따라서 굳이 현재 위치를 기록할 필요가 없고 그에 따라 dfs함수와 dp배열에도 현재위치를 기록하는..
ACM 예선에서 트리에서의 두 정점간의 최단거리를 구하는 방법을 몰라서 충격받고 바로 그 방법인 LCA를 공부했다. 공부하고보니 그렇게 어려운 알고리즘도 아니어서 더욱 아까웠다.LCA 알고리즘은 말 그대로 트리에서 두 정점간의 가장 깊은(루트에서 먼) 부모 노드를 찾아내는 알고리즘이다. 그 부모 노드를 찾으면 거리 또한 자연스럽게 알아낼 수 있다. 일단 naive하게 두 노드가 서로 만날 때까지 위로 한칸 한칸씩만 올라가면, 트리가 일직선으로 쭉 뻗어있는 모형에서 시간이 O(N)이 소요된다(트리의 노드의 개수가 N개). 따라서 11438-LCA2 같이 노드가 10만개, query가 10만개가 들어올 경우 시간이 터지게 된다. 따라서 O(N)보다 더 빠르게 찾아내야 하는데 실제로 O(logN)만에 가능하다..