본문 바로가기

Algorithm202

LeetCode 120 - Triangle (Medium) 문제 LeetCode - 120번 풀이 과정 첫번째 행에서 마지막 행까지 도달하기 위한 거리의 최소 합을 구하는 문제입니다. dp(row, idx) = row 행의 idx 열에서 마지막 행에 도달하기 위한 최소 거리 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[row][idx] = min(dp[row + 1][idx], dp[row + 1][idx + 1]) + triangle[row][idx] 코드 /** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function (triangle) { const INF = 9999999; const rowLimit = triangle.length; const mem.. 2021. 4. 13.
LeetCode 38 - Count and Say (Medium) 문제 LeetCode - 38번 풀이 과정 주어진 규칙대로 문자열 처리를 구현하는 문제입니다. 연속된 숫자들의 개수를 세어주기 위해 임시 변수를 사용했습니다. 코드 /** * @param {number} n * @return {string} */ var countAndSay = function (n) { let str = "1"; for (let i = 1; i < n; i += 1) { let cacheKey = ""; let count = 0; let temp = ""; for (let ch of str) { if (cacheKey !== ch) { if (cacheKey) { temp += `${count}${cacheKey}`; } cacheKey = ch; count = 1; } else { c.. 2021. 4. 13.
LeetCode 199 - Binary Tree Right Side View (Medium) 문제 LeetCode - 199번 풀이 과정 이진 트리를 오른쪽에서 봤을 때 보이는 노드들을 높이순으로 출력하는 문제입니다. 이를 위해서 방문 시 이전까지 방문한 트리 높이 추적을 위해 isVisitedLevel 이라는 배열을 유지하며 방문을 오른쪽 자식 -> 왼쪽 자식 순으로 하되 이전에 방문하지 않은 레벨일 경우에만 배열에 push 해줍니다. 코드 /** * 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===undefin.. 2021. 4. 5.
LeetCode 344 - Reverse String (Easy) 문제 LeetCode - 344번 풀이 과정 in place 한 방법으로 배열을 뒤집는 연산을 수행하는 문제입니다. 왼쪽 끝 과 오른쪽 끝 을 가리키는 두 개의 포인터를 활용해서 뒤집기 연산을 수행하면 됩니다. 코드 /** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString = function (s) { let lo = 0; let hi = s.length - 1; while (lo < hi) { [s[hi], s[lo]] = [s[lo], s[hi]]; lo += 1; hi -= 1; } return s; }; 2021. 4. 5.
BOJ 15732 - 도토리 숨기기 문제 백준 온라인 저지 - 15732번 풀이 과정 일정한 간격으로 도토리가 놓여있다고 했을 때 특정 순서의 도토리가 들어있는 상자의 위치를 찾는 문제입니다. 만약 주어진 규칙들을 모두 수행해보고 도토리의 위치를 찾는 브루트 포스 를 수행한다면 최악의 경우 O(NK) 이기 때문에 시간 초과가 발생합니다. 대신에 상한과 하한을 설정한 뒤 이분 탐색 을 활용해서 마지막 도토리가 있는 상자의 위치를 찾도록 하겠습니다. 각각의 위치에서 해당 지점이 마지막 도토리라는 사실을 어떻게 판단할 수 있을까요? 이는 바로 각 규칙을 모두 순회하면서 특정 지점 x 보다 앞에 있는 도토리의 개수를 세어주면 됩니다. 각 규칙의 시작 위치를 init , 간격을 step , 기준 지점을 x 라고 한다면 다음과 같은 부등식이 성립합니.. 2021. 3. 18.
BOJ 2178 - 미로 탐색 문제 백준 온라인 저지 - 2178번 풀이 과정 시작 지점에서 (N, M) 의 목표 지점에 도달하기 위한 최단 경로를 계산하는 BFS 문제입니다. 별다른 추가 조건 없이 기본적인 BFS 알고리즘을 구현해주면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(x, y): q = deque() visit = [[0]*M for _ in range(N)] q.append(.. 2021. 3. 18.

티스토리툴바