개발자 퉁이리

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 2차원 배열을 사용하여 문제를 풀었다. 각 문자의 길이만큼 배열을 만들어주고, 규칙성을 찾아내어 정보를 담아준다. i for문과 j for문을 사용해 두 문자열을 비교해주는데 일치하면 dp [i][j] = dp [i - 1][j - 1] + 문자 저장..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 누적 합 ⊙ 문제 접근 과정 2차원 dp 배열을 만들어주고 누적합을 저장해준다. 이 문제에서 누적합을 구할 때, 중복만 제거해주면 된다. + - - result +는 두 번 빼서 한번 더하는 곳이다. dp[i][j] = dp[i-1][j]+dp[i][j-1] - dp[i-1]..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 1칸 뒤를 선택하는 경우와 2칸 뒤를 선택하는 경우 2가지를 비교해주어 더 큰 값을 더해주는 점화식을 만들었다. ⊙ 문제 풀이 #include using namespace std; #define MAX 100001 int T, N; int sticker[2][MAX], dp[2][MAX]..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 이친수는 첫 번째 숫자가 1이고, 1이 연속해서 2번 오면 안 된다. dp[0] = 0, dp[1] = 1, dp[2] = 1이다. dp[1]은 하나, "0, 1" (첫번째 숫자 1 and 1이 연속해서 2번 안 옴) dp[2]도 하나, "00, 01, 11, 10" 그렇다면 dp[3]은..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 for문 2개를 사용하여 이중 list의 각각의 index를 만져줬다. 반복문 속의 조건문은 총 3가지로 나눴다. 가장 왼쪽에 있을 때, 가장 끝에 있을 때, 그리고 나머지. ⊙ 문제 풀이 N=int(input()) T=[] for _ in range(N): T.append(list(map(int,input().split()))) for i in range(1,N): f..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 ⊙ 문제 접근 과정 처음 접근할 땐, vector 두 개를 사용하고 sort에 또 다른 함수를 만들어서 정렬해주는 바람에 코드 길이가 길었지만 더 효율적으로 문제를 푸는 방법이 있었다. 아래에서 소개하겠다. max함수를 이용하면 문제를 쉽게 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 index 0 = red index 1 = green index 2 = blue 배열을 사용했다. 다 더하고 더한 N번째의 최솟값을 출력하였다. ⊙ 문제 풀이 #include using namespace std; int N; int result=0; int dp[1001][3]..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 규칙을 찾고 점화식을 세우자! N=1, 1개 N=2, 3개 N=3, 5개 N=4, 11개 N=5, 21개 점화식 = (N-2)*2 + (N-1) ⊙ 문제 풀이 arr= [0,1,3] for i in range(3,1001): arr.append(arr[i-2]*2+arr[i-1]) N=int(input()) print(arr[N..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 DP문제를 보면 점화식을 세울 생각이 먼저 든다. arr[N-1] + arr[N-2]일 때 두 가지로 나누어 푼다. ⊙ 문제 풀이 #include using namespace std; int N; int arr[1001]; int main() { cin >> N; arr[1] =1; arr[2] =2; for (auto..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 DP 문제다. 규칙성을 찾고 점화식을 세워 풀면 된다. ⊙ 문제 풀이 #include using namespace std; #define MAX 301 int N; int stairs[MAX]; int dp[MAX]; int main() { cin >> N; for(auto i=0;i> stairs[i]; dp..