728x90 반응형 전체 글77 [algorithm] 백준 - 합분해 이 문제는 DP문제이다. 0부터 n까지 k개를 더해서 n이 되는 경우의 수를 구하는 것이며, 덧셈의 순서가 바뀐 경우는 다른 경우로 센다. 그리고 한개의 수를 여러번 쓸 수 있다. n은 2고 k는 2이라고 예를 들어보자. k n n을 구하기 위한 과정 1 0 0 경우의 수 : 1개 1 1 1 경우의 수 : 1개 1 2 2 경우의 수 : 1개 2 0 0 0 경우의 수 : 1개 2 1 0 1 1 0 경우의 수 : 2개 2 2 0 2 1 1 2 0 경우의 수 : 3개 따라서 3개라는 것을 알 수 있다. 여기서 알아야할 것은 n을 구하기 위해서는 사실 k n n을 구하기 위한 과정 1 0 0 경우의 수 : 1개 1 1 1 경우의 수 : 1개 1 2 2 경우의 수 : 1개 2 0 0 0 경우의 수 : 1개 2 1.. 2020. 11. 3. [나의 목표] 11월 30일 이 문제집을 올쏠하는 것이 목표이다. 내가 알고리즘을 풀면서 풀이과정을 적는 이유는, 풀이과정을 이해하기 위한 목적도 있으나 풀이과정을 글로 써보고 말로 말해보면서 머릿 속에 있는 것을 말로 설명하는 연습을 하기 위함이다. 즉, 기술 면접을 준비하기 위해서 연습하고 있다. 그때까지 화이팅! 2020. 11. 3. [algorithm] 백준 - 제곱수의 합 DP문제이다. 어떤 자연수는 제곱수의 합으로 이루어져 있으며, 합을 이루는 가장 적은 항의 개수를 리턴하는 것이다. 자연수 제곱수의 합 1 1 18 (3개) 4^2 + 2 = 18 (2개) 3^2 + 3^2 = 18 ... 가장 적은 개수: 2개 제곱 수가 가장 큰 수와 상관 없이 적은 개수를 이루기 위해서는 모든 제곱수와 비교해서 적은 개수를 구해야한다. 따라서 제곱수에 해당하는 수는 제곱수 1개로 이루어져 가장 적은 수이므로 별도로 vector에 삽입하고, if((int)sqrt(i) == sqrt(i)){ dp[i] = 1; multiplyVector.push_back(i); } 제곱수가 아닌 수는 삽입된 수 중 가장 적은 항으로 이룰 수 있는 경우를 찾아 DP에 삽입했다. dp[i] = 98765.. 2020. 11. 3. [algorithm] 백준 - 연속합 2 이 문제는 DP 문제이다. 1. 수는 한 개 이상 선택해야한다. 2. 수열에서 수를 하나 제거할 수 있다. 수를 제거했을 경우, 수를 제거 하지 않았을 경우로 나누어서 계산한다. 만약 수를 제거 했다면, 현재 위치한 수를 합산하지 않는다면, 여태까지 수열 중 제거한 적이 없는 값 합산한다면 제거한 적이 있는 값 을 비교해서 큰 값을 누적한다. dp[i][1] = max(arr[i] + dp[i - 1][1], dp[i - 1][0]); 수를 제거하지 않는다면, 현재 위치한 수와 수열 중 제거한 적이 없는 값을 비교해서 큰 값을 누적한다. dp[i][0] = max(arr[i] + dp[i - 1][0], arr[i]); 따라서 이런 식으로 코드를 작성했다. // 연속합(2) #include using n.. 2020. 11. 3. 이전 1 ··· 9 10 11 12 13 14 15 ··· 20 다음 728x90 반응형
