👨💻📱✍️🎢314 BOJ 2869 - 달팽이는 올라가고 싶다 문제 백준 온라인 저지 - 2869번 풀이 과정 처음에는 해당 문제가 왜 이분 탐색 문제집에 포함되어 있는지 의문이었습니다. 수학적으로 해결할 수도 있을 것 같지만 이분 탐색 으로 해결할 수 있는 방법을 찾고 싶이서 다른 방식으로 접근했습니다. 달팽이는 매일 A 만큼 올라갑니다. 달팽이가 끝에 도달하기 위해서는 마지막 이동 전 위치가 V - A 보다 크거나 같으면 됩니다. 따라서 날짜 * (A - B) >= V - A 가 되는 최소 날짜를 이분 탐색 으로 찾으면 됩니다. 코드 import sys def solution(): move_offset = A - B lo, hi = 0, 1000000000 day = 2e9 while lo = V - A: day = min(day, mid) hi = mid - .. 2021. 4. 13. BOJ 16926 - 배열 돌리기 1 문제 백준 온라인 저지 - 16926번 풀이 과정 배열을 회전하는 로직을 구현하는 문제입니다. python 으로 제출하니 시간초과가 발생하여 pypy3 로 제출했습니다. 코드 import sys def rotate(): x, y = 0, 0 n, m = N, M time = min(N, M) // 2 while time: cache = board[x][y] # 윗쪽 for i in range(m - 1): board[x][y + i] = board[x][y + i + 1] # 오른쪽 for i in range(n - 1): board[x + i][y + m - 1] = board[x + i + 1][y + m - 1] # 아래쪽 for i in range(m - 1): board[x + n - 1][y .. 2021. 4. 13. LeetCode 36 - Valid Sudoku (Medium) 문제 LeetCode - 36번 풀이 과정 스도쿠 를 구현하는 문제입니다. 대신 모든 로직을 구현하는 것은 아니고 채워진 숫자들에 대해서 스도쿠 조건을 만족하는지 판단하는 문제입니다. 먼저 3x3 크기의 서브 박스들에서 19 사이의 숫자들 중 중복이 존재하는지 검사합니다. 이후 각 행과 열을 순회하며 마찬가지로 19 사이의 숫자 중복성을 검사합니다. 코드 /** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function (board) { const isSubboxRepetition = checkSubboxes(board); if (!isSubboxRepetition) { return false; } for (let .. 2021. 4. 13. 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. 이전 1 ··· 21 22 23 24 25 26 27 ··· 53 다음