인생은 효율성

https://leetcode.com/problems/escape-the-spreading-fire/ Escape the Spreading Fire - 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초마다 사방으로 퍼지는데 불에 타지 않고 도착지까지 간다고 할 수 있을 때, 시작위치에서 최대로 머무를 수 있는 시간을 구하는 문제이다. 크게 두 단계로 나눠서 진행해야 한다. 1단계는 불이 근원지부터 모든 셀에 퍼지는데 걸리는 시간을 grid에 기록하고 2단..

https://leetcode.com/problems/longest-common-subsequence/ Longest Common Subsequence - 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 알고리즘의 전형적인 LCA문제 그 자체이다. 이 문제는 top-down 방식과 bottom-up 방식 두 가지로 풀어보았다. class Solution: def longestCommonSubsequence(self, text1: str, text2: str) ->..

https://leetcode.com/problems/snakes-and-ladders/ Snakes and Ladders - 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. ladder 또는 snake를 만났을 때 해당 위치로 바로 이동하는 게 하나의 과정이라는 것 먼저 좌표를 구하는 함수를 따로 만들어서 현재 칸 번호를 주면 row, col을 되돌려주도록..

https://leetcode.com/problems/swim-in-rising-water/ Swim in Rising Water - 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문제인데 다익스트라 알고리즘을 사용해서 풀 수도 있다. 파이썬은 heapq 메서드가 있어서 우선순위 큐를 구현하기 쉽기 때문에 파이썬으로는 다익스트라 알고리즘을 적용해서 풀었고 자바스크립트는 DFS로 풀었다. [다익스트라] 다익스트라 알고리즘은 이 문제처럼 각 지점 간..

https://leetcode.com/problems/course-schedule/ Course Schedule - 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 prerequisites의 [0]의 값을 갖기 위해서는 [1]값을 먼저 얻어야 하는 BFS문제이다. 전형적인 BFS문제대로 풀었다. ① [0]의 값을 키로 딕셔너리(python) 혹은 맵(JS)를 만들어서 해당 값을 얻기 위해 먼저 얻어야 하는 목록들을 value로 저장해둔다. ② numCourses-..

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/ Shortest Unsorted Continuous 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 정렬해야 하는 제일 앞 인덱스와 제일 끝 인덱스를 찾아주면 된다. start와 end 두 가지 변수를 사용해서 start에는 [start] > [start+1]가 되는 지점을 찾고 end는 반대를 찾아서 변수에 저장해준다. ..

https://leetcode.com/problems/product-of-array-except-self/ Product of Array Except Self - 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의 [i]에는 자기 자신을 제외한 숫자를 모두 곱한 값이 저장되어야 한다. 그러면 i일 때 곱해주는 값은 nums [:i]와 nums [i+1:]으로 구분해서 생각할 수 있다. 다시 말해 나를 기준으로 앞부분과 뒷부분으로 나눠서 누적 곱을 구한다..

https://leetcode.com/problems/find-the-difference/ Find the Difference - 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 문제를 풀다가 풀이 방법이 이마를 탁 치게 만들어서 가져와봤다. 딕셔너리로 빈도수를 체크해서 풀어야 하나 고민하고 있었는데 의외로 쉽게 풀 수 있단 걸 알게 되었다. s와 t의 모든 문자가 똑같은데(예시에는 나와있지 않지만 s와 t의 문자들은 순서가 다를 수도 있다.) 단 한 가지만 t에..

[문제 1] 주어진 문자열 배열을 뒤집기 var reverseString = function (s) { let l = 0, r = s.length - 1; while (l None: l, r = 0, len(s)-1 while l < r: s[l], s[r] = s[r], s[l] l += 1 r -= 1 reverse() 메서드를 쓰면 간단하게 해결할 수 있지만 알고리즘으로 직접 구현하는 것도 매우 간단하다. 왼쪽과 오른쪽을 가리킬 포인터를 만든 뒤 각자의 위치에서 중간 쪽으로 하나씩..

이진 탐색 알고리즘은 검색 범위를 절반씩 줄여나가면서 탐색하는 알고리즘이다. 흔히 술자리에서 소주 뚜껑에 있는 숫자를 맞추는 게임을 할 때의 방식과 동일하다. 1. 25 제시. 타깃 숫자는 더 작음 => 범위를 0~25로 줄임 2. 12 제시. 타깃 숫자는 더 큼 => 범위를 13~25로 줄임 3. 19를 제시 => 정답 이렇게 숫자가 오름차순 혹은 내림차순의 일정한 순서로 정렬되어 있는 경우 이진 탐색 알고리즘을 사용하면 탐색 시간을 많이 줄일 수 있다. 이 방법을 응용한 문제 3가지를 풀어볼 것이다. [문제 1] 배열 nums에서 target숫자가 위치한 인덱스를 반환하라. (target이 nums에 존재하지 않으면 -1 반환) // JavaScript const searchIndex = (nums,..