내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/43105

DP 유형의 문제입니다.

삼각형을 좌측으로 정렬해 계단 형태의 2차원 배열로 생각하고 풀면 쉽게 풀립니다.

삼각형을 내려오는 방향은 좌하단, 우하단 두가지만 가능합니다.

즉 내 위치가 i 번째 행의 j 번째 열이라면 내 위치로 오기 위해선 반드시 (i-1, j-1) 또는 (i-1, j)을 지나야 합니다.

따라서 해당 위치로 오는 경로의 최댓값은 (i-1, j-1) 또는 (i-1, j)로 가는 경로 중 큰 값에 해당 위치의 값을 더한 값이 됩니다.

마찬가지 규칙이 처음 0,0에서부터 시작해 연산해주면 됩니다. 단, 가장 좌측 (i행 0열)과 가장 우측 (i행의 i열)은 내려오는 경로가 한가지만 가능하므로 따로 계산해주어야합니다.

우리가 찾아야할 최댓값은 삼각형의 높이 == i번째 행의 원소중 최댓값입니다. 

def solution(triangle):
    answer = 0
    height = len(triangle)
    dp = [[0 for i in range(height)] for j in range(height)]

    dp[0][0] = triangle[0][0]

    for i in range(1, height):
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
        for j in range(1, i):
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]

    for i in range(height):
        answer = max(answer, dp[height - 1][i])
    
    return answer

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

곱이 양의 정수가 되는 가장 긴 부분수열의 길이를 구하는 문제입니다.

고려해야할 조건은 다음과 같습니다.

1. 중간에 0이 들어가는 경우 어떻게 곱해도 0이 되기 때문에 양의 정수라는 조건을 충족시키지 못합니다. 그래서 부분수열은 0을 기준으로 끊어진 형태가 됩니다.

2. 부분수열 안에 음수가 짝수개 있으면 곱하면서 서로 상쇄되어 곱셈의 결과가 양의 정수가 됩니다.

3. 그럼 음수가 홀수개 있다면 어떨까요? 하나만 빼주면 짝수가 됩니다.

(음수가 1개 있어서 하나를 빼도 0개로 조건을 충족합니다.)

내 위치에서 가장 먼 음수를 빼고 그 다음부터 카운트 하는게 수열의 길이를 길게 만들겁니다.

그리고 내 위치에서 가장 먼 음수는 0 이후에 처음 나온 음수가 될겁니다.

코드로 구현하면 이렇습니다.

class Solution:
    def getMaxLen(self, nums: list) -> int:
        answer = -1
        zeroInedx = -1
        firstNegative = -1
        negativeCount = 0
        
        for i in range(0, len(nums)):
            if(nums[i] == 0):
                firstNegative = -1
                negativeCount = 0
                zeroInedx = i
            
            if(nums[i] < 0):
                negativeCount += 1 
                if(firstNegative == -1):
                    firstNegative = i
            
            if(negativeCount % 2 == 0):
                answer = max(answer, i - zeroInedx)
            else :
                answer = max(answer, i - firstNegative)
        
        return answer
    

input = [[1,-2,-3,4],[0,1,-2,-3,-4],[-1,-2,-3,0,1]]

for i in input:
    print(Solution().getMaxLen(i))

https://leetcode.com/problems/maximum-sum-circular-subarray/

Maximum Subarray를 살짝 비튼 문제입니다.

처음엔 Maximum Subarray를 앞 뒤로 두번 구해서 겹치지 않도록 조각을 붙여가며 탐색할까 생각도 해봤지만 깔끔한 구현방법이 떠오르지 않아서 솔루션을 참고했습니다.

생각지도 못했던 아이디어가 있더라구요.

https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass

자세한 설명은 위 링크에 있는데 핵심 아이디어는 이미지만 봐도 알 수 있으실것 같습니다.

자명하게도 최대합이 되는 부분수열은 두 경우중에 하나일겁니다.

원형으로 이어지지 않거나, 이어지거나.

이어지지 않는 경우는 기존의 Maximum Subarray문제의 풀이와 같습니다.

이어지는 경우는 위 그림처럼 전체 합에서 Minimum Subarray를 뺀 값이 됩니다.

다시 생각해보면 원형으로 이어진 이 Maximum Subarray는 아래의 array의 Maximum Subarray와 같습니다.

(왼쪽 부분을 똑 떼어서 붙였습니다.)

array를 두 부분으로 나누었을 때, 한쪽이 최대합이라면 반대쪽은 최소합이 됩니다.

totalSum - maxSum = minSum / totalSum - minSum = maxSum

만약 더 작은 음수의 다른 minSum이 존재한다면 maxSum도 더 큰 수가 생겨서 수식에 모순이 생기게 됩니다.

array의 모든 수가 양수여서 minSum이 없는 경우에는 배열의 전체 totalSum이 문제의 해답이 되고, 케이스 1에서 찾아낼 수 있습니다.

즉 array의 minSum을 찾아 totalSum에서 뺀다면 원형으로 이어진 maxSum을 알아낼 수 있습니다.

minSum을 찾는 메소드를 따로 작성해도 되지만 기존의 메소드를 이용하되 입력 배열의 부호를 바꿔주면 똑같이 구할 수 있습니다. 다만 모든 수가 음수인 경우(minSum == totalSum)에는 예외가 발생하므로 그 부분만 따로 처리해주시면 됩니다.

class Solution:
    def maxSubarraySumCircular(self, nums: list) -> int:
        nonCircularSum = self.maxSubArray(nums)
        circularSum = sum(nums)
        
        for i in range(0,len(nums)):
            nums[i] = -nums[i]
        
        circularSum += self.maxSubArray(nums)
        
        return max(nonCircularSum,circularSum) if(circularSum != 0) else nonCircularSum
    
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[1,-2,3,-2],[5,-3,5],[-3,-2,-3]]
for i in input:
    print(Solution().maxSubarraySumCircular(i))

https://leetcode.com/problems/maximum-subarray/

연속 부분 수열의 최대합(한국어로 맞는지 모르겠습니다)을 구하는 정말 유명한 DP 문제입니다.

문제를 볼 때마다 매번 10초 정도 LCS와 헷갈립니다. 완전히 다른 알고리즘이라 금방 깨닫긴 하지만, 아마 입력의 형태가 비슷해서 그런것 같습니다. 

저만 그럴수도 있구요.

아이디어는 이렇습니다. 배열 nums가 주어졌다고 할때, 

어떤 위치 i 에서 끝나는 부분수열의 최대합은 두가지 경우입니다.

i-1에서 끝나는 부분수열의 최대합이 양수라서 그 값을 더하거나, 버리고 자기 자신만 취하거나

배열을 만들어서 각 위치마다 해당 위치에서 끝나는 최대합을 기록하며 풀이해도 되는데 이번 문제에선 중간 내용을 활용하지 않기 때문에 그냥 변수에 바로 저장해서 풀이했습니다.

if-else구문을 max(i, sum+i)로 줄이면 코드라인은 줄어들지만 실행시간이 조금 느려집니다.

조건문을 (0 > sum)으로 작성해도 같은 코드입니다.

class Solution:
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[-2,1,-3,4,-1,2,1,-5,4],[1],[5,4,-1,7,8]]
for i in input:
    print(Solution().maxSubArray(i))

https://leetcode.com/problems/jump-game-ii/

점프게임의 시리즈 문제입니다.

1번 문제와 달리 도달할 수 있는지의 가부가 아니라 도달하는 최소의 step을 리턴해야 합니다. (마지막 위치에 도달하는것은 문제에서 보장함.)

처음에는 각 index별로 도달하는 최소의 step을 갱신하는 기본적인 DP의 풀이방법으로 풀었는데, 채점에 통과는 되었지만 실행시간이 좋지 않았습니다.

제공되는 testcase의 내용을 확인해 보니 각 index에서 매 번 목적지에 도달이 가능하다면 1차 제출한 코드는 N^2의 시간복잡도를 갖게 된다는 사실을 알게되었습니다.

(예를 들어 100 길이의 배열에 들어있는 숫자가 99,98,97,96...0 이라면 제 코드는 index를 한 칸 진행할 때마다 뒤의 모든 배열을 순회해야 합니다.)

class Solution:
    def jump(self, nums: list) -> int:
        dp = [20000]*len(nums)
        dp[0] = 0
        
        for i in range(0, len(nums)-1):
            for j in range(i+1, min(len(nums), i + nums[i] + 1)):
                dp[j] = min(dp[i]+1, dp[j])
        return dp[-1]
    

input = [[2,3,1,1,4],[2,3,0,1,4]]

for i in input:
    print(Solution().jump(i))

토론 창의 도움을 얻어 BFS와 유사한, 매 step마다 내가 갈수있는 최대의 범위를 갱신하는 코드를 작성했습니다.

class Solution:
    def jump(self, nums: list) -> int:
        step = 0
        position = 0
        canMove = 0
        
        while(position < len(nums)-1):
            step += 1
            maxMove = 0
            
            while(position <= canMove):
                maxMove = max(maxMove, position+nums[position])
                position += 1
                if(maxMove >= len(nums)-1):
                    return step
                
            canMove = maxMove
        
        return step

input = [[0],[2,3,1,1,4],[2,3,0,1,4]]

for i in input:
    print(Solution().jump(i))

확실히 실행시간이 어마어마하게 차이가 나네요.

https://leetcode.com/problems/jump-game/

배열의 마지막에 도달할 수 있는지 묻는 문제입니다.

저는 거꾸로 배열의 마지막에서 시작해 어떤 위치까지 갈 수 있는지의 여부를 갱신하고 만약 시작점에서도 가능하다면 True를 리턴하는 식으로 풀이했습니다.

class Solution:
    def canJump(self, nums: list) -> bool:
        idx = len(nums)-2
        reach = len(nums)-1
        
        while(idx >= 0):
            if(nums[idx] + idx >= reach):
                reach = idx
            idx -= 1
            
        return reach == 0
    

input = [[2,3,1,1,4],[3,2,1,0,4],[2,0,0]]

for i in input:
    print(Solution().canJump(i))

https://leetcode.com/problems/delete-and-earn/

주어진 조건에서 어떤 숫자를 선택하면 앞 뒤로 붙은 숫자들은 선택할 수 없습니다.

또 어떤 숫자를 선택하면 그 숫자는 계속 선택해도 됩니다.

문제의 설명만 보면 숨겨진 의도를 바로 찾기 힘들지만 생각해 보면 숫자를 연달아 선택할 수 없다는건 이전의 House Robber문제와 같은 유형이란것을 알 수 있습니다.

또 어떤 숫자를 선택하면 그 숫자에 걸린 point는 모두 획득 할 수 있기 때문에 숫자의 범위와 같은 크기의 List로 값을 압축 해 쉽게 구현 할 수 있습니다.

class Solution:
    def deleteAndEarn(self, nums: list) -> int:
        expectValue = [0] * 10001
        for i in nums:
            expectValue[i] += i
        
        dp = [0] * 10001
        dp[1] = expectValue[1]
        for i in range(2,10001):
            dp[i] = max(dp[i-1], dp[i-2]+expectValue[i])
        
        return dp[-1]
    

input = [[3,4,2], [2,2,3,3,3,4]]
for i in input:
    print(Solution().deleteAndEarn(i))

https://leetcode.com/problems/house-robber-ii/

https://nodingco.tistory.com/101?category=570522 

위 문제의 시리즈로 마찬가지로 DP문제입니다.

집들의 위치가 원형으로 연결되어 첫번째 집과 마지막 집이 붙어있는 형태가 되었다는 조건이 추가되었습니다.

아이디어를 떠올리기가 힘들었는데요. 

간단하게 생각하면 첫번째 집과 마지막 집은 동시에 도둑질을 할 수 없습니다.

집들을 의미하는 입력 리스트를 [첫번째 집~마지막 앞의 집]과 [두번째 집~마지막 집]으로 나누어 각각의 최댓값을 1번 문제와 같은 방식으로 구하면 둘 중에 더 큰 값이 정답이 됩니다.

생각해보면, [첫번째 집~마지막 앞의 집]에서 나오는 정답의 경우는 두가지로 생각해 볼 수 있습니다.

1. 첫번째 집을 도둑질 함 -> 이 경우엔 마지막 집은 당연히 털 수 없었습니다. 하지만 마지막 집을 턴 경우의 값이 더 컸을수도 있겠죠? 그 경우는 [두번째 집~마지막 집]으로 나뉜 범위에서 구한 정답이 됩니다.

2. 첫번째 집을 도둑질 하지 않음 - > 이 경우는 [두번째 집~마지막 집]으로 나눈 것에서 얻어낸 정답과 같습니다. (마지막집의 도둑질여부는 관계없습니다.)

[두번째 집~마지막 집]의 경우도 같은 방식으로 생각됩니다.

따라서 두 범위에서 문제를 풀이하면 둘 중 하나는 무조건 정답이 되게 됩니다.

class Solution:
    def rob(self, nums: list) -> int:
        if(len(nums) == 1):
            return nums[0]
        
        return max(self.sliceRob(nums[1:]), self.sliceRob(nums[:-1]))

    def sliceRob(self, nums: list) -> int:
        dp = [0] * (len(nums) + 1)
        dp[0] = 0
        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1],dp[i-2]+ nums[i-1])

        return dp[-1]


input = [[2,3,2],[1,2,3,1],[1,2,3],[1]]
for i in input:
    print(Solution().rob(i))