배열 탐색 s. 부분합, 누적합 알고리즘(분할정복)

                                    📌 아주 유명한 단골 문제이다. 이번 기회에 확실하게 정리하자.

⚠️ n: 1 .. 100000 : 최대 nlogn
🤩 Follow up: divide and conquer

🤔 모든 탐색을 고려하는 것?
>>> O(n²) 🚫time Limit!

🤔 딕셔너리를 사용하여 문제풀기
>>> 자신 보다 왼쪽의 모든 합 중 가장 큰 합을 자기 자신 위치에 기록한다.
    >>> 🤔 자신 기준으로 오른쪽을 고려할 필요없는가?
        >>> 어차피 다음 요소가 자신마저 포함하여 계산하기 때문에 고려하지 않아도된다.
        >>> 항상 본인 위치의 누적합을 계산 해둔다.

                                    ✅ 딕셔너리를 사용한다.
>>> {idx: maxSum}

✅ for i, n in enumerate(nums):
>>> 자신(n)과 i - 1위 딕셔너리 키 값을 조회하여 비교 한다.
    >>> max(자신, 자신 + i - 1)

✅ 딕셔너리의 가장 큰 value가 정답이다.

                                    class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        mdic = {}

        for i, n in enumerate(nums):
            if i == 0:
                mdic[i] = n
                continue

            mdic[i] = max(n, n + mdic[i - 1])

        result = -9999999999999
        for key in mdic:
            result = max(result, mdic[key])

        return result

                                    📌 divide conquer : 문제를 반으로 나눠서 각 부분을 정복 후, 합쳐서 최종 문제를 푸는 알고리즘

🤔 어떻게 분할 정복을 적용할 수 있을까?
>>> 1. 절반으로 나눈다.
>>> 2. 갂 가장 큰 subarray를 구한다.
    >>> 2.1. 여기서 가장 idx가 낮은 값과, 가장 idx가 높은 값을 저장해둔다.
>>> 3. 가장 낮은 idx에서 가장 높은 idx 범위를 탐색하여 다시 최대값을 초기화 한다.
➡️ 이렇게 생각한 이유는, 연결 중간부가 끊어지면 안된다고 생각했기 때문이다.

                                    ✅ dictinary를 주고 받자.
>>> 처음에 전체 값을 업데이트해서 제공

✅ left_dict와 right_dict를 나눈다.
>>> 각각 dict를 업데이트 후 return

✅ dict를 서로 합친다.
>>> left + right
>>> left의 가장 큰 원소가 위치하는 곳 = 시작점
>>> right의 가장 큰 원소가 위치하는 곳 = 끝 점

✅ 분할 된 dict를 서로 합친다.

🤔 divide conquer이 맞을까.. ?

                                    class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        def divquer(ndict):
            print(">>> init <<<\n ndict: {}".format(ndict))
            if len(ndict) <= 1:
                print("return len <= 1: ndict: ", ndict)
                return ndict

            mid = len(ndict) // 2
            print("divide start: mid: {}".format(mid))

            ldict = {}
            for i in range(mid):
                if i not in ndict:
                    print("somethinis wrong... key fault i: {}, ndict: {}".format(i, ndict))
                    continue
                ldict[i] = ndict[i]

            print("left dict maded: ldict: ", ldict)
            rdict = {}
            for i in range(mid, len(ndict)):
                if i not in ndict:
                    print("somethinis wrong... key fault i: {}, ndict: {}".format(i, rdict))
                    continue

                rdict[i] = ndict[i]
            print("right dict maded: rdict ", rdict)

            left = divquer(ldict)
            right = divquer(rdict)

            print("\n[after divide]\n")

            print("left maded: {}\n right maded: {}".format(left, right))

            # combine two dict
            con = {}
            for k in left:
                con[k] = left[k]

            for k in right:
                con[k] = right[k]

            print("con maded: con: ", con)

            for k in con:
                if k - 1 not in con:
                    continue
                con[k] = max(con[k], con[k] + con[k - 1])
            print("<return!> con updated: con: ", con)

            return con

        init = {}
        for i in range(len(nums)):
            init[i] = nums[i]

        result_dict = divquer(init)
        max_sum = max(result_dict.values())

        return max_sum

                                    🤔 딕셔너리를 n..m까지 분할?
>>> keys = sorted(d)
mid = len(keys) // 2

# 중간 인덱스를 기준으로 분리
left_keys = keys[:mid]
right_keys = keys[mid:]

# 분리된 키를 이용해 딕셔너리 분리 (원하는 경우)
left_dict = {k: d[k] for k in left_keys}
right_dict = {k: d[k] for k in right_keys}

print("Left keys:", left_keys)
print("Right keys:", right_keys)
print("Left dict:", left_dict)
print("Right dict:", right_dict)

🤔 list의 min과 max값 쌈뽕하게 구하기
>>> max(list), min(list)
>>> dict.keys() : key들의 집합, dict.values() : value들의 집합
>>> dict의 경우 바로 min(dict), max(dict)로 해도된다 !