본문 바로가기

반응형

알고리즘

[분할 정복] L-트로미노(L-Tromino) 타일링 1. 트로미노란? 트로미노(Tromino)란, n=3인 폴리오미노(polyomino)로, 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형이다. 따라서 다음과 같이 두 개의 트로미노가 존재할 수 있다. 2. $2^n$ x $2^n$ L-트로미노 타일링 이제, 이 트로미노중에서 일자형이 아닌 L 모양의 트로미노를 한 변의 길이가 $2^n$인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 $2^n$인 정사각형을 항상 채울 수 있다. 증명은 다음과 같이 수학적 귀납법으로 가능하다. [정리] $2^n$ X $2^n$ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-트로미노로 모두 채울 수 있다. [증명] 1. n = 1일 때 n = 1인 ..
비트마스크 (BitMask) 알고리즘 [목차] 1. 비트마스크(BitMask)란? 2. 비트마스크의 장점 3. 비트 연산자 4. 비트마스크를 이용한 집합 구현 * 종만북에 잘 설명되어 있어 기본적으로 종만북의 설명을 따릅니다. 1. 비트마스크(BitMask)란? - 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. - 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. - 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말한다. 2. 비트마스크의 장점 비트마스크는 크게 어려운 개념이 아니며, 이 개념을 알고 있다면 매우 유용한 경우가 꽤나 있다. 비트마스크의 장점들은 다음과 같다. 1. ..
최소 / 최대 맨해튼 거리 (Manhattan Distance) 1. 맨해튼 거리(Manhattan Distance)란? 우리가 일상생활에서, 또는 일반적으로 사용하는 거리는 '유클리드 거리'이다. 편의상 2차원 평면 (x축, y축)이라고 하자. 두 점 $ (x1, y1) $, $ (x2, y2) $ 사이의 거리를 구한다고 할 때, 우리가 일반적으로 이용해왔던 $\sqrt{(x1 - x2)^2 + (y1-y2)^2}$ 로 구하는 거리가 유클리드 거리이다. 반면, 맨해튼 거리(Manhattan Distance)는 각 좌표의 차를 모두 더한 것을 거리로 한다. 즉, $ \left | x1 - x2 \right | + \left | y1 - y2 \right | $ 가 두 점 $ (x1, y1) $, $ (x2, y2) $ 사이의 맨해튼 거리이다. 일상생활에서는 잘 이용되..
완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘 1. 완전 탐색이란? 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. '무식하게 푼다'라는 의미인 Brute-Force (브루트 포스)라고도 부른다. 이름이 거창하게 지어져 있지만 사실 완전 탐색 자체로는 알고리즘이라고 부르긴 그렇고, 문제 푸는'방법'이라고 이해하면 편할 것 같다. 알고리즘을 모르는 사람이 프로그래밍 문제를 푼다면, 당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아낼 것이고 이 과정 자체가 완전 탐색이다. 대신에 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법이다. 예를 한번 들어보자. "10개의 정수 원소로 이루어진 수열이 있다. 이 수열에서 두 원소를 선택해서 구한 합의 최댓값을 구하시오. " 이..
소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법 어떠한 자연수 N이 소수인지를 판별하는 방법은 여러 가지 방법이 있다. 그중에서 너무 난도 높은 것은 제외하고 충분히 PS에서 쓸만한 방법을 알아보자. 우선, N이 소수인지를 판별하는 경우와 N이하의 소수가 몇개있는지, N이하의 소수를 모두 구하는 경우 두가지로 보통 나뉜다. 1. N을 2부터 N-1까지 모두 나누기 소수는 1또는 자기 자신으로만 나누어지기 때문에 위의 방법으로 N이 나누어 떨어지지 않는다면 N은 소수라고 할 수 있다. 만약, N이 어떤 두 수로 나누어진다고 한다면, N = p*q의 형태가 되고, p와 q 둘 중 하나는 반드시 $ \sqrt{N} $의 값 이하일 것이다. 따라서 N-1까지 나눌 필요는 없고, $ \sqrt{N} $까지만 나눠도 소수인지 판별이 가능하다. 물론, 이 방법을 ..
LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 주어진 수열에서 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다. (당연히 어려운 문제로는 NlogN을 요구하는 문제가 나온다...) [개념] LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다. 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다. 예를 들어 위와 같은 길이가 8인 수열이..
Knuth's Optimization Knuth's Optimization은 Dynamic Programming의 점화식이 아래와 같은 특정 조건을 만족하는 경우 사용할 수 있는 "최적화" 기법이다. i) DP 점화식 형태 $ dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] $ $ (i\le k
볼록 껍질 (Convex Hull) 볼록 껍질 (Convex Hull) 볼록 껍질이란? "2차원 평면 상에서 주어진 점들을 모두 포함하는 가장 작은 다각형" (이 때, 다각형의 각 변들은 주어진 점을 양 끝점으로 갖는다) 기하 알고리즘에서 볼록 껍질이 자주 응용되기 때문에 중요한 알고리즘이다. 볼록 껍질을 구하는 데에는 '그라함 스캔 알고리즘(Graham's Scan Algorithm)'이 이용된다. 볼록 껍질 (Convex Hull) 구하는 과정은 다음과 같다. 1. 주어진 점들 중 y좌표가 가장 작거나 혹은 y좌표가 가장 작은 점이 둘 이상이라면 x좌표가 가장 작은 점을 선택 2. 선택한 점을 기준으로 나머지 점들을 반시계 방향으로 정렬 (각을 이용) 3. 그라함 스캔 알고리즘..