그랬었습니다

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 #include using namespace std; int main() { int input; cin >> input; int arg1 = 0, arg2 = 1, sum = 0; switch (input) { case 0: cout

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std; int countLine(int N); class Line {private: int A, B;public: void setLine(int A, int B) { this->A = A; this->B = B; } bool operatorA B; }}; int main() { int N; scanf("%d", &N); printf("%d\n", countLine(N));} int countLine(int N) {..

https://everyyy.tistory.com/75 [백준]11053-가장 긴 증가하는 부분 수열(Dynamic Programming) 이 문제 역시 동적 계획법으로 푸는 문제다. 주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다. 이 문제에는 가장 심플한 규칙이 있다. v[i][0]이 i번째 수의 값이고, v[i].. everyyy.tistory.com 11053번 가장 긴 증가하는 부분 수열 문제와 매우 흡사하고, 위 문제를 조금만 변형해면 풀 수 있는 문제이다. 우선 똑같이 가장 긴 증가하는 부분 수열을 구한다. 동시에 오른쪽에서 왼쪽으로 가면서 가장 긴 감소하는 부분 수열을 구한다. 왼쪽에서 오른쪽으로 이동하며 반환할 후보 변수에 일단 증가, 감소 중 더 ..

이 문제 역시 동적 계획법으로 푸는 문제다. 주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다. 이 문제에는 가장 심플한 규칙이 있다. v[i][0]이 i번째 수의 값이고, v[i][1]이 i번째 수의 값을 증가수열의 마지막 수로 잡았을 경우 가장 길게 만들 수 있는 증가수열의 길이라고 한다면, v[i][0] i)라면 v[i][1] < v[j][1]이다. 이 말이 무슨 말이냐면, 주어진 수열의 어떠한 값이 그보다 왼쪽에 있는 수열보다 크다면, 그 수를 마지막으로 하여 만들 수 있는 증가수열의 길이는 왼쪽에 위치한 그보다 작은 값을 마지막으로 하여 만들 수 있는 증가수열의 길이보다 길다. 라는 것이다. 따라서 풀이는 간단하다. 왼쪽에서부터 오른쪽으로 진행하면서 하나씩 ..

이 문제는 2579번 계단 오르기 문제와 매우 흡사하다. 다만 하나의 조건이 빠졌다. 다만 그 조건이 계산의 편의를 돕는 조건이었기 때문에 조건이 빠졌다고 계산이 쉬워진 게 아니라, 중간에 하나의 계산이 추가됐다. https://everyyy.tistory.com/71 [백준]2579-계단 오르기(Dynamic Programming) 계단을 오르는 방법은 2가지 방법이 있다. 한 계단씩 오르는 방법과 두 계단씩 오르는 방법. 그리고 제약조건으로 "연속된 세 개의 계단을 모두 밟아서는 안된다."가 있다. 조금 관점을 바꿔서, 올라올 계단의 입.. everyyy.tistory.com 일단은 위 포스팅을 참고하면 좋다. 계단 오르기에서는 있었지만 이 문제에서 없어진 조건은 "무조건 1칸이나 2칸을 전진해야 한..

정답률이 30퍼도 안되는 문제다. 근데 솔직히 정답률 더 높은 계단 오르기나 1로 만들기 문제보다 쉽게 느껴졌다. 왜지..? 요즘 동적 계획법 문제를 많이 풀어서 익숙해졌나? 아무튼.. 이 문제는 의외로 간단하다. 중복을 생각할 필요가 없다. 대신 예외를 생각해야한다. 1에서 파생되는 수는 10, 12가 있다. 2에서는 21, 23이 있다. 등등.. 그럼 두 자리 숫자로 넘어가보자. 10에서 파생되는 수는? 101뿐이다. 89에서 파생되는 수는? 898뿐이다. 나머지는 모두 끝 자리 숫자에 1을 빼고 더하는 두 가지 경우가 나온다. 복잡하게 생각하지 말고 맨 끝자리만 보면 된다. 길이 N인 계단 수 중에서 끝자리가 0인 수의 개수는? 길이 N - 1인 계단 수 중에서 끝자리가 1인 수의 개수와 같다. 끝..

이 문제 역시 Dynamic Programming으로 해결해야 한다. 이 문제는 문제 그대로 큰 숫자를 나누고, 빼면서 접근하면 안 된다. 만약 그렇게 한다면 숫자가 3과 2로 나누어 떨어지는지 검사하는 데에만 엄청난 리소스가 낭비된다. 반대로 생각해보자. 2로 나누어 떨어지는 수는 2로 나눈 몫의 2배와 같은 값이다. 3으로 나누어 떨어지는 수는 3으로 나눈 몫의 3배와 같은 값이다. 그렇다면 역으로 작은 수에 2나 3을 곱하고, 1을 더하면서 숫자를 늘려가면 된다. 1부터 시작한다. 1의 3배는 3이다. 한 번의 연산이니 1을 입력한다. 1의 2배는 2이다. 한 번의 연산이니 1을 입력한다. 1+1은 2이다. 그런데 2에는 이미 숫자가 입력되어 있다. 비교 후 더 작은 값을 넣는다. 이렇게 하면 배열..

계단을 오르는 방법은 2가지 방법이 있다. 한 계단씩 오르는 방법과 두 계단씩 오르는 방법. 그리고 제약조건으로 "연속된 세 개의 계단을 모두 밟아서는 안된다."가 있다. 조금 관점을 바꿔서, 올라올 계단의 입장에서 보자. 올라오는 방법은 한 계단 아래에서 올라오는 방법과 두 계단 아래에서 올라오는 방법이 있다. 그리고 s[i][1]을 "가장 마지막에 한 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"라고 정의하자. s[i][2]는 "가장 마지막에 두 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"이다. 그럼 s[i][1]을 살펴보자. 한 계단 아래에서 올라왔다. 즉 i - 1번째 계단과 i번째 계단을 밟았다는 것이다. 따라서 이 방법을 골랐을 경우에는 i - 1번째 ..

또 다른 동적 계획법 문제인 RGB거리와 크게 다르지 않은 문제이다. RGB거리 문제를 이해할 수 있다면 크게 어렵지 않게 이해할 수 있을 것이다. https://everyyy.tistory.com/69

백준에서 단계별로 풀기를 위에서부터 100 문제 정도 풀면 동적 계획법이 나온다. 동적 계획법1 파트에서 4번까지는 피보나치 같은 비교적 간단한 문제만 나온다. 여기까지는 알고리즘에 대한 공부를 따로 하지 않아도 직관으로 어느 정도 풀 수준이라고 할 법하다고 생각한다. 하지만 이 문제는 대중적? 알고리즘의 한 부분인 Dynamic Programming을 공부하지 않으면 꽤나 고전할 법한 문제이다. 물론 따로 공부하지 않았다고 해서 풀지 못할 문제라는건 아니지만.. 여하튼 이 문제는 동적 계획법을 처음 공부한 사람이 익숙해지기 위해 풀어보는 입문용 문제라고 봐도 좋을 것 같다. 자 이제 문제를 살펴보자. i번째 집은 i-1번째와 i+1번째 집과 같은 색으로 칠할 수 없다. 1번째 집부터 차례대로 집의 색을..