Algorithm202 LeetCode 226 - Invert Binary Tree (Easy) 문제 LeetCode - 226번 풀이 과정 주어진 이진 트리를 뒤집는 연산을 수행하는 문제입니다. 다른분들의 풀이법을 보니 level order traversal 을 사용하신 분들도 있었지만 저는 dfs 를 사용했습니다. 각 서브트리의 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 invert 해준 다음 해당 서브트리의 루트노드를 반환해줍니다. 이러한 재귀 호출을 반복하면 최종적으로 기존의 root 는 invert 된 트리가 됩니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===.. 2021. 3. 3. LeetCode 406 - Queue Reconstruction by Height (Medium) 문제 LeetCode - 406번 풀이 과정 각 사람들의 키 h 와 자신보다 앞에 서있는 사람들 중 자신보다 키가 큰 사람들의 수 n 이 주어질 때 조건에 맞도록 사람들을 나열하는 방법을 찾는 문제입니다. 따라서 우선 n 의 오름차순으로 정렬하며 n 이 같을 경우에는 h 가 증가하는 순으로 정렬합니다. 그리고 정렬된 사람들을 한명씩 자신의 위치를 찾아 삽입해주는 방식으로 진행합니다. 이때 n 을 만족시키면서 최대한 뒤에 위치하도록 설정해주도록 하는 탐욕적 선택 을 활용합니다. 코드 /** * @param {number[][]} people * @return {number[][]} */ var reconstructQueue = function (people) { const answer = []; peopl.. 2021. 3. 3. BOJ 1105 - 팔 문제 백준 온라인 저지 - 1105번 풀이 과정 L 과 R 이 주어질 때 해당 두 수 사이에 존재하는 모든 수들 중에서 8 의 개수가 가장 작은 경우를 찾는 문제입니다. 여기서 알아야할 점은 두 수의 자리수가 다를 경우 무조건 8 의 개수가 0인 경우가 존재한다는 것입니다. 예를 들어 100, 1000, 10000 ... 등이 있습니다. 또한 L 은 R 보다 같거나 크다는 전제가 있기 때문에 각 자리수를 비교했을 때 R 의 특정 자리수에서 L 보다 커지는 위치가 존재합니다. (만약 두 수가 같다면 존재하지 않습니다.) 해당 자리수 이후의 숫자들은 탐색할 필요가 없는데 이는 이후의 숫자들을 모두 0으로 하면 8이 등장하지 않는 경우를 만들 수 있기 때문입니다. 따라서 숫자의 가장 앞 자리부터 탐색을 수행하.. 2021. 3. 3. BOJ 16509 - 장군 문제 백준 온라인 저지 - 16509번 풀이 과정 상 이 움직일 수 있는 방법을 고려하여 왕 에게 도달 가능한 최소시간을 구하는 문제입니다. 문제에 제시된 방법으로 상 을 BFS 를 이용해 최소시간을 구할 수 있으며 이때 주의할 점은 상의 이동 경로가 격자를 벗어나거나 다른 물체가 있으면 안된다는 것입니다. 따라서 경로상의 모든 지점을 확인하는 check_path 함수를 구현하고 만약 통과할 경우에만 해당 지점으로 탐색을 이어가는 방법으로 구현했습니다. 코드 import sys from collections import deque sang = list(map(int, sys.stdin.readline().split())) king = list(map(int, sys.stdin.readline().spli.. 2021. 3. 3. LeetCode 54 - Spiral Matrix (Medium) 문제 LeetCode - 54번 풀이 과정 2차원 배열 을 이용한 구현 문제입니다. 배열의 움직임에서 규칙을 찾아 화전하는 시뮬레이션을 할 수도 있지만 좀 더 간단한 방법으로 DFS 를 활용하여 모든 위치를 탐색할 수 있습니다. 시작지점 (0, 0) 에서부터 오른쪽, 아래쪽, 왼쪽, 위쪽 순서대로 방향을 틀어가며 탐색합니다. 이때 방향을 전환하는 시점은 배열을 벗어나거나 이미 방문한 지점을 다시 방문하려고 할 때입니다. 이를 활용하면 다음과 같은 코드로 원하는 연산을 수행할 수 있습니다. 코드 /** * @param {number[][]} matrix * @return {number[]} */ var spiralOrder = function (matrix) { const m = matrix.length;.. 2021. 3. 3. LeetCode 94 - Binary Tree Inorder Traversal (Medium) 문제 LeetCode - 94번 풀이 과정 이진 검색 트리의 중위 순회 를 구현하는 문제입니다. 재귀 호출 을 이용해서 왼쪽 서브트리, 서브 루트, 오른쪽 서브트리 순서로 방문해주면 됩니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var inord.. 2021. 3. 3. 이전 1 ··· 24 25 26 27 28 29 30 ··· 34 다음
