내일은 알고리즘

https://leetcode.com/problems/reverse-linked-list/

LinkedList를 뒤집는 문제입니다.

재귀함수를 이용해 리스트를 타고 끝을 찾은 뒤 끝에서부터 재귀함수를 빠져나오면서 연결 방향을 거꾸로 뒤집었습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if(not head or not head.next):
            return head
        
        rest = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return rest

input = ListNode(1,ListNode(2, ListNode(3,ListNode(4, ListNode(5,None)))))
# input = None

answer = Solution().reverseList(input)
while(answer):
    print(answer.val)
    answer = answer.next

https://leetcode.com/problems/merge-two-sorted-lists/

구현은 어렵지 않지만 LinkedList에 낯설면 접근하기 어려울 수도 있는 문제입니다.

두개의 정렬된 LinkedList가 주어지는데 이 둘을 합쳐 정렬된 하나의 LinkedList를 만들어야 합니다.

결과를 저장하기 위한 새로운 하나의 리스트를 만들고 입력된 두개의 리스트를 비교하면서 작은 순서대로 새로운 리스트에 붙여나갔습니다.

만약 입력 리스트 중에 하나가 끝난다면 결과 리스트의 맨 끝이 남은 입력리스트를 가리키게 하고 리턴했습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        root = ListNode()
        index = root
        
        while(list1 and list2):
            if(list1.val > list2.val):
                index.next = list2
                list2 = list2.next
                index = index.next
            else:
                index.next = list1
                list1 = list1.next
                index = index.next
        
        if(list1):
            index.next = list1
        elif(list2):
            index.next = list2
        
        return root.next
    

input = [[ListNode(1,ListNode(2, ListNode(4,None))),ListNode(1,ListNode(3, ListNode(4,None)))],
         [None,None],
         [None,ListNode(1,ListNode(3, ListNode(4,None)))],
         [ListNode(1,None),None]]

for i in input:
    answer = Solution().mergeTwoLists(i[0],i[1])
    while(answer):
        print(answer.val)
        answer = answer.next

https://leetcode.com/problems/min-cost-climbing-stairs/

계단문제의 변형입니다. 

가장 적은 걸음수로 계단을 오르는 유형과 흡사한 가장 적은 힘을 들이고 계단을 오르는 값을 찾는 문제입니다.

각 계단별로 여기까지 오는데 쓰는 최소한의 힘을 기억시키고 규칙에 따라 하나씩 최솟값을 채워가며 구현했습니다.

class Solution:
    def minCostClimbingStairs(self, cost: list) -> int:
        size = len(cost) + 1
        dp = [0] * size

        for i in range(2,size):
            dp[i] = min((dp[i-1] + cost[i-1]),(dp[i-2] + cost[i-2]))

        return dp[-1]



input = [[10,15,20],[1,100,1,1,1,100,1,1,100,1]]

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

https://leetcode.com/problems/climbing-stairs/

DP의 또다른 대표 문제인 계단 문제입니다.

이 기본 유형에서는 피보나치와 코드가 거의 같다고 보셔도 될 것 같습니다.

계단을 오르는 갯수, 지뢰, 내려가기 등을 섞어 여러 유형으로 활용되는 문제입니다.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-2] + dp[i-1]
        return dp[n]


for i in range(1,46):
    print(Solution().climbStairs(i))

https://leetcode.com/problems/n-th-tribonacci-number/

피보나치 문제와 99.9% 똑같지만 점화식이 이전의 세 수를 더한다는 차이점이 있습니다.

그러니 이름이 트리보나치겠죠? 간단하게 풀이했습니다.

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0] * (38)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1

        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        return dp[n]

for i in range(0,26):
    print(Solution().tribonacci(i))

https://leetcode.com/problems/fibonacci-number/

정말 유명한 피보나치 DP문제입니다.

매번 피보나치 수를 새로 계산하지 않고 이전의 결과값을 사용해 계산하면 됩니다.

Memoization의 개념과 필요성을 한방에 이해시키는 좋은 문제라고 생각합니다.

class Solution:
    def fib(self, n: int) -> int:
        dp = [0] * (31)
        dp[0] = 0
        dp[1] = 1

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

        return dp[n]

for i in range(0,31):
    print(Solution().fib(i))

https://leetcode.com/problems/is-subsequence/

Subsequence는 어떤 String에서 임의의 문자들을 삭제했을때 만들어지는 String이라고 합니다.

s가 t의 Subsequence인지 묻는 문제입니다.

문제 자체는 그리디한 느낌으로 s의 문자들을 차례대로 t에서 찾으면 해결됩니다.

다만 제 풀이코드 기준에서 s와 t의 길이에 따라 index가 범위를 넘어가는 경우가 있어서 예외처리해 주었습니다.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if(len(s) > len(t)):
            return False
        if(len(s) == 0):
            return True

        idx = 0
        for i in t:
            if(i == s[idx]):
                idx += 1
            if(len(s) == idx):
                return True
        return False

input = [["abc", "ahbgdc"],["axc", "ahbgdc"]]

for i in input:
    print(Solution().isSubsequence(i[0],i[1]))

https://leetcode.com/problems/isomorphic-strings/

상당히 낯선 단어인데 Isomorphic은 동형사상이라는 뜻이라고 합니다.

Isomorphic String은 두 String의 형태가 닮아있는 것을 말하는데요. 예를 들어 glass와 shell이 동형관계입니다.

두 단어는 생김새가 전혀 다르지만 알파벳이 등장하는 순서대로 번호를 매기면 12344, 12344로 구조가 같음을 알 수 있습니다.

반대로 banana와 canada는 단어 생긴건 비슷하지만 번호를 매기면 123232와 123242로 차이가 있습니다.

문제에서 주어진 String을 앞에서부터 읽어가며 처음 만나는 알파벳인 경우 Dictionary에 Index값을 넣어주고, 이미 만났던 알파벳인 경우 Index값을 비교해 같은 구조인지 체크해줬습니다.

물론 알파벳의 내용은 다르므로 Dictionary를 두개 만들어서 따로 저장했습니다.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sDict = {}
        tDict = {}
        idx = 0

        for i in range(0,len(s)):
            if(not (s[i] in sDict) and not (t[i] in tDict)):
                sDict[s[i]] = idx
                tDict[t[i]] = idx
                idx += 1
            elif(s[i] in sDict and t[i] in tDict):
                if(sDict[s[i]] != tDict[t[i]]):
                    return False
            else: 
                return False
        
        return True

input = [["egg","add"],["foo","bar"],["paper","title"]]

for i in input:
    print(Solution().isIsomorphic(i[0],i[1]))