본문 바로가기

전체 글

 (90)
[백준/c++] BOJ 15988 - 1, 2, 3 더하기 3 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다. 해결 '1'을 만드는 방법 a. 1 '2'를 만드는 방법 a. 1 + 1 b. 2 '3'을 만드는 방법 a. 1 + 1+ 1 b. 1 + 2 c. 2 + 1 d. 3 '4'를 만드는 방법 a. 1 + 1 + 1 + 1 b. 1 + 2 + 1 c. 2 + 1 + 1 d. 3 + 1 e. 1 + 1 + 2 f. 2 + 2 g. 1 + 3 '4'를 만드는 방법..
[백준/c++] BOJ 1912 - 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 설명 n개의 정수로 이루어진 임의의 수열이 주어진다. 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구한다. 해결 dp[n] : n번까지의 연속합의 최대합 dp[1] = arr[1] dp[2] = arr[2] + dp[1] || arr[2[ ... dp[n] = dp[n - 1] + arr[n] || arr[n] => n - 1번까지의 최댓값 + n번값 or n번 값 중 큰 것 코드..
[백준/c++] BOJ 2193 - 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 설명 이진수 중 특별한 성질을 갖는 것들이 있는데, 이를 이친수라고 한다. 1. 이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. N (1 n; dp[1][0] = 0, dp[1][1] = 1; for (int i = 2; i
[백준/c++] BOJ 9465 - 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 설명 스티커 2n개를 그림 (a)와 같이 2행 n열로 배치한다. 스티커의 품질이 매우 좋지 않아서 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 각 스티커에 점수를 매기고, 점수의 합이 최대가 되도록 스티커를 떼어내려고 한다. 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 집합 점수의 최댓값을 구한다. ..
동적 프로그래밍 (dynamic programming) 동적 프로그래밍이란? 흔히 dp라고 불리는 이 알고리즘은, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다. 어떤 상황에 사용? dp를 사용하기 위해서는 아래 조건을 만족해야 한다. 1. 겹치는 부분 문제 (Overlapping Subproblems) : 동일한 작은 문제들이 반복하여 나타난다 2. 최적 부분 구조 (Optimal Substructure) : 부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있다 3. 단순한 부분 문제 (Simple Subproblems) : 부문제들이 j, k, l, m과 같은 몇 개의 변수로 정의될 수 있다 보통은 위의 1, 2번을 만족시킬 때 dp를 사용할 수 있다고 한다. 분할통치법과의 관계..
[백준/c++] BOJ 28280 - 귀납법 https://www.acmicpc.net/problem/28280 28280번: 귀납법 각 테스트케이스마다 한 줄에, $1$에서 시작해서 $2$배를 하거나 $1$을 빼는 행동을 최소 몇 번 반복해야 $k$를 만들 수 있는지 출력한다. 만약 $k$를 만들지 못한다면, 대신 Wrong proof!를 출력한다. www.acmicpc.net 문제 설명 1. n = k일 때 성립하면 n = 2k 일 때도 성립한다. 2. n = k > 1 일 때 성립하면 n = k - 1일 때도 성립한다. 양의 정수 k가 주어질 때, 정수 1에서 시작하여 현재 값을 2배 하거나 1을 뺀 값으로 바꾸는 행동을 몇 번 해야 k를 만들 수 있는지 계산한다. 테스트 케이스 개수 T (1 n; while (n--) { cin >> m; ..
[백준/c++] BOJ 14888 - 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 문제 설명 n개의 수로 이루어진 수열이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 n-1개의 연산자가 주어진다. (+, -, *, /) 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행한다. n개의 수와 n-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과..
[백준/c++] BOJ 1245 - 농장 관리 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제 설명 NxM 크기의 농장이 있다. 산봉우리가 몇 개 있는지 세려고 한다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. ("인접하다"의 정의는 X좌표 차이와 Y좌표 차이가가 모두 1 이하일 경우로 정의된다.) 격자 내에 산봉우리의 개수가 총 몇 개인지 구한다. N(1 < N = m; } void bfs(int i, in..

티스토리툴바