복습 정리 노트

백준 BOJ 17272번 : 리그 오브 레전설 (Large) 문제 난이도 : Gold I 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 N초를 길이가 1초인 스킬과 길이가 M초인 스킬로 구성하는 방법의 수를 구하는 문제이다. dp[N] = dp[N-1] + dp[N-M]이라는 점화식을 세울 수 있다. 그러나 Large 문제에서는 N이 10^18 이하이므로 dp로는 풀이가 불가능하다. 따라서 점화식을 행렬로 구성하여 행렬의 거듭제곱으로 답을 구해주어야 한다. 위와 같이 점화식을 만들 수 있다. 참고로 M이 100 이하이므로, 행렬의 크기는 아무리 커도 100 x 100을 넘어가지 않는다. 위의 A 행렬을 N 제곱 해주면, 곱해지는 행렬은 a_0, a_-1, ...으로 구성되는데, 정의에 의해 a_0 = 1..

백준 BOJ 12987번 : Matrix Again 문제 난이도 : Gold II 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 주어진 행렬 A에 대해, S = A + A^2 + ... + A^K를 구하는 문제이다. 단일 행렬에 대한 거듭제곱은 N^2 log K 시간에 구할 수 있으나, 식 S의 경우에는 그러한 방식을 쓰더라도 결국 각 항을 따로 구하면 시간 복잡도가 늘어난다. 따라서 이 문제에서는 점화식을 사용하여 분할 정복으로 문제를 풀어주어야 되는데, 점화식은 다음과 같다. 위와 같이 점화식을 세우면 K를 계속해서 2로 나눠가면서 log 시간 복잡도로 식의 값을 구할 수 있다. 이 때 ( i ) 케이스의 A^(K/2)는 분할 정복을 이용한 거듭제곱 알고리즘을 사용하여 log(K) 시간에 구해준다. ..

백준 BOJ 12878번 : Blocks 문제 난이도 : Gold III 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 N개의 블럭을 각각 빨강, 주황, 노랑, 초록색 중 하나로 칠하는데 그들 중 빨간색으로 칠해진 블럭과 노란색으로 칠해진 블럭이 각각 짝수개인 경우의 수를 구하는 문제이다. 가장 간단한 해결책은 N = 5 정도까지 완전 탐색으로 모든 경우를 count 해본 뒤, 규칙을 찾아 일반항을 찾는 방법이 있다. 직접 계산하는 방법은 위와 같다. 빨간색 또는 노란색으로 칠할 블럭을 선택하고, 그들 중 빨간색으로 칠할 블럭을 고른다. 나머지 블럭 중에서는 초록색 또는 주황색 중 어떤 색으로 칠할지를 고른다. 이 문제의 식 유도에서 핵심은 NC0 + NC2 + NC4 + ... = 2^(N-1)임을 알..

백준 BOJ 1185번 : 유럽여행 문제 난이도 : Platinum IV 알고리즘 분류 : 최소 스패닝 트리 (MST) 트리 형태의 그래프가 주어지고, 한 지점에서 시작하여 어떤 노드와 간선을 지나갈 때의 비용이 모두 주어질 때, 최소 비용으로 모든 노드를 순회할 때 드는 최소 비용을 구하는 문제이다. 경로를 생각해보면, 시작점을 제외하고 어떤 경로든 지나갔다가 다시 돌아와야 하므로, 간선의 시작점 → 간선 → 간선의 끝 점 → 간선 순서로 반드시 지나가게 된다. 따라서 간선의 비용 자체를 (간선의 시작점의 비용 + 간선의 끝 점의 비용 + 간선의 비용 x 2)로 설정해주고, 여기에 시작점으로 설정할 최소 비용인 노드의 비용을 더해주면 된다. #include #define int long long usi..

최근 최소 스패닝 트리 (MST) 문제들을 풀이하고 있는데, 문제 풀이 방식이 다들 상당히 비슷해서 모든 문제들의 풀이를 적는 것은 비효율적으로 보인다. (크루스칼이나 프림 알고리즘으로 모두 풀린다) 그들 중 별도의 아이디어가 필요한 문제들만 몇 개 풀이를 적어보려고 한다. 백준 BOJ 22570번 : Save your cats 문제 난이도 : Gold IV 알고리즘 분류 : 최소 스패닝 트리 (MST) 마녀가 울타리로 고양이를 가두었다고 하며, 각 폐쇄된 공간에는 고양이가 갇혀있다. 울타리를 부수는 비용은 울타리의 길이에 해당할 때, 최소 비용으로 고양이를 모두 구하는 비용을 구하는 문제이다. 울타리들을 그래프의 간선이라고 생각해보자. 사이클이 존재하지 않으면 모든 고양이가 구출될 수 있으므로, 결국 ..

백준 BOJ 15683번 : 감시 문제 난이도 : Gold IV 알고리즘 분류 : 구현, 브루트포스 1~5인 5종류의 감시 카메라가 있고 각 카메라는 네 방향 중 하나로 설치할 수 있으며, 6은 벽이라고 할 때 감시 카메라가 감시할 수 없는 블럭의 최소 수를 구하는 문제이다. 감시 카메라의 최대 개수가 8개 이하이므로, 8개의 감시 카메라를 모두 4방향에 대해 검사해도 4^8의 경우의 수밖에 나오지 않는다. 따라서 브루트포스로 모든 감시 카메라로 가능한 모든 방향의 배치를 돌려주면 된다. 나의 경우에는 8자리 이하의 4진수를 사용하여 각 자리수가 카메라의 방향이 되도록 구현하였다. #include #define int long long using namespace std; int N, M; struct ..

백준 BOJ 12100번 : 2048 (Easy) 문제 난이도 : Gold II 알고리즘 분류 : 구현 게임 2048을 구현하여, N x N 격자의 보드가 주어질 때 최대 5번 이동시켜서 얻을 수 있는 최대 숫자의 크기를 구하는 문제이다. (코딩하다가 심심해서 잠깐 해봤다.) 내가 꽤 오래 미루던 구현 문제이다. 구현 문제는 심지어 풀이를 참고해도 내가 다시 짜려면 한참 걸린다. 아무튼 이 문제는 구조 자체는 단순 DFS 방식으로 짤 수 있는데, 문제는 네 방향으로 숫자가 이동하는 것을 구현하기가 귀찮다. 구현 방법은 이러한데, 예를 들어 모든 숫자를 밑으로 이동시켰을 때 밑에서 1번째 칸에서 맨 밑으로 검사, 밑에서 2번째 칸에서 맨 밑까지 검사, 밑에서 3번째 칸에서 맨 밑까지 검사, ...의 방식으..

오늘은 DP 태그에서 내가 안 푼 문제 중 푼 사람 수가 많은 문제들을 풀 것이다. DP나 그리디는 같은 골드 난이도 문제들 중에서도 새로운 아이디어를 떠올려야 하는 경우가 많아서 일정 시간 내에 풀이가 떠오르지 않는다면 풀이를 참고하여 푸는 문제가 꽤 있을 수도 있다. 백준 BOJ 2011번 : 암호코드 문제 난이도 : Gold V 알고리즘 분류 : DP 이 문제는 다른 풀이도 확인해보았으나 설명이 부족한 글이 많아서 내가 신경써서 정리했으므로 맨 위에 배치한다. (!!) 숫자로만 이루어진 문자열을 각 숫자가 알파벳 번호라고 생각하고 해독할 때 해독할 수 있는 서로 다른 알파벳 문자열의 수를 구하는 문제이다. (예를 들면 25는 B와 E로 해석할 수도 있지만 25번째 알파벳 Y로 해석할 수도 있다.) ..

8월 5일부터 8월 8일까지 약 53문제 정도를 풀었는데, 문제가 너무 많아서 밀린 풀이를 적을 엄두가 안 난다. 그래서 이 때 풀이한 문제들은 일단 보류해두기로 했다. 그리고 코드포스 Div.2 라운드를 하나 참가했는데, 지금 실력만 유지한다면 조만간 퍼플에 갈 수 있을 것 같다. 시간이 남는다면 해당 라운드의 A~E까지 풀이 정리를 한 번 해보려고 한다. 아무튼 여기서는 오늘(8월 9일) 풀이한 백준 풀이를 다룬다. 백준 BOJ 11085번 : 군사 이동 문제 난이도 : Gold III 알고리즘 분류 : 분리 집합 두 도시(노드) 사이의 경로 중 가장 너비가 작은 간선의 너비가 최대가 되도록 할 때 가장 작은 너비를 구하는 문제이다. 태그가 분리 집합으로 되어 있어서 처음에는 어떻게 유니온 파인드로 ..

백준 BOJ 11690번 : LCM (1, 2, ..., n) 문제 난이도 : Gold III 알고리즘 분류 : (빠른) 에라토스테네스의 체 1부터 N까지의 자연수들의 최소공배수를 구하는 문제이다. 핵심 아이디어는 N 이하의 자연수 중 특정 소인수의 거듭제곱을 가장 많이 포함하고 있는 수가 LCM의 약수가 된다. 예를 들어 N = 10이면 LCM은 2의 거듭제곱을 약수로 가질텐데, 10 이하의 자연수 중 8이 2^3으로 2를 가장 많이 가지고 있으므로, LCM(1, ..., 10)은 2^3을 약수로 가져야 한다. 그러면 이제 10^8 이하의 소수를 구하면 되는데, 먼저 메모리의 경우 bool 벡터로 메모리를 할당할 경우 10^8칸까지는 256MB에 충분히 들어간다. 그 다음 코드의 작동 시간을 줄여야 하..