leetcode 1041(구현), 96(이진트리 dp)

1041 https://leetcode.com/problems/robot-bounded-in-circle/

 

명령어들을 반복했을때 로봇의 이동경로가 서클을 이루는지를 판별하는 문제이다. 오랫만에 푸느라 그런지 어떻게 풀어야 할지 감이 안잡혔는데... discussion을 보니 

1. 명령을 다 실행하고 0,0으로 되돌아오면 서클을 이룸.

2. 또는 명령을 다 실행했는데 이동 방향이 북쪽이 아니면 명령을 반복하면 다시 처음으로 되돌아옴.

 

이라고 한다. 2번을 떠올리려면 직관력이 뛰어놔야 할듯 싶다. 명령이 다 끝났는데도 0,0이 아니고 이동 방향이 북쪽이면 위로만 계속 올라가게되니 아닌거고, 다 끝나고 방향이 왼쪽이면 시계 반대방향으로 돌면서 0,0으로 돌아오고, 오른쪽이면 시계 방향으로 돌면서 0,0으로 오고, 방향이 남쪽이면 명령을 재실행하면 다시 0,0으로 돌아온다.

처음보면 뭔소린지 헷갈릴텐데 그림 그려가면서 보면 이해가 된다..

 

코테용 문제는 아닌듯

class Solution(object):
    def isRobotBounded(self, instructions):
        #instructions = 'GLGLGGLGL'
        x, y = 0, 0
        move_list = [(0, -1, 0, 1), (1, 0, -1, 0)]  # x, y
        move_index = 0
        for each in instructions:
            if each == 'L':
                move_index += 1
                move_index %= 4
            elif each == 'R':
                move_index -= 1
                move_index %= -4
            else:
                
                x, y = x + move_list[0][move_index], y + move_list[1][move_index]
        return (x == 0 and y == 0) or move_index != 0

 

96 https://leetcode.com/problems/unique-binary-search-trees/

 

상당히 좋은 글을 발견해서 번역함. 

https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i)

 

1 ~ n 시퀀스로 이진 탐색 트리(BST)를 만든다고 합시다. 1 ~ n사이에서 하나씩 숫자들을 꺼내와서 i라고 합시다. i를 루트로 삼아서 BST를 만들어보면 1~(i-1)은 트리의 왼쪽 자식에, (i+1)~n은 트리의 오른쪽 자식에 있게 됩니다. 그러면 다시 이 정보를 토대로 왼쪽 자식과 오른쪽 자식으로 재귀적으로(recursively) 들어가면서 subtree를 만들 수 있습니다.

이런식으로 트리를 만들면 모두가 유일한 루트를 가지므로 유일한 트리라고 볼 수 있습니다.

 

유일한 BST의 총 갯수를 구하는게 문제입니다. 두개의 함수를 정의해봅시다.

G(n) : 길이가 n인 유일한 BST의 갯수.

F(i, n), 1 <= i <= n인 i에 대해서 i가 루트인 BST의 갯수.

ex) F(2, 3)은 1~3범위의 숫자를 가진, 루트가 2인 BST의 갯수.

 

결국 G(n)이 문제의 정답이며, G(n)은 F(i, n)함수들을 조합해서 구할 수 있습니다. G(n)은 아래처럼 나타낼 수 있습니다.

G(n) = F(1, n) + F(2, n) + ... F(n, n) 

== 1 ~ n 시퀀스의 모든 유일한 BST의 갯수는 (시퀀스 n중 1이 루트인 경우의 수) + (시퀀스 n중 2가 루트인 경우의 수) + ...(시퀀스 n중 n이 루트인 경우인 수) 입니다.

초기값으로 G(0)과 G(1)은 어차피 하나밖에 없으므로 G(0) = G(1) = 1입니다.

 

1 ~ n 시퀀스에서 숫자 하나를 뽑아 i라고 하고, 루트로 삼으면 유일한 BST는 F(i, n)이고, 이건 왼쪽 자식과 오른쪽 자식의 카티전 곱입니다(cartesian product. 그냥 곱이라고 봐도 무방) 

예로 F(3, 7)은 1 ~ 7 시퀀스에서 루트가 3인 유일한 BST의 갯수이며, 이 BST를 그려보면 [1, 2]가 왼쪽 자식에 있게되고 [4, 5, 6, 7]이 오른쪽 자식에 있게 됩니다.(BST이므로.) 그러면 (왼쪽 자식에서 만들어지는 유일한 BST개수) x (오른쪽 자식에서 만들어지는 유일한 BST개수)의 결과값이 F(3, 7)이 됩니다.

 

근데 (왼쪽 자식에서 만들어지는 유일한 BST개수) 는 G(2)이고, (오른쪽 자식에서 만들어지는 유일한 BST개수)는 G(4)입니다. 결국 F(3, 7) = G(2) * G(4)입니다. 이것을 점화식으로 정리하면 다음과 같습니다.

 

1 <= i <= n인 i에 대해서 F(i, n) = G(i - 1) * G(n - i) 

그런데 맨 처음에 G(n) = F(1, n) + F(2, n) + ... F(n, n) 였으므로 여기에 다시 대입해보면

G(n) = (G(0) * G(n-1)) + (G(1) * G(n-1)) + .... + (G(n-1) * G(0))이 됩니다. 괄호를 제거하면

G(n) = G(0) * G(n-1) + G(1) * G(n-1) + .... + G(n-1) * G(0) 입니다.

 

파이썬 코드로 구현하면 아래처럼 됩니다. 두 코드중 아래 코드가 위 이론과 더 비슷해보이는듯

class Solution(object):
    def numTrees(self, n):
        G = [0] * (n+1)
        G[0] = G[1] = 1
        for i in xrange(2, n+1):
            for j in xrange(1, i+1):
                G[i] += G[j-1] * G[i-j]

        return G[n]
------------------------------------------------
class Solution(object):
    def numTrees(self, n):
        mem = {0: 1, 1: 1}
        def G(n):
            if n in mem:
                return mem[n]

            res = 0
            for i in xrange(1, n + 1):
                res += G(i - 1) * G(n - i)
            mem[n] = res
            return res

        return G(n)