복습 정리 노트

백준 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)임을 알..

최근 최소 스패닝 트리 (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에 충분히 들어간다. 그 다음 코드의 작동 시간을 줄여야 하..

백준 BOJ 4353번 : Beavergnaw 문제 난이도 : Silver IV 알고리즘 분류 : 기하학 지름이 D인 원통형 나무의 위아래 높이 차가 D인 부분을 파서 지름이 d이고 높이가 d인 원통형 나무를 남길 때, 파먹은 부분의 부피를 구하는 문제이다. (구체적인 형태는 위의 그림을 참고하자.) 문제의 조건에 따라 식을 정리하면 위와 같이 된다. 원뿔대의 부피는 1/3 pi H (r^2 + rR + R^R)인데 이것은 큰 원뿔의 부피에서 작은 원뿔의 부피를 (높이는 비례식으로 계산) 계산하여 얻을 수 있는 공식이다. 나머지는 관계식을 구해서 d를 구하면 되는데, 나의 경우에는 식을 풀기 귀찮아서 이분 탐색으로 해결했다. #include #define int long long using namespa..

백준 BOJ 16488번: 피카츄가 낸 어려운 문제 문제 난이도 : Silver V 알고리즘 분류 : 기하학 AB = AC인 이등변삼각형 ABC에 대해 BC에 K개의 점 P_i를 잡고 함수 F(i)를 (선분 AP_i의 길이)^2 + (선분 BP_i의 길이) × (선분 CP_i의 길이)로 정의할 때, F(1)+F(2)+···+F(K)의 값을 구하는 문제이다. 굳이 증명을 하지 않아도 삼각형을 어떻게 잡아도 조건만 만족하면 같은 답이 나온다는 사실을 유추할 수 있으므로, 가장 구하기 쉬운 상황 하나를 만들어 그려보면 된다. 예를 들어 위와 같이 직각이등변삼각형을 잡고 P를 한 점으로 고정시켜 생각해보면 답은 N^2 K임을 알 수 있다. #include #define int long long using nam..