그랬었습니다

계단을 오르는 방법은 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번째 집부터 차례대로 집의 색을..

123456789101112131415161718192021222324252627282930313233//#define _CRT_SECURE_NO_WARNINGS#include using namespace std; long long wave(int input); int main() { int N; cin >> N; for (int i = 0; i > input; cout

123456789101112131415161718192021222324//#define _CRT_SECURE_NO_WARNINGS#include using namespace std; int fib(int n); int main() { int N; cin >> N; cout

그냥 n번째 피보나치 수를 계산하는 문제가 아니다. n번째 피보나치 수를 재귀 함수로 구할 때, fib(0)과 fib(1)이 몇 번씩 호출되는지를 묻는 문제다. 근데 딱히 다를 건 없다. 동적 계획법으로 푸는데, 누적하는 수가 피보나치 수가 아니라 0과 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 //#define _CRT_SECURE_NO_WARNINGS #include using namespace std; void fib(int n); int main() { int n; cin >> n; for (int i = 0; i >..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 //#define _CRT_SECURE_NO_WARNINGS #include using namespace std; unsigned long long fib(int n); int main() { int n; cin >> n; cout

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647//#define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std; class Client {private: int age, order; char name[101];public: void setInfo(int age, char* name, int order) { int i; this->age = age; for (i = 0; name[i] != NULL; i++) this->name[i] = name[i]; this->name[i] = NULL; this->order = orde..

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556//#define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std; class Text {private: string text;public: void setText(string text) { this->text.clear(); this->text.append(text); } bool operatortext.length() text.length() == text.text.length()) { for (int i = 0; i text.length();..

사실 설명할 거리도 없는 문제이긴 한데.. 그리고 이 문제는 정렬 자체가 목적인 문제가 맞긴 하지만, 예외적으로 std::sort를 사용했다. 연산자 오버로딩을 사용한다는 것에 의의를 둔다랄까.. 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 //#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; class Position { private: int xpos, ypos; public: Position() { this->xpos = 0; this..