Python – Jacob's Software Engineering Blog

Algorithm 문제 : Jump Game

문제 출처 : https://leetcode.com/problems/jump-game/description/

이번 문제는 음이 아닌 정수들의 array가 주어졌을 때, index 0부터 시작해서 해당 index의 값만큼 오른쪽으로 jump할 수 있습니다. 그렇게 해서 array의 끝까지 jump할 수 있는지의 여부를 리턴하는 함수를 짜는 것이 문제입니다.

예를 들면, A = [2,3,1,1,4]가 주어졌을 때, 처음에서 점프할 수 있는 한도는 2이므로, 2만큼 점프해도 되고, 1만큼 점프해도 됩니다. 2만큼 점프했을 때는 3번째 원소로 가고, 거기서 다시 1만큼 점프해서 4번째 원소로 가고, 거기서 다시 1만큼 점프해서 마지막 원소로 갈 수 있습니다. 또한 맨 처음에서 1만큼 점프할 경우 두번째 원소로 가게 되고, 그 값이 3이므로 3칸까지 오른쪽으로 갈 수 있습니다. 이 때도 마찬가지로 마지막 원소까지 갈 수 있습니다. 따라서 이 경우엔 true를 리턴합니다.

반면, A = [3,2,1,0,4]이라면, 첫 원소에서 3칸까지 점프할 수 있는데, 3칸을 뛰면 거기에 있는 원소가 0이므로 더 점프할 수 없게 되고 마지막 원소로 도달할 수 없습니다. 2칸을 점프하면 1이 나오는데, 1칸 더 뛰어서 다시 0이 나오므로 마찬가지로 도달할 수 없습니다. 1칸을 점프하면 2가 나오는데, 거기서 2칸을 뛰건 1칸을 뛰건 무조건 0을 만나게 되므로 이 경우에도 마지막까지 도달할 수 없게 됩니다. 따라서 이 경우엔 결코 마지막 원소까지 점프할 수 없게됩니다! 따라서 false를 리턴합니다.

일단 Brute force하게는 index 0에서 해당 원소만큼 모든 가능한 점프들을 해보고 그 다음 도착한 칸에서 또 가능한 모든 점프들을 해보는 식으로 구할 수 있습니다. 하지만 이는 굉장히 비효율적인 답안 찾기가 됩니다.

따라서 좀 더 효율적인 방법을 써야 하는데, 이 경우에 있어서는 greedy 알고리즘이 매우 효율적입니다.

Greedy 알고리즘의 로직은 다음과 같습니다.

1. 맨 마지막에서 두번째 index부터 0번째 index까지 오면서 조사를 시작합니다.
2. 만약 nums[i]+i가 마지막 index보다 크거나 같으면, left_most_good_index를 i로 세팅합니다.
3. 그 후, nums[i]+i가 left_most_good_index보다 큰 경우, 계속하여 left_most_good_index를 i로 세팅합니다.

이런 식으로 맨 첫번째 index까지 왔을 때, left_most_good_index가 0인지 아닌지만 리턴하면 됩니다. 이렇게 되면 complexity는 $O(n)$ 이 될 것이고, memory도 그냥 variable 1개만 유지하기 때문에 $O(1)$ 의 훌륭한 optimized code가 완성됩니다! 🙂

	def canJump(self, nums):
	"""
	:type nums: List[int]
	:rtype: bool
	"""
	if len(nums) == 1:
	return True

	left_most_good_index = None

	for i in xrange(len(nums)-2, -1, -1):
	if nums[i] + i >= len(nums)-1:
	left_most_good_index = i
	if left_most_good_index and nums[i] + i >= left_most_good_index:
	left_most_good_index = i

	return left_most_good_index == 0

view raw jump_game.py hosted with ❤ by GitHub

Algorithm, Python

Algorithm 문제 : Find Duplicate Subtrees

문제 출처 : https://leetcode.com/problems/find-duplicate-subtrees/description/

이번 문제는, binary tree가 주어졌을 때, 가능한 모든 중복되는 subtree를 리턴하는 문제입니다. 단, 리턴할 때 해당 subtree의 root node만 리턴하면 됩니다.
중복된다는 의미는 두 tree가 동일한 구조를 갖고 각 노드가 동일한 값을 갖는 것을 의미합니다.

예를 들면,

이런 트리가 있으면, 이 구조에선 두 개의 duplicate subtree를 발견할 수 있습니다.

      2
     /       와      4
    4

이 때 정답은 각 duplicate subtree의 root인 2와 4의 노드만 리턴하면 됩니다.

이 문제를 접근하는 첫번째 방법은 tree를 serialize해서 해당 serial이 두번 이상 등장했는지 체크하는 방법입니다. 아래의 코드를 보시겠습니다.

def findDuplicateSubtrees(root):
    """
    :type root: TreeNode
    :rtype: List[TreeNode]
    """

    # 각 serial이 몇번 등장하는지를 기록할 dictionary입니다.
    counter = {}
    
    # 최종적으로 duplicate subtree의 정보를 가지고 있을 리스트입니다.
    result = []

    def serializeTree(node):
        # 해당 노드가 None이면 '#'으로 serialize합니다.
        # 이를 통해 자식 노드가 없으면 없다는 걸 확실히 표현할 수 있습니다.
        if node is None:
            return "#"
        
        # 본인의 값과 각 좌우 자식에서 만들어진 serial을 가져와 붙여서 새로운 serial을 만듭니다.
        serial = "{},{},{}".format(node.val, serializeTree(node.left), serializeTree(node.right))
        
        # counter에 해당 serial의 등장 횟수를 증가시킨 후,
        # 2번 이상이면 바로 최종 결과에 append 시켜줍니다.
        counter[serial] = counter.get(serial, 0) + 1
        if counter[serial] == 2:
            result.append(node)
            
        return serial

    serializeTree(root)
    return result

이렇게 되면 각 노드를 한번씩 방문하게 되고, 그 한번 방문때마다 자녀들의 serial들을 붙여야 하기 때문에 $O(N)$ 이 소요되므로 결국 $O(N^2)$ 의 complexity를 갖습니다.

그렇다면 사실 문제가 되는 부분은 자녀들의 serial을 붙이는 부분입니다. 이것이 root와 가까워질수록 붙여야 하는 길이가 길어지기 때문에 이런 사태가 벌어지는 것입니다. 따라서 우리가 각 노드마다 어떻게 생겼는지에 따라 unique한 id를 부여하면 어떨까요? 그리하여 일일이 긴 serial을 가지고 다니는 대신에 (node.val, left_child's id, right_child's id) 이렇게 간단하게 쿼리할 수 있게 말입니다. 이렇게 되면 불필요한 $O(N)$ 이 사라지므로 각 노드를 방문할 때 소요되는 $O(N)$ 의 complexity만 가질 수 있게 됩니다!

def findDuplicateSubtrees(self, root):
    # 종전과 다른 것은 고유한 tree를 저장하기 위한 데이터 구조가 새로 필요합니다.
    trees = {}
    
    count = {}
    ans = []

    def lookup(node):
        if node:
            # 왼쪽 자식의 고유 id를 가져옵니다.
            left_id = lookup(node.left)
            # 오른쪽 자식의 고유 id를 가져옵니다.
            right_id = lookup(node.right)
            
            # (자신의 값, 왼쪽 자식 고유 id, 오른쪽 자식 고유 id)로 key를 만들어서
            # 그것이 고유한 tree에 있으면 해당 id를 받아오고,
            # 기존에 없던 tree이면 unique한 번호를 부여합니다.
            if (node.val, left_id, right_id) not in trees:
                trees[(node.val, left_id, right_id)] = len(trees)
            uid = trees[(node.val, left_id, right_id)]

            # 나머지 로직은 똑같습니다. uid가 두번 이상 출현하면 최종 결과에 추가해줍니다.
            count[uid] = count.get(uid, 0) + 1
            if count[uid] == 2:
                ans.append(node)

            print uid
            return uid

    lookup(root)
    return ans

Algorithm, Python

Algorithm 문제 : Palindrome Partitioning

문제 출처 : https://leetcode.com/problems/palindrome-partitioning/description/

이번 문제는 문자열 s가 주어졌을 때, 문자열을 나눈 partition을 찾는데, 그 partition의 각 substring이 모두 palindrome인 것을 모조리 찾아내는 문제입니다.

예를 들면, "aab"가 주어졌다고 할 때,

[
  ["aa","b"],
  ["a","a","b"]
]

를 리턴해야 합니다. “aa”와 “b”로 쪼개면 “aa”도 palindrome이고 “b”도 palindrome이기 때문에 가능한 partition입니다. 마찬가지로 한글자씩 쪼개면 무조건 가능한 경우가 되겠지요.

이렇게 무언가 부분집합을 몽땅 구해봐야할 때 가장 먼저 생각나야 하는 방법이 backtracking입니다!
일단 로직은, chunk 사이즈를 1부터 늘려가면서 잘라내고 그 chunk가 palindrome이면 나머지 문자열을 다시 재귀함수로 호출합니다. 그리고 해당 chunk로 가능한 모든 partition을 점검하고 나면 기존 chunk를 제거하고 새로운 chunk로 조사를 시작하는 식으로 진행합니다.

코드를 보면서 얘기하면 더 이해가 되시리라 생각됩니다.
가장 먼저, 주어진 문자열이 palindrome인지 아닌지를 조사해야겠습니다.

def isPalindrome(s):
    # 길이가 1인 문자열은 무조건 palindrome입니다.
    if len(s) == 1:
        return True

    # 길이가 짝수인 문자열은 전반부의 문자열과 후반부의 문자열을 뒤집은 문자열과 같아야 합니다.
    elif len(s) % 2 == 0:
        return s[:len(s)/2] == s[len(s)-1:len(s)/2-1:-1]
    
    # 길이가 홀수인 문자열은 정 가운데 글자를 사이에 두고 전반부 문자열과, 뒤집은 후반부 문자열이 같아야 합니다.
    else:
        return s[:len(s)/2] == s[len(s)-1:len(s)/2:-1]

이제 이 함수를 가지고 backtracking 함수를 구현해 보도록 하겠습니다.

def backtrack(s, index, result, current):
    # 재귀 함수의 종료 조건은, 문자열 끝까지 검색을 마친 경우입니다.
    # 그런데 만약 리스트가 비어있으면,(가능한 경우가 없으면) 굳이 결과에 넣어주지 않습니다.
    # 주의하실 점은 반드시 current를 복사해서 넣어주셔야 한다는 점입니다.
    # 그렇지 않으면 backtracking에 의해 current가 변경되기 때문에 결과가 맞지 않아집니다.
    if index >= len(s) and len(current) > 0:
        result.append(current[:])
    else:
        # Chunk는 길이 1부터 시작합니다.
        window = 1
        # 1부터 가능한 모든 길이의 chunk들을 조사합니다.
        while window <= len(s)-index:
            sample = s[index:index+window]
            # 해당 chunk가 palindrome이면,
            # chunk를 넣고 나머지 문자열을 index+window부터 조사 시작합니다.
            if isPalindrome(sample):
                current.append(sample)
                backtrack(s, index+window, result, current)
                # 끝나고 backtrack을 위해 빼줍니다.
                current.pop()
            window += 1

최종적으로 아래와 같이 호출하여 사용합니다.

result = []
backtrack(s, 0, result, [])
return result