본문 바로가기

알고리즘22

[BOJ] 백준 11726번: 2xn 타일링, 타일링 문제 www.acmicpc.net/submit/11726/21279055 로그인 www.acmicpc.net 타일링 문제는 동적 계획법을 접하면 입문 문제로 간단한 점화식으로 풀리는 문제입니다. 타일은 1x2 크기와 이것을 회전한 2x1 타일이 있으며, 길이 n이 주어질 때 2 x n 직사각형을 채울 수 있는 경우의 수를 찾아야 합니다. 아래는 n이 각각 1, 2, 3 인 경우를 보여줍니다. 각 경우에서 보면 빨간 블록은 이전 단계들의 블록 모양이며 파란색은 현재 단계에 새로 추가된 블록입니다. 여기까지만 보면 점화식을 d[i] = d[i-1] + d[i-2]로 유추해볼 수 있습니다. 좀더 정확하게 알아보기 위해 n이 4인 경우를 보면 n이 2인 경우 + n이 3인 경우의 합이 됩니다. 점화식은 피보나치 형태.. 2020. 9. 7.
[BOJ] 백준 9012번: 괄호 www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 '(' 와 ')' 가 주어졌을 때 ( )는 올바른 문자열이며 올바른 문자열 S에 대하여 ( S ) 도 올바른 문자열이고, 올바른 문자열 T와 ST를 이루는 것도 올바른 문자열일 때, 주어진 괄호 문자열이 올바른 문자열인지 판별하는 문제입니다. 문자열을 탐색하는 중 현재 문자가 ( 라면, 이 후 가장 먼저오는 )와 짝을 이뤄야합니다. Last in First out 의 특징을 .. 2020. 9. 7.
[BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱) 먼저 우리는 빠른 거듭 제곱 알고리즘을 알고있습니다. pow(a,y), 즉 a^y 를 구할때 만약 y가 홀수면 a * a^y/2*a^y/2로 분해하여 짝수 거듭 제곱의 반을 구해가면서 O(lgY)의 복잡도로 구할 수 있습니다. int pow(int a, int y) { int x = 1; while (y) { if (y & 1) { x *= a; } a *= a; y /= 2; } return x; } math.h 헤더의 내장 pow를 사용하지 않고 직접 구현하여 쓰는 이유는, 몇몇 문제에서 특정 수로 나눈 나머지 값을 요구하기 때문입니다. 이유는 답이 너무 커지거나 하는 경우에, 보통 1,000,000,007 (1e9+7)와 같은 소수로 나눈 나머지 값을 요구합니다. 소수는 어떠한 수와도 나누어 떨어지.. 2020. 8. 17.
오일러 𝜑(피 또는 파이) 함수, 서로소 개수 구하기 서로소란 1 을 제외하고 공약수가 없는 두 수의 관계입니다. 오일러 피함수 φ(n)은 n이하의 자연수 중 n과 서로소인 자연수의 개수를 의미하는 함수입니다. 예를 들어 φ(6)은 2로 1과 5의 서로소가 있음을 의미합니다. 모든 자연수는 소수들의 (prime) 곱으로 표현 할 수 있습니다. 예를들어 16은 2^4 로 표현할 수 있고 15는 3^1 * 5^1 로 나타낼 수 있습니다. φ(16)은 2, 4, 6, 8, 10, 12, 14, 16을 제외한 나머지 자연수와 서로소입니다. 여기서 알 수 있는 사실은, 자연수를 구성하는 소수들의 배수는 전부 서로소가 아닙니다. 즉, φ(16) = 16 - (16/2) = 8개로 구할 수 있습니다. ( n 이하의 k의 배수의 개수는 n/k로 구할 수 있습니다, 나머지.. 2020. 8. 13.

티스토리툴바