개발자가 되고 싶은 준개발자

문제 트리가 주어졌을 때, 트리가 Binary Search Tree인지 판별하라 코드 (Naive 버전) 트리가 BST인지를 판별하기 위해서는 1) 왼쪽 subtree, 오른쪽 subtree가 BST여야 하며, 2) root의 왼쪽 subtree에 있는 값들은 root보다 모두 작아야 하며, root의 오른쪽 subtree에 있는 값들은 root보다 모두 커야 한다. (재귀적으로 바닥까지 모든 subtree가) 따라서 직관적으로 tree를 모두 traverse하면서 이를 확인하는 코드를 짰다. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = No..

문제 m*n의 그리드에서 좌측 위 코너에서 우측 아래 코너까지 가는 각기 다른 경로의 개수를 리턴해라. 풀이 그리드의 크기와 같은 테이블을 그리고 각 칸마다 그 칸으로 가는 경로의 총 개수를 기입하면 된다. 이 문제를 동적 프로그래밍으로 풀수 있는 이유는 작은 문제를 풀면 이를 이용하여 큰 문제를 풀 수 있기 때문이다. 문제에는 아래나 오른쪽으로 밖에 가지 못한다는 제약 사항이 있기 때문에, 특정 칸까지 가는 경로의 수는 위의 칸까지 가는 경로의 수와 왼쪽 칸까지 가능 경로의 수의 합과 같다. (어렸을 때 눈높이 학습지를 많이 풀어서 그런지 이 문제가 너무 익숙하다 ㅋㅋㅋ) 코드 class Solution(object): def uniquePaths(self, m, n): """ :type m: int ..

동적 프로그래밍 카테고리에 있는 문제로 가장 긴 앞뒤가 같은 문자열을 찾는 문제이다. 풀이 동적 프로그래밍으로 문제를 풀기 위해서는 계산한 결과를 저장하여 다음에 '재사용'하여야 한다. Palindrome은 앞뒤가 같은 문자열로, 전체가 palindrome이면 부분도 palindrome이다. "abcba"로 예를 들어보자. "abcba"가 palindrome이면, "bcb", "c"도 모두 palindrome이다. 따라서 작은 문제부터 풀고, 큰 문제는 +𝛂만 추가로 확인하면 된다. 우선 가장 가운데의 "c"가 palindrome인지 확인하고, 맞다면 그 양 옆의 문자인 "b"를 추가로 확인한다. 양 옆의 문자가 같다면, 이 또한 palindrome이다. 그러면 다시 그 양 옆의 문자를 확인하는 식으로 ..