[알고리즘] LeetCode 981. Time Based Key-Value Store JS
2022. 12. 24. 14:58
알고리즘
개요 객체형식으로 푸는 문제로 set,get을 정의하는 문제였다. set은 [key, value, timestamp]형식으로 주어지고 get은 [key, timestamp]형식으로 주어진다. set은 자료구조를 생각해서 데이터를 저장해야하고, get은 키와 일치하거나 가장 가까운 timestamp를 갖는 value를 출력하는게 문제이다. Time Based Key-Value Store - LeetCode Time Based Key-Value Store - Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's ..
[알고리즘] LeetCode 236. Lowest Common Ancestor of a Binary Tree JS
2022. 12. 23. 18:00
알고리즘
개요 이진트리가 주어지는데 여기서 가장 가까운 공통의 조상노드를 찾는 게 목적이다. 주어진 노드가 6,2라면 가장 가까운 조상노드는 5이므로 5를 리턴하면 된다. 이 문제는 이전에 풀었던 문제와 상당히 유사해서 금방 떠올릴 수 있었다. 그때는 이진검색트리의 성질을 이용해서 풀었는데 웃긴건 저번이랑 똑같이 문제를 풀었다는 점이다. [알고리즘] LeetCode Lowest Common Ancestor of a Binary Search Tree JS 개요 이진트리와 두 개의 노드가 주어지는데 이때 두 노드 공통의 가장 가까운 조상 노드를 주어진 이진트리안에서 찾아 리턴하는 문제이다. 이때 주어진 이진트리는 BST의 속성을 가지는데 정 choiblog.tistory.com 풀이 찾아야하는 노드 배열을 만든 뒤 ..
[알고리즘] LeetCode 207. Course Schedule JS
2022. 12. 14. 20:34
알고리즘
개요 numCourse와 prerequisites 두 배열이 매개변수로 주어진다. prerequisites는 각 numCourse에 대한 선 이수과목 정보가 주어진다. 예를들어 numCourse가 2라면 과목이 2개 있다는 뜻이고 prerequisites가 [1,0]으로 주어진다면 1을 이수하려면 0과목을 먼저 이수해야된다는 말이된다 따라서 0을 먼저 이수하면 전 과목을 이수할 수 있으니 true를 리턴한다. 만약 numCourse 2일때 prerequisites [1,0] [0,1]로 주어진다면 1을 이수하기 위해선 0과목을 먼저 이수해야되지만 반대로 0과목을 이수하기 위해선 1과목을 이수해야한다는 모순(싸이클)이 발생한다. 이렇게 되면 전과목을 이수할 수 없기 때문에 false를 반환해야한다. Cou..
[알고리즘] LeetCode 3Sum JS
2022. 12. 11. 22:09
알고리즘
개요 하나의 배열에서 세가지 숫자를 뽑아 0이 되는 경우를 모두 찾는 문제이다. 조합으로 생각하면 쉽다. 순서 상관없이 3가지 숫자를 뽑는데 같은 인덱스에서 3가지를 뽑을 수 없고 이미 만들어진 경우의 수라면 패스한다 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 경우의 수를 구하는 문제를 만나면 왠지 모르게 자꾸 DFS로 접근하게 된다. 이번 문제 자체는 세 가지를 뽑아서 비교하는 문제이니 단순히 그리디로 구현한다해도 반복문 3개를 돌려서 풀..
[알고리즘] LeetCode 01 Matrix JS
2022. 12. 10. 21:26
알고리즘
개요 0과 1로만 이루어진 2차원 배열이 주어질때 1의 인덱스에서 0과 얼마나 멀리 떨어져있는지 각 원소마다 계산하는 문제이다. 이때 거리는 상하좌우의 거리로 계산한다 01 Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 처음 문제를 BFS로 접근했었다. 조금 많이 복잡하게 구현됐는데 흐름도를 통해 살펴보면 다음과 같다. 2차원 배열을 탐색하기 위해 이중 for문을 돌린다 그렇게 돌면서 0은 넘어가고 1의 위치에서 BFS를 통해 근처 0의 위..
[알고리즘] LeetCode 57. Insert Interval JS
2022. 12. 7. 18:34
알고리즘
개요 2차원 배열 intervals와 1차원 배열 newInterval이 들어온다. intervals 배열은 시작 시간과 끝나는 시간을 나타내는 정수 1차원 배열을 원소로 갖는다 이때 1차원 배열 newInterval을 intervals 배열에 넣으려고 할때 시간이 겹쳐지지 않도록 겹쳐지는 부분을 합병해서 변경된 intervals 배열을 리턴하는게 문제이다. Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] 시간으로 생각하면 이해하기 쉽다. 1시~3시까진데 중간에 2~5시 인터벌이 들어와 1시~5까지가 되었다. Insert Interval - LeetCode Level up your coding skills and qu..
[알고리즘] LeetCode Maximum Subarray JS
2022. 12. 6. 12:50
알고리즘
개요 연속 부분 배열 중 가장 큰 값을 리턴하는 문제이다. [-2,1,-3,4,-1,2,1,-5,4] => [4,-1,2,1] => 6 Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 처음 투포인터가 떠올라 순차적으로 계속해서 접근해나갈때 왼쪽 포인터를 옮기는 조건을 도저히 찾을 수 없었다. 계속 고민하다가 못 풀어서 다른 사람의 풀이를 봤다. 잘 안풀렸던 부분이 값을 비교해나가며 교체하는 반복문 안 구조였다. 연속된 배열이..
[알고리즘] LeetCode diameter of Binary Tree JS
2022. 12. 6. 11:39
알고리즘
개요 주어진 이진트리에서 지름을 구하는 문제이다. 이때 지름은 정점과 정점 간의 길이 중에서 가장 긴 길이를 지름이라고 한다. Diameter of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 DFS로 풀어야한다는 것은 쉽게 눈치챌 수 있었다. 그런데 탐색하면서 계산해야 되는 길이를 어떻게 계산해야하는지 쉽게 떠올리지 못했다. 매번 DFS를 풀때나 BFS 풀때 노드의 레벨로 접근해서만 풀다보니 이번 문제처럼 역순으로 값을 가지고 ..
[알고리즘] LeetCode Add Binary JS
2022. 12. 6. 09:23
알고리즘
개요 이진수가 a,b 들어오는데 이진수 덧셈해서 리턴하는 문제이다 Add Binary - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 어떻게 덧셈이 이루어지는지는 알고있었는데 구현을 상당히 애먹어서 단순히 parseInt로 주어진 이진수를 십진수로 만들어 더하고 다시 이진수로 변환해주었다. 그런데 값이 js의 표현범위를 벗어났을 때 에러가 출력됐고 BigInt로 값을 더할 수 있다는 것을 확인했다. 이후 정석적인 덧셈을 확인하고 추가해놓았다. /** * ..
[알고리즘] LeetCode Majority Element JS
2022. 12. 5. 21:10
알고리즘
개요 주어진 배열에서 가장 많이 나온 원소를 찾아 리턴하는 문제이다. Majority Element - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 해쉬맵으로 쉽게 구현할 수 있었다. 처음엔 주어진 배열로 해쉬맵을 만들고 만들어진 해쉬맵에 키값으로 한번 더 돌려 구현하였다. 거기서 가장 큰 원소의 값을 answer 변수에 넣어 리턴하는 간단한 문제이다 /** * @param {number[]} nums * @return {number} * * 가장 많이 ..