[알고리즘] 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} * * 가장 많이 ..
[알고리즘] LeetCode Reverse Linked List JS
2022. 12. 4. 11:38
알고리즘
개요 주어진 연결리스트를 뒤집어 리턴하는 문제이다. Reverse Linked List - 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 풀이 이전 노드의 정보와 다음 노드의 정보를 저장해두면 쉽게 문제를 해결할 수 있다. 그런데 문제는 잘 풀어놓고 엉뚱한 곳에서 삽질을 했는데 노드의 위치를 리턴하는 부분이었다. 당연히 node가 가리키는 부분을 리턴했었다. 그런데 마지막 연결리스트의 tail까지 탐색하기 위해선 node가 null이 될때까지 탐색하기 때문에 n..
[알고리즘] LeetCode Ransom Note JS
2022. 12. 3. 19:50
알고리즘
개요 ransomNote라는 문자열과 magazine이라는 문자열이 주어지는데 이때 ransomNote가 magazine에 포함되어있는지를 확인해보는 문제이다. Ransom Note - 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 풀이 단순히 includes로 돌려볼 수도 있겠지만 그렇게한다면 ransomNote가 따로 떨어져있을 경우를 찾지 못한다. 따라서 HashMap을 사용하였고 쉽게 풀어낼 수 있었다 /** * @param {string} ransomN..
[알고리즘] LeetCode First Bad Version JS
2022. 12. 3. 17:59
알고리즘
개요 이렇게 주어지는 문제는 처음이었는데 함수를 전달받고 함수에 버전을 넣으면 bad version인지 아닌지 알려준다. 이를 통헤서 제일 처음 bad version을 찾는 문제이다 First Bad Version - 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 풀이 투 포인터로 접근을 했었고 그림으로 그려봤을 때 분기 조건으로는 다음과 같았다. 1 2 3 4 5 false false false true true 첫 번째 true가 나오는 조건을 찾는게 문제이..
[알고리즘] LeetCode Linked List Cycle JS
2022. 12. 2. 22:10
알고리즘
개요 연결리스트의 맨 마지막이 노드와 연결되어있는지, 즉 원형 연결 리스트인지 확인하는 문제이다. Linked List Cycle - 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 풀이 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boo..