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

문제 레벨 별로 다른 순서(왼쪽->오른쪽, 오른쪽->왼쪽)로 이진 트리(Binary Tree)를 순회하라. 풀이 쉬울 줄 알았는데 생각보다 통과하기가 어려웠다. 기본적인 알고리즘은 이전 포스트인 이진 트리를 BFS(너비 우선 탐색) 방식으로 레벨별로 순회하는 알고리즘과 비슷하다. (june-coder.tistory.com/16?category=913762) [LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드 문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순� june-coder.tistory.c..

문제 왼쪽 상단 코너에서 오른쪽 하단 코너까지 각 칸에 적힌 수의 합이 최소인 경로를 구해라. 풀이 이 문제를 푸는 데 중요한 포인트는 특정 칸까지의 최소인 경로는 하나만 구하면 된다는 점이다. 그 경로가 어떤 경로인지는 중요하지 않고, 수의 합이 최소라는 점만 중요하다. 따라서 최소의 합을 내는 경로를 구했다면 그 최소의 합만 저장하고, 경로는 저장할 필요가 없다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 적합하다. 각 칸까지의 경로의 최소 합을 저장하고, 다음 칸의 값을 구할 때 이전 값들을 사용하면 된다. 즉, dp[i][j] = min(dp[i-1][j], dp[i][j-1])+ grid[i][j]. (물론, 예외처리는 해주어야 한다.) 코드 class Solution(object): def ..

문제 이전 글에서 푼 Unique Paths(https://june-coder.tistory.com/5?category=913762)에 약간의 제약사항이 추가된 문제이다. 이전에는 시작점에서 도착점까지 가능한 경로의 개수를 구하면 되었지만, 이번 문제에서는 지도에 방해물이 추가된다. 따라서 방해물을 지나지 않는 경로의 개수를 세어야 한다. 풀이 문제 자체는 평이했다. 이전 문제를 푼 방법대로, 특정 지점의 윗 칸과 왼쪽 칸의 경로의 개수를 합하면 된다. 이 문제에서는 방해물이 있기 때문에 왼쪽이나 위에 방해물이 있으면 해당 경로로는 오지 못하는 것을 의미하기 때문에 그 경로를 제외한 나머지 경로를 구하면 된다. 그러나 약간 어려웠던 부분은 예외 처리이다. 만약 [[1]]와 같은 입력이 들어온다면 답은 무..

문제 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이다. 그러면 다시 그 양 옆의 문자를 확인하는 식으로 ..

문제 list_of_list = [[0]*5]*5 위처럼 리스트의 리스트를 생성하면 [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]가 만들어진다. 여기까지는 좋다. 그런데 리스트의 일부분을 수정하면 어떻게 될까? for i in range(5): list_of_list[0][i] = 1 위의 코드를 이어 실행하면, list_of_list가 [[1,1,1,1,1], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]이 되어야 할 것 같다. 그런데 실제로는 [[1,1,1,1,1], [1,1,1,1,1], [1,1,1,1,1], [1,1,1,1,1], [1,1,1,1,1]]이 된다. (띠용? 당황스럽..