본문 바로가기

ㄴ 알고리즘/백준BOJ풀이27

[백준 11727번] 2×n 타일링 2 풀이 문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 입력 채워야 하는 직사각형의 가로 길이 N 출력 2*N 직사각형을 1x2, 2x1, 2x2 타일로 채울 수 있는 방법의 수 풀이 방법 DP[N] = 2*N 직사각형을 채울 수 있는 방법의 수로 놓고, 이를 작은 문제들로 나누어 동적 프로그래밍으로 풀이한다. 2*N 직사각형을 만드는(채우는) 방법은 3가지가 있다. 1) 2*(N-1) 직사각형의 오른쪽에 2*1 크기의 타일을 한개 놓는 것 2) 2*(N-2) 직사각형의 오른쪽에 1*2 크기의 타일을 두개 놓는 것 3) 2*(N-2) 직사각형.. 2021. 11. 18.
[백준 2410번] 2의 멱수의 합 풀이 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 입력으로 주어진 N을 2의 멱수(2^k) 의 조합으로 몇개나 나타낼 수 있는지 구하는 문제이다. 이는 다이나믹 프로그래밍 기법으로 해결할 수 있다. 수를 하나씩 늘려 가능한 2^k 조합을 구해보면, 다음과 같다. N=1 -> 1 N=2 -> 1+1, 2 N=3 -> 1+1+1, 2+1 N=4 -> 1+1+1+1, 2+1+1, 2+2, 4 N=5 -> 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1 ... N이 홀수일 경우를 살펴보면, N-1의 가능한 조합 끝에 1씩을 더해주어 완성된다. N=3 인 경우, N=2 일 때의 조합 (1+.. 2021. 10. 20.
[백준 2251번] 물통 풀이 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 담을 수 있는 부피가 각각 A, B, C 인 물통 3개가 있다. 초기에는 마지막 물통만 가득 차 있으며, 나머지 물통은 비어있다. 한 물통이 가득 차거나 빌 때까지 물을 옮기고, 이를 반복할 수 있다. 처음 물통에 들어있는 양이 0 일 때, 마지막 물통에 들어있을 수 있는 물의 양을 모두 구해야 한다. 가장 쉬운 방법은, 각 물통에 담길 수 있는 물의 양에 대해 모든 경우의 수를 탐색하고, 첫번째 물통이 비었다면 마지막 물통의 양을 저장하는 .. 2021. 10. 18.
[백준 1992번] 쿼드트리 풀이 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 한 변의 길이가 N(N은 2의 배수)이고 0과 1로 이루어진 정사각형이 주어졌을 때, 이를 압축하여 표현하는 문제이다. 압축하는 규칙을 정리해보면 다음과 같다. 1) 모든 요소가 0인 정사각형은 0을 출력한다. 2) 모든 요소가 1인 정사각형은 1을 출력한다. 3) 1과 0이 섞여있는 정사각형은 4등분 하여 ( 왼쪽 위 정사각형 값, 오른쪽 위 정사각형 값, 왼쪽 아래 정사각형 값, 오른쪽 아래 정사각형 값)을 출력한다. 문제에서 제시한 예시에 대해.. 2021. 10. 15.
[백준 1790번] 수 이어 쓰기 2 풀이 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 1 부터 N까지의 수를 이어붙였을 때, K번쨰 자리에 있는 문자를 출력하는 문제이다. 먼저, K번째 자리에 있는 문자를 찾기 위하여 1번 부터 몇번까지의 수를 이어붙여야 하는지 찾아보자. 수의 특성에 따라, 1 ~ 9 까지의 수는 1자리 수들이고 9 * 10^0 = 9 개 이며, 9*10^0 * 1(문자의 자리수) = 9 개의 문자를 표현한다. 10 ~ 99 까지의 수는 2자리 수들이고 9 * 10^1 = 90 개 이며, 9*10^1 * 2(문자의 자리수) = 180 개의 문자를 표현한다. 1.. 2021. 10. 13.
[백준 1629번] 곱셈 풀이 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net A^B % C 를 구하는 문제이다. A와 B의 최댓값이 2147483647 이므로, 직접 A^B를 구해 C로 나누면 오버플로우가 발생하게 된다. 따라서 다음 두가지 사실과 분할 정복 방법을 이용하여 문제를 해결해보고자 한다. 1. A^B는 B가 짝수인지 홀수인지에 따라 A^(2/B)의 곱으로 나타낼 수 있다. 예를 들어, B = 10 일 때, A^10 = A^5 * A^5 이다. B = 9 일 때, A^9 = A^4 * A^4 * A 이다. 즉, B%2 == 0 (B가 짝수) 일 때, A^B = A^(2/B) * A^(2/B).. 2021. 10. 12.
[백준 1149번] RGB 거리 풀이 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집 N개를 각각 빨강(r), 초록(g), 파랑(b)으로 칠할 때의 비용이 주어진다. i번째 집은 i-1 번째 집과 다른 색으로 칠해져야 한다. N개의 집에 대하여 칠할 수 있는 모든 조합을 탐색하면, //R로 시작하는 경우 R / G / \ / B R ... \ R \ / B \ G 경우의 수가 2의 거듭제곱으로 늘어 시간 복잡도는 3 * 2^(N-1) 이 된다. 해당 방법은 시간 초과가 예상되므로, 다이내믹 프로그래밍(dp) 점화식을 세워.. 2021. 10. 11.
[백준 16139번] 인간-컴퓨터 상호작용 풀이 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문자열 S가 주어졌을 때, l 부터 r까지의 인덱스 중 알파벳 a의 개수를 출력하는 문제이다. a, l, r 이 q번 주어질 때마다 문자열을 일일이 탐색하여 해결할 수도 있겠지만 시간 초과가 발생할 것으로 예상된다. 해당 문제는 구간합 개념으로 쉽게 해결할 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 //idx s e u n g j a e h w a n g //s[idx] 0 1 1 1 1 1 1.. 2021. 10. 7.
[백준 14465번] 소가 길을 건너간 이유 5 풀이 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net N개의 신호등 중 B개가 고장 나 있을 때, 연속으로 K개가 존재하도록 고쳐야 하는 최소 신호등의 개수를 출력하는 문제이다. N = 10, B = 5, K = 6 일 때, 최소로 고쳐야 하는 신호등의 개수를 구하기 위해 1개를 고치는 경우부터 B개를 고치는 경우까지 모두 확인할 수도 있다. 그러나 이 방법은 높은 시간 복잡도를 가진다. 슬라이딩 윈도우 기법을 이용하여 연산 과정을 줄여보자. 슬라이딩 윈도우 기법은 연속된 영역에서 특정 값을 계산하여 비교할 때 사용한다. 슬라이딩 + 윈도우 = 미끄러지는 창문이라는 뜻으.. 2021. 10. 5.
[백준 10819번] 차이를 최대로 풀이 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 배열의 크기 N과 요소들이 주어졌을 때, 배열의 순서를 적절히 바꾸어 sum = |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 의 최댓값을 구하는 문제이다. 재귀 함수를 통해 배열의 순서를 정하고, sum의 최댓값을 구하는 방법이 있다. 먼저 원소의 개수 N과 배열 A를 초기화시키자. scanf("%d", &N); memset(A, 0, sizeof(A)); for (int i=0; i 2021. 10. 4.

티스토리툴바