답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/16288 풀이 : K개 이하의 서로다른 증가수열을 구성할 수 있는지를 묻는 문제입니다. K개 만큼의 수열을 구성하고 K개의 순열 중 현재 값보다 작으면서 최대의 값을 현재 값으로 바꾸면서 수열을 구성하면 됩니다. 수열의 갯수가 K개를 넘어가는 순간 NO를 출력하고 수열의 갯수가 K개 이하가 되면 YES를 출력합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include int n, k, arr[100], karr[100], max, idx; int main() { scanf("%d %d", &n, &k);..

문제 출처 : https://www.acmicpc.net/problem/2343 풀이 : 이분 탐색 문제입니다. 블루레이의 길이를 기준으로 이분탐색을 돌아 가능한 모든 경우의수를 다 시도해봅니다. 이분 탐색을 돌 때 left와 right를 기준으로 도는데, 1. Mid 값이 문제조건을 만족 할 때, (즉, Mid값을 블루레이의 길이로 잡고 M을 채울때 M개 안에 다 채워 질 때) - binary( left , Mid - 1 ) 2. Mid 값이 문제 조건을 만족 시키지 못 할 때, - binary( Mid + 1, right ) 위와 같이 탐색하시면 됩니다. O(n) * O(logn) 으로 총 O(nlogn)의 시간복잡도를 가집니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

문제 출처 : https://www.acmicpc.net/problem/5430 풀이 : 큐 문제입니다. 이 문제는 배열을 자주 뒤집어야 하는데 말 그대로 뒤집기만 하면 타임오버가 납니다. front 와 rear의 위치만 바꿔 주어 O(1)로 뒤집은 듯한 효과를 내시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include struct reverse_queue { int data[100001]; int front, r..

문제 출처 : https://www.acmicpc.net/problem/11055 풀이 : DP문제 입니다. 가장 큰 값을 가지는 LIS가 아니라 가장 큰 값을 가지는 증가 부분 수열 이라는 점에 주의합시다. 값을 쌓아 가실 때 이전까지 증가 수열 중 현재 값과 증가 수열을 이루면서 가장 큰 값을 갖는 증가수열이 되도록 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include int n,arr[1000],cache[1000],max; int main() { scanf("%d", &n); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/16500 풀이 : DP문제입니다. 문자열을 처음부터 끝까지 훑으면서 단어들과 매칭합니다 그리고 단어 목록들로 문자열의 현재 시점까지 완성 시킬 수 있는지 없는지 여부를 word배열에 쌓아가는데, 쌓을 때 현재 검사하고있는 S문자열의 바로 앞 문자까지 완성되있는지 여부를 확인하고 완성되어 있으면 word 배열에 완성 됬다고 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include char comp[101]; char carr[101][101]; int n,word[101]; int main() { scanf("%s", comp)..

문제출저 : https://www.acmicpc.net/problem/11052 풀이 : DP문제입니다. 동전문제와 거의 일치합니다. 메모이 제이션을 할 때 현재 cache에 쌓여있는 값과 이 팩을 샀을때의 값을 비교하여 쌓아가면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n,card[1001],cache[1001]; int main() { scanf("%d", &n); for (int i = 1; i

문제 출저 : https://www.acmicpc.net/problem/11727 풀이 : DP문제 입니다. 1x2 타일, 2x1타일, 2x2타일을 이용해 타일링을 합니다 2x1타일은 2x2타일로 만들어서 사용해야 하므로 2x2와 같은 경우에 들어가도록 계산하되, 다른 경우로 여겨주시면 됩니다. N=1일때 1 N=2일때 3 N>=3일때 N-1패턴에서 1x2타일을 붙이는 경우, N-2패턴에서 2x1타일 2개, 2x2타일 1개를 붙이는 경우를 더하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n, cache[1001]; int main() { scanf("%d", &n); cache[1] = 1; cache[2] = 3; for (int i = 3; i

문제 출저 : https://www.acmicpc.net/problem/1904 풀이: DP문제입니다. N=1 일때 1 N=2 일때 1,00 N>=3 일때 [N] = [N - 2] + [N - 1]입니다. N>=3일때 점화식이 저렇게 나오는 이유는 N일때의 타일패턴은 N-1 에서 1타일을 추가한 것, N-2에서 00타일을 추가한 것 뿐이기 때문입니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n, cache[1000001]; int main() { scanf("%d", &n); cache[1] = 1; cache[2] = 2; for (int i = 3; i

문제 출저 : https://www.acmicpc.net/problem/11726 풀이 : DP 문제 입니다. 1X2 타일과 2X1 타일로 2XN을 타일링 할 때 아래의 규칙대로 쌓으면 됩니다. 규칙 1) 1X2 타일을 2 X (i - 1) 타일링 한 것에 덧붙인다. 규칙 2) 2X1 타일을 2X2 타일로 만들어 2 X (i - 2) 타일링 한 것에 덧붙인다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n, cache[1001]; int main() { scanf("%d", &n); cache[1] = 1; cache[2] = 2; for (int i = 3; i

문제 출저 : https://www.acmicpc.net/problem/2193 풀이 : DP문제입니다. 이친수는 1) 첫번째 숫자는 0으로 시작할수 없다. 2) 1이 연속으로 나올 수 없다. 이 두가지 조건을 만족해야합니다. 따라서 데이터를 쌓을 때 2번 조건을 통해 얻어 낼 수 있는 아래의 규칙에 따라 쌓으시면 됩니다. 규칙 1) 현재 자릿수의 끝 수가 1인 이친수(cache[i][1])는 이전 자릿수의 끝 수가 0인 이친수(cache[i - 1][0])에서 밖에 만들 수 없다. 규칙 2) 현재 자릿수의 끝 수가 0인 이친수(cache[i][0])은 이전 자릿수의 끝 수가 0인 이친수(cache[i - 1][0])와 1인 이친수(cache[i - 1][1]) 둘 다에서 만들 수 있다. 1 2 3 4 ..