[DP] 제곱수의 합 (백준 1699번)

알고리즘에 대해

 

알고리즘을 배우기 전에 대부분의 사람들이 궁금한 것이, 수학적인 능력의 유무가

알고리즘을 배우는 데에 필수적인지 일 것이다.

나도 어렴풋이 그런 걸 느끼기도 했고, 경험해가며 굳이 필요없다는 것을 느꼈다.

인공지능을 한다거나, 아니면 그래픽스를 할 게 아니라면 필요없다는 것을 이해할 수 있었다.

 

비록 내가 인공지능이나 그래픽스를 해본 것은 아니지만,

수식을 쓰는가 안 쓰는가, 그런 도구적인 쓰임과 자신이 사용하는 공식들에 대한 이해 없이

그저 수학적 사고력만으로 풀 수 있는 문제들 선이 내게 필요한 cut line 이었기 때문이다.

 

그 이상으로 가려면 아직 시간도 많고, 필요할 때 배워도 문제 없겠다고 싶었다.

(Q. 나는 하루에 8시간 정도 code를 짜고 있는데, 필요할 때 배워도 문제 없겠다는 의미는?)

(A. 필요할 때 8시간 씩 수학을 배우면 되지 않을까, 필요한 수식, 필요한 논문만 봐가면서.)

 

그러나 DP 문제는 다르다.

 

이전에도 말했지만 몇 번을 말해도 부족하지 않은 거 같다.

누군가 내게 지금까지 배운 알고리즘을 설명하라고 하면 나는 다음과 같이, 다음의 순서로 설명한다.

(알고리즘을 다뤄 본 사람들을 대상으로 설명한다면.)

 

먼저 전체 탐색을 위해서 for문을 쓰는 방식, 그리고 for문을 중첩하는 방식들,

우리가 알고리즘이라는 생각을 하지 않고 본능처럼 쓰고 있는 그러한 방식들을

brute force라고 한다.

 

그리고 그 brute force에서 재귀적인 방법을 사용하여

더 활용도를 높이고 시간 복잡도를 낮춘 것(활용도에 따라 다르겠지만)을 dfs라고 한다.

그리고 이 dfs에서 매개변수로 현재 stack의 깊이를 전달하는 것을 back tracking이라고 한다.

 

반면 brute force에서 queue를 이용해 물결이 치는 것처럼,

현재 index로부터 주변으로 퍼져 나가며 탐색하는 방식을 bfs라고 한다.

bfs에 가중치를 반영하여, 방문 여부와 무관하게 다시금 방문할 수 있는 가능성을 열어준 것을

(이전의 방문 기록이 그저 true or false 였다면, 이 방식은 가중치의 합이다.)

다익스트라 알고리즘이라고 한다.

 

내가 모르는 부분이 있겠지만,

이것들을 나는 일단 '탐색' 알고리즘이라고 생각하고 싶다.

 

그리고 이 탐색 외의 방식,

(물론 탐색이 아니라고 해도 탐색의 형태로 문제를 해결할 수 있긴 하다.)

(데이터의 구조를 어떻게 이해하느냐에 따라 문제를 푸는 방식도 달라질 테니.)

 

예를 들어 DP가 있다. (또 이 안에 memorization이 있다.)

 

DP는 dynamic programming 이라는 이름인데, 정말 이름이 이걸 잘 표현하고 있는 듯하다.

다만 dynamic한 것은, 문제 자체보다는 개발자가 아닌가 싶다.

다른 알고리즘과 다르게 형식이라는 것이, 무척이나 빈약하다.

어쩌면 형식 자체가 간결하다는 말이 적합할지 모르겠지만,

마치 동적 할당을 하여 부족한 메모리를 지원받듯이, 부족한 조건을 개발자에게 요구한다.

 

탐색 알고리즘이 인접한 항에 대하여 접근한다는 점 때문에, 순차적인 모습을 띄는데,

DP는 index는 순차적일지 몰라도 항과 항 사이의 조건식을 개발자가 직접 생각해야 한다.

그래서 이전의 "전깃줄" 문제처럼 복잡할 수밖에 없다.

 

https://kscodebase.tistory.com/60

[LIS] 전깃줄 (백준 2565번)

 

 

내가 푼 순서는 다음과 같다.

 

#include <iostream>
#include <cmath>
using namespace std;
 
 
int main(void)
{
    long long int num;
    cin >> num;
    
    int count = 0;
    while (num > 3)
    {
        for (long long int i = num; i > 1; i--)
        {
            if (i * i <= num)
            {
                count++;
                num -= i * i;
//                cout << i << ' ';
            }
        }
    }
    // 43인 경우 9 + 9 + 25로 가능한데, 내 코드로는 36 + 4 + 1 + 1 + 1로 된다.
    // 이걸, 그냥 해결은 힘들 거 같고, DP로 해결해야 할 거 같다.
//    cout << endl;
    cout << count + num;
}

 

내가 처음에 한 방식이다, 위에서부터 점진적으로 빼는 방식이다.

만약 16이란 숫자가 있다면 4^2를 빼면 0이 되므로 for문은 멈추고 count는 1로 멈춘다.

3이하의 수는 무조건 1^2가 해당 숫자만큼 필요하기 때문에

마지막 출력에서 count + num을 출력하게끔 하였다.

하지만 주석에서와 같이 43같은 숫자를 볼 때 가장 큰 수부터 빼는 게 가장 항이 적은 경우가 아니다.

 

#include <iostream>
#include <cmath>
using namespace std;
 
int num;
int visited[100001];
int minV = 987654321;
int counted;
 
void dfs(void)
{
    if (counted > minV) return;
    // 단순히 dfs로만 하면 시간초과가 난다는 것을 알아서, 이 조건문을 추가했다.
    // 이미 값이 더 커진 경우에는 바로 끝내게끔 한 것이다.
    // 이것으로 빨라지긴 했지만, 그래도 출력 값에 비례하는 수 많은 경우의 수가 나온다.
    // sqrt(num)을 대신해서 for문의 start 지점을 직접 지정해주는 방법도 있을 거 같지만,
    // 가독성이 떨어지는 코드를 작성하고 싶지는 않다.
    // 그럼 어떻게 해야 할까...
 
    if (num == 0)
    {
        if (counted < minV) minV = counted;
        return;
    }
 
    for (int i = sqrt(num); i >= 1; i--)
    {
        if (num - i * i >= 0)
        {    
            counted++;
            num -= i * i;
 
            visited[i]++;
            dfs();
            num += (i * i);
            counted--;
//            visited[i]--;
//            num += i * i;
        }
    }
}
 
int main(void)
{
    cin >> num;
//    int data = num;
    
    dfs();
 
//    for (int i = 1; i <= data; i++)
//    {
//        cout << visited[i] << ' ';
//    }
 
//    cout << endl;
    cout << minV;
}
// dfs 방식으로 일단 구현해보았다.
// dfs로 전체탐색을 하니까 당연히 답이 나오긴 하는데, 어마무시하게 느리다.
// 이 방법은 무조건 시간초과가 나올 테니 역시 DP가 답인 거 같다...
// DP로 풀려면 머리 터질 거 같아서 싫었는데...

visited 배열은 볼 필요가 없다.

 

내가 dfs로 풀었을 때도 답은 나왔다, 당연히 그럴 수 밖에 없는 게 전체 탐색이니까.

N과 M 문제를 풀었을 때와 같이, 모든 경우의 수를 다 찾아보는 데 틀릴 리가 없다.

다만 이 방식은, 시간 초과가 매우 크다.

일부로 sqrt 함수를 써서 시간을 단축하게끔도 했고, 일정 이상 깊이로 못들어가게 방지도 했다.

하지만 탐색하고자 하는 숫자 (초기값 num)가 크면 클수록 경우의 수가 많아졌다.

 

n^2의 시간 복잡도, 그 이상을 가지고 있을 것이다.

 

#include <iostream>
#include <cmath>
using namespace std;
 
int dp[100001];
 
int main(void)
{
    int num;
    cin >> num;
 
    for (int i = 1; i <= num; i++)
    {
        dp[i] = i;
        for (int j = 2; j * j <= i; j++)
            if (dp[i - j * j] + 1 < dp[i])
                dp[i] = dp[i - j * j] + 1;
    }
 
    cout << dp[num];
 
    //    for (int i = 1; i <= num; i++)
    //    {
    //        cout << i << " : " << dp[i] << endl;
    //    }
    // 확인을 위해 만들어 본 코드이다. 모든 index에 해당하는 dp값을 출력한다.
}
 
//43 - 1 = 42;
//43 - 4 = 39;
//43 - 9 = 34;
//43 - 16 = 27;
//43 - 25 = 18;
//43 - 36 = 7;

 

마지막 코드다.

DP의 방식으로 해결했다, 솔직히 DP로 풀고 싶지 않았다.

DP 말고 다른 방식으로 풀고 싶었다기 보단, DP는 짧은 만큼, 개발자에게 두뇌 사용을 강요하기 때문이다.

 

솔직히 말하면, 각 항마다의 관련이 없어 보이기 때문에 더 힘들었다.

1과 2, 2와 3, 3과 4, 이렇게 관련이 없어 보였다.

그렇지만 dp의 대부분이 중첩 없는 반복문으로 각 항끼리의 관계를 파악하는 문제였기 때문에

1부터 시작하여 상당히 오랜 시간이 걸렸고, 전혀 진척이 없었다.

 

결론부터 말하면, 중첩된 반복문이었다.

 

DP문제는 항상 다음과 같은 꼴로 나온다.

 

if (DP[a] > DP[b] + 1) DP[a] = DP[b] + 1;

단, b 는 a보다 작아야 한다.

 

a는 우리가 지정하는 것, 1부터 순차적으로 증가하는 i 값에 해당하지만

b는 a보다 1 작은 수인지 아니면 2 작은 수인지, 아니면 어떠한 조건식인지 알 수가 없다.

DP 문제는 이처럼 b가 무엇인지 추론하는 문제다.

 

(중첩된 반복문을 쓰지 않아도 되긴 하지만, 이번 문제같은 경우는 b에 들어갈 수 있는 숫자가 몇 개인지 모른다.)

(a에 따라 달라지기 때문에 반복문을 쓰는 게 훨씬 좋았다.)

(하긴, 중첩된 반복문이라는 게 결국 for문 안에 if문을 여러 개 넣는 것과 같은 꼴이긴 하다.)

 

---

 

아까 문제가 된 43을 볼 때,

DP[43]는 DP[43 - j^2] + 1, 단 43 - j^2 > 0인 경우에 한하여, 가장 작은 값을 입력받는다.

 

너무 어려웠다.