본문 바로가기

알고리즘8

2021.7.30 TIL (보이는 학생, 가위바위보, 점수구하기, 등수구하기) 문제) 보이는 학생 선생님이 학생을 일렬로 세웠을 때, 맨 앞에 서있는 선생님이 볼 수 있는 학생의 수를 구하기. 키의 숫자 배열이 주어진다. [100, 120, 110, 120, 130, 105] => 1+ 1+ 0 + 0 + 1 + 0 = 3 function solution(numbers) { let answer; // code here; return answer; } 해답) function solution(numbers) { let answer = 0, max = Number.MIN_SAFE_INTEGER; for (let num of numbers) { if (max < num) { answer++; max = num; } } return answer; } 문제) 가위바위보 두 배열이 주어졌을 때.. 2021. 7. 30.
2021.7.23 TIL (일곱난쟁이 알고리즘 해답) 일곱 난쟁이 문제 백설공주의 일곱 난쟁이 키의 합은 100이다. 갑자기 9명의 난쟁이가 서로를 백설공주의 난쟁이라 주장하고 있는 상황. 7명의 난쟁이를 키의 순서대로 나열한 배열을 출력할 것. 답이 여러 개 일 경우, 하나의 배열만 출력하면 된다. 예시 ) let numbers = [20, 7, 23, 19, 10, 15, 25, 8, 13]; // expected = [20, 7, 23, 19, 10, 8, 13]; 문제 ) function findMyDwarfs(numbers) { let answer; // solution here return answer; } 나의 답 ) 1. 난쟁이들의 키의 합을 모두 더한 후, 2명 거짓말쟁이들의 키의 합을 알아낸다. 2. 난쟁이들을 한 명씩 키를 돌아가며, 거.. 2021. 7. 23.
2020.08.31 Best Time to Buy and Sell 풀이 문제) 숫자가 나열된 배열이 주어졌을 때, 각 원소는 그 날의 주식의 현가라고 가정하자. 최대의 이익은 얼마일까? 풀이) 예전에 풀었던 문제와 대동소이한 문제다. 풀다보니 배열의 최소/최대값의 패턴이 보이는 듯 하다. var maxProfit = function(prices) { let buy = prices[0], result = 0 for(let i = 0; i < prices.length-1; i++) { buy = Math.min(buy, prices[i]) result = Math.max(result, prices[i+1] - buy) } return result }; 2020. 8. 31.
2020.08.26 Move Zeros 풀이 문제) 숫자 배열이 주어질때, 0은 배열의 끝으로 몰아 수정하는 것. 이 때, 배열은 카피해서 쓸 수 없으며, 원배열 자체를 수정해야 한다. 풀이) 야호! 이번 문제도 정해놓은 시간 안에 풀었다! (쉬운 문제, 정답률이 높은 것만...선정) 빈 배열을 정의하고, 0이 나올 때마다 해당 인덱스를 빈 배열에 오름차순으로 추가한다. 0이 아닌 숫자가 나올 경우, 0의 인덱스 중 제일 작은 숫자를 선정해 (오름차순으로 추가했기 때문에, 0번째 인덱스를 가져다 쓰면된다) 해당 인덱스와 순서를 스위치한다. O(n) 시간 복잡도를 가진다. /** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. .. 2020. 8. 26.
2020.08.24 Merge Two Binary Trees 풀이 문제 ) 두 개의 binary trees가 주어질때, 같은 위치의 노드의 합을 더해 새로운 binary tree를 만드는 것이다. 해결) 나는 너무 어렵게 접근했나보다. 해답은 생각보다 간단했다. (문제 풀때 너무 많은 시간이 걸리면, 그냥 답을 보고 익힌다. 수학의 정석 문제처럼, 알고리즘도 결국엔 같은 패턴이 있다고 생각하여 초반에 모르는 건 그냥 답을 보고 해결하는 방법에 익숙해지려고 노력한다) /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * t.. 2020. 8. 25.
2020.08.24 Two Sum 다른 풀이 var twoSum = function(nums, target) { let comp = {}; for(let i = 0; i < nums.length; i++){ if(comp[nums[i]] !== undefined) { console.log(comp) return [comp[nums[i]], i] } comp[target - nums[i]] = i } } 주말에 하기로 한 two sum 의 풀이는 평일인 오늘에 하게 되었다. 해당 문제에 대한 풀이를 보니, 지난번 내가 푼 방법이 'Brutal force'한 풀이라며 말 그대로 우격다짐으로 억지로 풀어낸 해답답게 엄청난 runtime과 시간 복잡도를 자랑했다. 다른 풀이가 있을까 하여 봤더니, Hash table 의 방법을 이용하는 방법이었다. 자바스.. 2020. 8. 24.