개발자 퉁이리

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/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..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 슬라이딩 윈도우 ⊙ 문제 접근 과정 그렇게 어렵지는 않은 문제다. 공간 복잡도를 조금만 신경 쓴다면. 메모리 제한이 4MB이기에 공간을 잘 사용해야 한다. 변수를 여러 개 설정해주고 매번 갱신해 공간을 절약하는 방법을 선택했다. 아래 예시를 통해 접근 과정을 알아보자. 3 1 2 3 4 5 6 7 8 9 N=3, 3줄을 입력받는다. 첫 번째 줄은..

www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 다이나믹 프로그래밍 ⊙ 문제 접근 과정 어머나, 문제에 정답이 적혀있다. F(n) = F(n-1) + F(n-2) // (n>=2) 코드로 그대로 옮기자 ⊙ 문제 풀이 #include using namespace std; int def(int n) { if (n==0) { return 0; } else if..

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 처음에는 간단하게 문제에 접근하여 코드를 구현해봤다. 하지만 결과는 실패!! 단순 구현 문제가 아니라 다이나믹 프로그래밍 알고리즘으로 풀어야했다! 아래에 있는 힌트를 보니 단순 구현의 경우 10일 때 예외가 존재했다. 아래는 첫 번째로 푼 단순 구현 코드이다. X = int(input()) count = 0 while(X!=1): if(X%3==0): X=X/3 elif(X%2==0): X=X/2 else: X=X-1 coun..