기록공간

동적계획법을 사용하는 문제이다. 규칙을 먼저 살펴보자. * 1일 경우 1 -> 1개 * 2일 경우 1 + 1 2 -> 2개 * 3일 경우 1 + 1 + 1 2 + 1 1 + 2 3 -> 4개 * 4일 경우 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 1 1 + 3 3 + 1 -> 7개 (혹은 F(3) + F(2) + F(1) = 4 + 2 + 1 = 7) * 5일 경우 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 1 + 1 1 + 1 + 2 + 1 1 + 1 + 1 + 2 2 + 2 + 1 2 + 1 + 2 1 + 2 + 2 3 + 1 + 1 1 + 3 + 1 1 + 1 + 3 2 + 3 3 + 2 -> 13개 (혹은 F(4) + F(3..

동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 먼저 살펴보자. * 정수 2 1. 1을 빼면 1이 된다. 2. 2로 나누어 떨어지고 1이 된다. 3. 3으로 나누어 떨어지지 않는다. -> 정수 2를 1로 만드는 최소 횟수는 1이다. * 정수 3 1. 1을 빼면 2가 된다. 정수 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 2. 2로 나누어 떨어지지 않는다. 3. 3으로 나누어 떨어지고 1이 된다. -> 정수 3을 1로 만드는 최소 횟수는 1이다. * 정수 4 1. 1을 빼면 3이 된다. 정수 3에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 2. 2로 나누어 떨어지고 2가 된다. 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 3...

동적계획법(Dynamic Programming)을 사용하여 가장 긴 최장증가수열(LIS)을 구하는 문제이다. 동적계획법 : https://lipcoder.tistory.com/49 동적계획법(Dynamic Programming) 동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진.. lipcoder.tistory.com 최장증가수열 : https://lipcoder.tistory.com/50 최장증가수열 - LIS(Longest Increasing Subsequence) LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임..

행렬의 행(N)이나 열(M)의 크기가 하나라도 3보다 작은 경우에는 원소 뒤집기 작업(XOR)이 불가능하기 때문에 A와 B가 서로 같은지만 확인하면 된다. 만약 둘 다 3보다 큰 경우 1행부터 N - 3행까지 그리고 1열부터 M - 3열까지 A와 B가 특정위치에서 서로 같은지를 검사하며 다른 경우 그 위치에서부터 XOR를 진행한다. 모두 끝난 후에 행렬 A와 B가 같은지 확인하면 끝이 난다. 코드는 다음과 같다. #include #include #include using namespace std; void XOR(char** mat, int N, int M) { for (int i = N; i < N + 3; ++i) { for (int j = M; j < M + 3; ++j) { char temp = ..

K개의 부등호가 있을때 각각 최대값, 최소값이 되기 위해서는, 최대값은 9부터 9 - k까지, 그리고 최소값은 0부터 0 + k까지 차례대로 가지고 와야한다. 그리고 가지고 온 숫자들의 수열을 이용하여 입력한 부등호가 만족할때 까지 검사하면 각각 부등호에 맞는 최대값, 최소값이 나온다. 최대값은 현재 수열의 이전 수열을, 최소값은 현재 수열의 다음 수열을 차례대로 가져오며 검사를 진행해야 한다. 코드는 다음과 같다. #include #include #include using namespace std; bool check(char* num, char* symbol, int size) { for (int i = 0; i ': if ..

LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임의의 수열이 주어졌을때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장증가수열이라고 한다. 예를 들어 다음 수열이 주어졌다고 하자. 3 5 7 9 2 1 4 8 위 수열에서 몇 개의 수를 제거해 부분 수열을 만들었다고 하자. 3 7 9 1 4 8 (5, 2 제거) 7 9 1 8 (3, 5, 2, 4 제거) 3 5 7 8 (9, 2, 1, 4 제거) 1 4 8 (3, 5, 7, 9, 2 제거) 이들 중 세번째와 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다. 그리고 세번째와 같이 이러한 수열 중 가장 긴..

동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진 것이다(...). 분할정복(Divide and Conquer)과 다른 점 거의 비슷하지만 결정적인 차이점이 존재한다. 그것은 바로 나눠진 작은 문제에서 중복이 일어나는가 안일어나는가이다. 분할정복은 큰 문제를 해결하기 위해 그냥 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 동적계획법은 작은 문제들이 반복되는것(단, 바뀌지 않음)을 이용해 풀어나가는 방법이다. 동적계획법의 방법 모든 작은 문제들은 꼭 한번만 풀어야 한다. 그러므로 작은 문제의 정답은 어딘가..

그리디 알고리즘 문제이다. 끊어진 (적어도)N개의 기타줄을 사기위한 최소 비용을 구하기 위해서는 우선 브랜드 별로 오름차순으로 정렬하여 가장 싼 패키지 가격과 가장 싼 낱개 가격을 각각 구해준다. N이 6이상일 경우 패키지 가격으로 살 것인지 아니면 낱개 가격을 살것인지를 먼저 정해야 한다. 전자의 경우 N을 6과 나누어 나온 값 만큼 패키지 가격을 곱하여 최종 가격에 더해준다. 그리고 만약에 나머지 사야할 기타줄이 있는 경우, 그 갯수와 낱개의 곱이 패키지의 가격을 넘는다면 패키지 가격을 최종 가격에 더해주고 아닌경우 (낱개가격 * 사야할 기타줄 수)를 더해준다. 후자의 경우에는 그냥 (낱개가격 * 사야할 기타줄 수)를 더해주면 된다. 코드는 다음과 같다. #include #include using n..