꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1965사실상 최대 증가부분 수열의 길이 구하기 문제였습니다.예전에도 LIS 문제를 풀어봤기 때문에 쉽게 구현할 수 있었습니다. /* 정육면체 모양의 상자들이 일렬로 늘어서 있다. 상자들마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가(1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자들을 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7..

문제 링크입니다: https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 앞서 http://jaimemin.tistory.com/324?category=987849에서 작성한 코드에서 자료형을 int에서 long long으로 변환하고 조건에 맞게 변환하여 문제를 푸는데 성공했습니다.

문제 링크입니다: https://www.acmicpc.net/problem/11722http://jaimemin.tistory.com/317와 비슷한 문제였습니다. /* 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. */ #include #include using namespace std; const int MAX = 1000; int N; //수열의 길이 int cache[MAX + 1], arr[MAX]; //arr[start]에서 시작하는 감소 부분 수열 중 최대 길이 반환 int LDS(int start) //Least Decreasing Sequence { int &result = cache[start + 1]; if (result != -1) return..

문제 링크입니다: https://www.acmicpc.net/problem/11055LIS(Largest Increasing Sequence) 문제와 비슷하지만 증가 부분 수열의 최대 길이가 아닌 최대합인 점에서 달랐습니다. /* 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. */ #include #include #include //memset using namespace std; const int MAX = 1000; int N; int arr[MAX]; int cache[MAX]; int maxSum(void) { int result = 0; for (int i = 0; i < N; i++) { cache[i] = arr[i]; //i번째..

문제 링크입니다: https://www.acmicpc.net/problem/11048동 서 남 북을 고려하지 않고 동, 남, 남동 방향만 고려하면 됬기 때문에 쉽게 풀 수 있던 문제였습니다./* 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은(1, 1)이고, 가장 오른쪽 아랫 방은(N, M)이다. 준규는 현재(1, 1)에 있고, (N, M)으로 이동하려고 한다.준규가(r, c)에 있으면, (r + 1, c), (r, c + 1), (r + 1, c + 1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.또, 미로 밖으로 나갈 수는 없다. 준규가(N, M)으로 이동할 때, ..

문제 링크입니다: https://www.acmicpc.net/problem/2747백준 알고리즘 사이트 단계별로 풀어보기 항목을 보다가 '피보나치 수' 문제집 옆에 도전 중이라고 쓰여있는 것을 보고 완료하고 싶어서 풀어봤습니다. #include using namespace std; int N; int fibonacci(void) { switch (N) { case 0: //0번째 return 0; case 1: //1번째 return 1; default: //그 이후 int first = 0; int second = 1; int sum; //합 for (int i = 0; i < N - 1; i++) { sum = first + second; first = second; second = sum; } re..

문제 링크입니다: https://www.acmicpc.net/problem/11057슬슬 동적계획법에 대해 감을 잡아가는 것 같습니다! #include #include //memset using namespace std; const int MOD = 10007; int N; int cache[10][1001]; //시작하는 숫자(0~9), N N; if (N 1000) exit(-1); cout

문제 링크입니다: https://www.acmicpc.net/problem/2167요구사항이 살짝 모호했던 문제였습니다. 처음에는 (i, j)~(x, y)까지의 배열의 합을 전부 구하는 문제인 줄 알았습니다.여기서 진짜 요구하는 답은 행번호 i 이상 x 이하 그리고 열번호 j 이상 y 이하인 인덱스의 합이였습니다.완전탐색법과 다이나믹 프로그래밍의 실행속도 차이가 명확하게 드러나는 문제였습니다. /* 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. */ //완전 탐색법 /* #include #include //memset using namespace std; const int MAX = 300 + 1; int arr[MAX][..

문제 링크입니다: https://www.acmicpc.net/problem/9465동적계획법이라고는 했지만 거의 완전탐색법으로 푼 문제였습니다.(그 결과 실행속도...)핵심은 전 대각선과 전전 대각선만 비교하면 된다는 것이였습니다. /* 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림(a)와 같이 2행 n열로 배치되어 있다.상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이..

문제 링크입니다: https://www.acmicpc.net/problem/2163사실 메모이제이션으로 풀지 않고 간단한 곱셈을 통해 풀 수 있는 문제였습니다.하지만 문제를 푸는 과정이 중요하기 때문에 다이나믹 프로그래밍으로도 풀어봤습니다. /* 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초..