본문 바로가기

전체 글115

[토비의 스프링] 오브젝트와 의존관계 보호되어 있는 글 입니다. 2021. 7. 23.
차원에 대한 오랜 생각 물론 수학적 물리적으로는 이미 어떠한 정답이 있겠지만, 답을 찾고자 하기보다 그냥 사색을 목적으로 가끔 차원에 대해 생각할 때가 있다. 0차원은 점, 1차원은 선, 2차원은 면, 3차원은 공간. 각 차원에서 x축, y축, z축을 더하면 다음 차원이 된다. 4차원, 5차원은 뭘까, 가끔씩 생각해보곤 했다. n차원이 수없이 많이 모이면 n+1차원이 된다. n차원에서는 n+1차원을 시각적으로 표현할 수 없다. xyz축 다음은 시간축이라고 한다. 그러므로 4번째 축은 시공간이 될 것이다. 4차원 시공간을 우리가 사는 3차원 세계에 시각적으로 그릴 수는 없다. 그렇다면 가장 가까운 것은 무엇일까? 어릴 땐 시공간을 마음대로 넘나들 수 있는, 뇌 속의 기억이 아닐까 생각했다. 형태를 알 수 없고, 시공간을 제약없이.. 2021. 6. 22.
[LeetCode] Minimum Path Sum (javascript) 좌상단에서 출발하여 우하단까지 오른쪽, 아래로만 움직여 도착해야 한다. 가는 경로의 숫자를 모두 더했을때, 가장 작은 숫자를 구하는 문제다. 최단경로 경우의 수 문제와 유사하게 풀 수 있다. 처음엔 모든 경로를 처음부터 더해가면서 최솟값을 구해보려고 했으나.. (첫번째 경로 결과 : 10, 두번째 경로 결과 : 8 ...) Time Limit에 걸렸다. 이미 구해놓은 결과값보다 큰 경우 패스하도록 해도 마찬가지... 더보기 틀린 풀이 // 잘못된 접근방식(Time Limit) var minPathSum = function (grid) { let result = Infinity; const ml = grid.length - 1; const nl = grid[0].length -1; console.log(m.. 2021. 6. 22.
[LeetCode] Merge Intervals (javascript) 주어진 2차배열 내의 요소들끼리 겹치는 것을 합쳐주는 문제다. 예를들어 [[1, 3], [2, 4], [5, 8]] 이 있다고 하면 이렇게 [[1, 4], [5, 8]]로 겹치는 요소는 합쳐주는 것이다. 여기서 각 요소의 첫 번째 요소([1, 4]의 1)를 head, 두 번째 요소([1, 4]의 4)를 tail이라고 부르겠다. 그래서 배열을 차례대로 돌면서, 현재 요소와 다음 요소가 겹치는 부분이 있으면 합치는 방식으로 풀었다. 어렵지 않게 풀리는듯 했으나 간과했던 포인트가 있었는데, 1. 주어진 배열들은 소팅되어 있지 않다. 즉, 차례대로 합치다간 나중에 제외되는 요소가 나타난다. ex. [[1, 3], [2, 4], [5, 8], [2, 3]] => [[1, 4], [5, 8]]이 되어야 하나 [[1.. 2021. 6. 15.
[LeetCode] Unique Paths, Unique Paths II (javascript) Unique Path 전형적인 최단경로 찾기 조합 문제! (m + n)! / m! * n! 식을 이용하여 풀었다. /** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { // (m+n-2)! / ((m-1)! * (n-1)!) console.log(factorial(m+n-2), factorial(m-1), factorial(n-1)) return factorial(m+n-2)/(factorial(m-1)*factorial(n-1)); }; const factorial = (n) => { if(n == 0) return 1; let num = n; for (let i = num -.. 2021. 6. 15.
[LeetCode] Longest Substring Without Repeating Characters (javascript) 가장 긴 반복되지 않는 문자열의 길이를 리턴하는 문제다. 예를들어 abcdaddd => [abcd][ad][d][d] = 4 abcabc => [abc][abc] = 3 처음엔 문자별로 for문을 돌면서 다음에 출현하는 같은 문자까지의 index 차이를 구하려고 했다. abcabc => [abc] "a"bc => 3 다만 이런경우... abbabc => [abb] "a"bc => 3 이런 케이스를 피할 수 없고, 또 abb안에서 중복이 없는지 검사하는 등 복잡해지게 된다. 다른 풀이들을 참고한 결과, substring해가면서 중복이 없으면 결과값에 더해주고, 중복이 있으면 앞글자를 방출하는 형태가 가장 이해하기도 편하고 코드도 깔끔해 보여서 이렇게 구현했다. /** * @param {string} s *.. 2021. 6. 15.
[LeetCode] Longest Substring Without Repeating Characters (javascript) 반복되지 않는 가장 긴 문자열의 길이를 찾는 문제다. 예를들어 abcabcda 라면, abcd or bcda = 4가 된다. current라는 문자열 변수를 두고 현재 문자열에 포함되지 않은 문자라면 더해가면 되고, 포함되어 있다면 잘라내면 된다. current = "abc" 인 상태에서 다음 a가 들어오게 되면 current에 존재하는 a의 index를 찾아 그 다음부터 잘라내고, current.substring(2), current = "bc" 다음으로 들어온 a를 더해준다. current += "a", current = "bcd" /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { if .. 2021. 6. 11.
[LeetCode] Repeated String Match (javascript) 주어진 문자열 a, b가 있을 때, a를 몇번 반복해야 b가 한번이라도 포함되는지 찾는 문제다. 처음엔 별생각 없이 str.includes(b) 대신 new RegExp(b).test(str) 를 사용해 풀었었다. 그러나 정규식보다 includes가 훨씬 빨랐다. // 정규식보다 includes를 쓰는게 런타임도, 메모리도 훨씬 낫다 // 정규식 : Runtime 340ms, Memory 45MB // includes : Runtime 84ms, Memory 40.4MB /** * @param {string} a * @param {string} b * @return {number} */ var repeatedStringMatch = function(a, b) { let str = a; let count .. 2021. 6. 11.
[LeetCode] Single Number (javascript) 주어진 배열에서 하나만 존재하는 숫자를 찾아 리턴하는 문제다. 배열에서 숫자를 하나씩 꺼내가면서, 남은 배열에 같은 숫자가 존재하지 않는 경우 리턴한다. 존재하는 경우, splice로 확인한 숫자를 제거한다. /** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { const count = Math.floor(nums.length/2); for(let i = 0; i < count; i++){ const item = nums.shift(); const index = nums.findIndex((n)=> n===item); if(index > -1) { nums.splice(index, 1); } else {.. 2021. 6. 11.