dynamic programming

⏱ 시간 초과 테스트 14번부터 시간복잡도가 급격하게 증가한다.DP를 이용해서 데이터 비교 및 탐색 시간을 줄이는 방법으로 해결하였다. 문제정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.      입출력 예시     풀이 이 풀이는 뒤에서부터 탐색하는게 핵심이다. 가장 큰 값은 answer에 기억해두면, 다음 턴에 뒷부분을 다시 탐색 할 필요가 없어진다.#include usin..

🔗 문제 링크 : https://www.acmicpc.net/problem/1003    문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibona..

🔗 문제 링크 : https://www.acmicpc.net/problem/1309   문제어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.     입출력 예시     풀이 | Dynamic Programming우리의 크기가 N 일 때 사자를 배치하는 경우의 수를 DP(N)으로 표현하였습니다..

🔗 문제 링크 : https://www.acmicpc.net/problem/1010   문제재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수..

🔗 문제 링크 : https://www.acmicpc.net/problem/9655   문제돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.     입출력 예시     풀이 #1 | 랜덤 값을 이용한 풀이 (시뮬레이션)게임 진행에 대한 시뮬레이션을 하듯 1과 3 중 하나를 선택하는 경우를 바탕으로 풀었다.#include #include #include using namespace std;int main() { //.# 랜..

💣 (출제자님의 의도가... 맞겠지요..?) 좌표와 배열은 반대로 봐야한다는 사실은 항상 인지하면서 조심스럽게 문제를 해결해 왔다.처음부터 눈 부릅뜨고 "절대로" 여기서 실수 내지 말아야지!! 결심했다.하지만 문제에서 주어지는 vector> puddles가 좌표 값이었을 줄이야..심지어 앞 뒤가 같은 {2, 2}이어서 문제에 주어지는 그림을 보고도 알아차릴 수 없었단 게 함정이었다. 엄청난 실패 폭격 속에서 이유를 알아차렸을 땐..  🌠 🌠 🤯 🌠 🌠 🌠 🌠 🌠   문제계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우..

🔗 문제 링크 : https://www.acmicpc.net/problem/2747   문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.     입출력 예시     풀이 #include using namespace std;int fib[50];int main() { ..

🔗 문제 링크 : https://www.acmicpc.net/problem/2748   문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.     입출력 예시     풀이 #include using namespace std;long long fib[91];int main()..

🔗 문제 링크 : https://www.acmicpc.net/problem/1932   문제 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.     입출력 예시    풀이 #include #in..