------------------------------------------------------------------------------------------------------------------------------------------- 문제풀이 1. 문제를 풀 수 있는 방법은 DFS 알고리즘과 DP 알고리즘이 떠올랐다. 하지만 이 문제는 최종 최댓값만을 원하므로 DP 알고리즘이 시간복잡도 면에서 더 좋다 생각하여 DP 알고리즘으로 풀게 되었고, 또한 DP 알고리즘 특성상 이전 값의 계산한 결과를 저장해두고 동일한 부분 문제가 다시 등장할 때 재 사용함으로써 중복 계산을 제거할 수 있기 때문인 이유도 있다. 2. 즉, 이전 메모리 값을 활용하면 좋은 문제임을 알아서 다음 단계로..

----------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 문제를 보면 경우의 수가 여러가지인 경우인 문제이다. 처음에는 각 집마다 색을 선택하는 경우가 2가지씩 생기므로 계속해서 완전 탐색한다면 ( 2^n) 복잡도 경우의 수가 기하급수적으로 증가하게 되므로 이 문제에 옳치 않은 풀이 방법이라 생각했습니다. 2. 따라서 이전의 결과값을 저장하고 재활용하는 Dynamic Programming을 사용하여 각 집을 특정 색으로 칠했을 때..

----------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 해당 문제는 시간제한이 0.25초로 빡빡한 문제로 일반적인 DFS 구조를 사용해서 재귀함수를 호출 하면서 O(2^n)씩 해당되므로 c++ 1초당 계산이 약 10^8인 것을 계산하면 해당 방법으로는 문제를 해결할 수 없음을 알 수 있다. 2. DP 방법을 이용하는데 DP는 이전에 구한 값을 미리 저장해 두고 재사용하여 불필요한 함수 호출과 중복 계산을 제거하는 방식이다. ----------..

----------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 3가지의 숫자의 조합으로 합을 만들어 특정한 숫자와 같게 만드는 문제이므로 일단 DFS 재귀함수 방식과 DP 점화식 방법을 생각함. 2. DFS 방식으로 문제를 접근할 시 시간복잡도가 O(3^n)으로 목표로 하는 숫자가 크면 클수록 시간복잡도가 커 시간 제한에 걸릴 확률이 높아진다. 따라서 DP 방법으로 문제 풀이를 한다. 3.출처: https://blog.naver.com/Po..

#include #include #include using namespace std;int solution(int N, int number) { int answer = 0; vector> m_vecDp(9); int sum =0; for(int i=1; i 문제 접근 순서 1. 처음에는 아무리 생각해도 규칙성을 어떻게 짜야하고 어디까지를 제한을 둬서 반복문을 돌려야 할지 너무 막막했다. 2. 문제를 자세히 보니 최솟값이 8보다 크면 -1을 return 하라고 나와 있는걸 보고 눈치를 채서 아 for문을 8이하 까지 돌려라는 말이구나를 눈치 챘다. 3. 하지만 문제의 규칙성을 이해하지 못하여 하나하나 대입해가면서 점화식을 세워봣다. Dp[1] =..

#include #include #include #include #include using namespace std; int main(){ int Number; cin >> Number; vector m_vec(Number+1, 1000000); m_vec[1] = 0; for(int i=2; i 문제 풀이 순서 1. 처음에는 DFS 알고리즘을 고민했다. 그러나 이 방법은 지수 복잡도를 가지므로 가장 큰 수가 10^6이므로 지수복잡도를 가지는 DFS로 3가지 방향으로 간다면 시간초과 오류가 발생할 것이라 생각해서 PASS 했다. 2. 그렇다면 생각을 바꿔 Dynamic Programming 알고리즘을 사용해봐야 겠다고 생각했다. ( 메모리를 재사용하는 알고리즘 ) 왜냐하면, 문..