밤 늦게까지 여는 카페

안녕하세요. 요즘 leetcode 문제를 열심히 풀고 있습니다.그래서 알고리즘 문제 풀이를 따로 포스팅 하지 않았습니다만... leetcode의 399. Evaluate Division 문제를 Runtime 100%로 풀게 되어서 포스팅하게 되었습니다. 1. 문제이 문제는 equations, values, queries 파라미터가 주어집니다. equations은 2개의 문자열로 이뤄진 리스트의 리스트로 values와 한 쌍이고equations[i][0] / equations[i][1] = values[i] 라는 뜻을 가집니다.예시equations = [["a","b"],["b","c"]]values = [2.0, 3.0]a / b = 2.0, b / c = 3.0queries는 equations와 동일..

안녕하세요. 이번에는 leetcode의 75. Sort Colors 문제를 풀어봤습니다.놀랍게도 첫 시도에 runtime 100%를 찍을 수 있었는데요. 한번 정리해보겠습니다!1. 문제이 문제에서는 길이 n인 수열이 주어집니다. 수열은 0, 1, 2로 이뤄져있고 0은 빨간색, 1은 하얀색, 2는 파란색을 의미합니다. 라이브러리 사용 없이 수열을 0, 1, 2 순으로 정렬해야 합니다.+ 새로운 수열을 반환하는 것이 아니라 수열 내부의 값을 바꿔줘야 합니다. 예시)주어진 수열 [1, 0, 2, 1, 2, 2]을 [0, 1, 1, 2, 2, 2] 로 바꿔야 합니다. 2. 풀이제가 생각한 방법은 1. 수열을 앞에서부터 쭈욱 읽으면서2. 순서가 잘못된(작은 수가 큰 수보다 뒤에 있는) 것을 발견하면 3. 바꿔주는..

이전에 풀었던 2257. Count Unguarded Cells in the Grid 문제를 3번째로 도전하는 중입니다. 이번에는 다른 분들이 푼 솔루션을 보고 개선 방법을 찾아봤습니다. 아뿔싸...첫번째로 시도한 방법의 구현만 바꿨을뿐인데 100%인 답이 있더라고요...참고: https://leetcode.com/problems/count-unguarded-cells-in-the-grid/solutions/6067031/beats-100-video-full-explain-3-approaches/ 첫번째 풀이에서 walls_dict, visited를 관리하는 대신에 m x n 짜리 격자지도를 표현할 수 있는 이중 리스트를 만드는 편이 훨씬 빠르더라고요...!dictionary와 list의 성능 차이인 것..

안녕하세요. 오늘은 이전에 풀었던 2257. Count Unguarded Cells in the Grid 문제를 다시 풀어보겠습니다.참고: https://goodahn.tistory.com/252 1. 개선된 문제 풀이이전에 풀었던 방법의 시간복잡도는 O(max(m, n) * guard 수) 입니다.그런데 'max(m, n) * guard 수'는 최대 10^9까지 커질 수 있습니다! 그래서 알고리즘의 속도가 느린 것이었죠.격자지도의 모든 점을 확인하는 것보다는 모든 guard에 대해서만 확인하는 것이 효율적이라고 생각했지만 문제 조건이 그렇지 않았습니다...guard의 수만큼 격자지도를 중복으로 검사하는 것이 효율성에 많은 영향을 미친 것 같더라고요 새로운 방법은 격자지도의 모든 점을 확인하는 방법입니다..

안녕하세요. 오늘은 leetcode의 2257. Count Unguarded Cells in the Grid 문제를 풀어봤습니다.https://leetcode.com/problems/count-unguarded-cells-in-the-grid/description/ 1. 문제이 문제에서는 두 수 m, n과 좌표로 이뤄진 두 리스트 guards, walls가 주어집니다.m, n은 격자 지도의 세로와 가로를 의미합니다. guards는 guard들의 좌표 리스트입니다. guard들은 자신의 좌표에서 상하좌우 방향으로 탐색할 수 있습니다. walls는 wall들의 좌표 리스트입니다. wall은 guard들의 탐색을 막습니다. 문제에서는 guard들이 탐색하지 못하는 칸의 개수를 구해야 합니다. (1, 1)에 g..

안녕하세요! 어제 말씀드렸던대로 어제 풀었던 2516. Take K of Each Character From Left and Right 문제를 다시 풀어보겠습니다! 참고: https://goodahn.tistory.com/250 1. 개선된 문제 풀이 - two pointer끄아아악! 아쉽게도 더 나은 방법을 생각해내지 못했습니다. 이번에도 거침없이 leetcode의 풀이를 참고했습니다!참고: https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/editorial/#approach-2-sliding-windowleetcode의 풀이를 보니 two pointer 방식입니다.two pointer 방식은 left 포인터와 righ..