나만 아는 것만 있는 연구실

동일한 연산임에도 답이 다르게 나올 때가 있다.

나누기 연산의 결과는 float로 바뀌므로 아랫 자리 수가 소실됨.
int를 이용해서 캐스팅해도 막을 수 없음.

동적 프로그래밍은 n번째의 정답을 추론하기 위해 n-1 번째 정답을 이용하는 것을 의미한다.

수열에서의 가장 큰 합을 가지는 Subarray를 찾는 문제를 해설.

풀이는 다음과 같다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_num = -99999
        now_num = 0
        for i in nums:
            if(now_num < 0):
                now_num = 0
            now_num = now_num+i
            max_num = max(max_num, now_num)
        return max_num

수열 nums에 대해서 maximum subarray의 합을 구하는 것은

nums[:-2] 즉, 마지막 바로 직전까지의 수열을 이용하면 가능하다.

nums보다 하나 적은 수열에서 얻은 maximum subarray의 합이

다음 정답에 어떻게 영향을 미치는 가를 고민해보자.

x_n이 수열의 마지막 숫자라고 생각했을 때,
생각할 수 있는 정답은 3가지 경우 중 하나가 된다.

① 바로 이전 항을 포함하며 계속 이어지는 수열
② x_n 단 하나 (바로 이전 항까지의 합이 음수인 경우)
③ x_(n-1) 을 포함하지 않는 이전의 수열

여기서 헷갈릴 수 있는 부분이 x_n이라는 수를 만나기 전까지

그 직전까지의 Subarray를 생각하는 것이다. 

최대의 Subarray를 찾기 위해서는 수열의 첫번째 항부터

그 다음 수가 양수이든 음수이든 상관없이 계속 더해보면서

부분 합을 체크해야 한다. 왜냐하면 subarray를 추가하는 과정에서

중간에 음수가 나온다고 해도 그것을 포함한 수열의 합이 양수라면,

다음에 나타날 숫자들이 역대 최대의 부분합을 만들어 낼 가능성이 있기 때문이다.

( +1이라도 최대에 보탬이 될 수 있음)

다시 말해 새로운 수가 음수여서 직전의 부분합보다 감소한다고 해도

이후 또 새로운 숫자를 추가하면 그 부분합이 역대 최대가 될 수 있다는 뜻이다.

다만 만들던 subarray를 끊고, 새롭게 시작해야 하는 순간이 있는데

그것은 여태까지의 subarray의 합이 음수가 되는 시점이다.

이어오던 subarray를 새로운 수에 붙이면 오히려 손해이기 때문에

Subarray를 이어나갈 필요가 없이, 새로운 수를 기점으로 다시 subarray를 따진다.

다시 본론으로 돌아오면 n개의 수열 nums의 최대 부분합은

n-1개의 수열 nums[:-2]의 최대 부분합과,

혹시 몰라서 끌고 온 subarray를 이용해서 구할 수 있다.

1. 혹시 몰라서 직전의 수를 포함하면서 끌고 온 subarray + 새로운 수(x_n)

2. 새로운 수(x_n)

3. 1번과 같은 수인지 아닌지는 모르지만 지금까지 중 역대 최대였던 합

위의 코드에 의하면 '혹시 몰라서 직전의 수를 포함하면서 끌고 온 subarray'의 부분합은

now_num 이라는 변수에 저장되어 있다. now_num이 역대 최대의 부분합인지는 모르지만

새로운 수 x_n을 더했을 때 최대의 부분합이 될 지,

아니면 그 뒤로도 계속 이어나갈 때 어느 순간 최대의 부분합이 될지 모른다.

그렇기 때문에 now_num에 저장하면서 부분합을 저장해나가는 것이다. 

이것은 지금까지 제일 컸던 부분합을 기억하는 것과는 별개의 것이 된다.

물론 끌고 온 subarray가 음수라면 그것은 전혀 의미가 없다. 무조건 방해가 된다.

이때는 0으로 바꾼다. 이것은 새로운 수로부터 다시 subarray를 만들겠다는 

단순한 테크닉에 불과하다. now_num = max( now_num + i, i) 의 꼴로 생각해도 무방하다.

이전까지의 부분합에 x_n을 더하거나, 혹은 x_n으로 새로운 subarray를 시작한다.

최종적으로 지금까지 역대 최대의 합(nums[:-2]의 최대 부분합) max_num과

새롭게 만들어진 subarray를 비교한다. 여기서 이긴 수가 최대의 부분합이 된다.

카데인 알고리즘은 이 문제만을 풀기 위해 생각한 알고리즘이기 때문에,

단순히 이 문제를 이렇게 풀었다라는 이해를 넘어서는

동적 프로그래밍 관점에서의 포괄적인 이해가 필요하다.

우리는 n번째 항의 정답을 얻기 위해서 n-1번째 정답을 기억해놨다.

그렇지만 n-1번째 정답과 무관한 n번째 정답이 만들어질 가능성이 있었기 때문에

정답이 될 수 있는 경우를 모두 고려해봐야만 했다.

(이를 Greedy 하다고 생각할 수도 있는 것 같다.)

알고리즘의 핵심은 "이전까지의 사례"를 이용했다는 점이다.

subarray를 이어가는 것도, max_num을 기억하고 비교하는 것도 그러하다.

결국 직전까지의 항과 지금의 항의 '관계'와 정답의 가능성을 얼마나 잘 이해하고,

가장 효율적인 형태의 식을 정의할 수 있느냐가 동적 프로그래밍의 열쇠인듯 하다.

3.x 버전에서 깔린 라이브러리가 그대로 남아있는 경우 새로운 Package 를 설치할 때 발생하는 문제인 듯 하다.

스택 오버 플로우에 제시된 해결 방법으로 잘 안돼서 그냥 대충 해결 봤다.

.libPaths()

# [1] "/usr/local/lib/R/site-library"
# [2] "/usr/lib/R/site-library"
# [3] "/usr/lib/R/library"

해당 하는 폴더로 가서 안에 있는 폴더를 전부 삭제한다.

sudo rm -rf /usr/lib/R/library/*
sudo rm -rf /usr/lib/R/site-library/*

그냥 이렇게 다 지워버리고

sudo apt-get remove r-base-core
sudo apt-get remove r-base
sudo apt-get autoremove
sudo apt install r-base

그리고 재설치 하면 되긴 한다.

소스코드를 외부에서 불러오면 빌드했을때 이런거 뜸

내 경우의 정답을 찾았다. 빌드 버전이니 컴파일러니 링커니 그딴거 상관없고

외부에서 불러온 소스 파일이 C 인데 내가 원래 쓰던 소스파일이 CPP 이다 하면

맛이 가는 현상이 일어난다는 것. 그러므로 그냥 소스 파일 확장자를 cpp로 바꿔주자.