https://leetcode.com/problems/median-of-two-sorted-arrays/두 개의 정렬된 List 합쳤을 때 중앙값을 구하는 문제이다. 단, 문제에서 O(log(m+n)) 시간 내에 풀이하라고 주어졌다. 1. Merge Sort 알고리즘처럼 하나씩 대소비교를 하여 정렬하는 풀이 시간복잡도 : O(m+n)Runtime : 90 msMemory : 16.8MBclass Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n = len(nums1) m = len(nums2) t = (n+m) # length of the merge..
Algorithm (PS)/LeetCode
https://leetcode.com/problems/sort-list 말그대로 배열을 정렬하는 문제이다. 그런데 이제 배열이 링크드 리스트 자료구조로 만들어 져 있는 상태인 ! 버블 소트같은거 밖에 생각못하다가 mergesort 로 풀어야 문제에서 조건으로 준 O(1) 공간 복잡도에 O(nlogn) 시간복잡도로 풀 수 있다. 기본 merge sort 라면 공간 복잡도가 2n 이 되었겠지만, 여기서는 링크드리스트의 특성을 이용하여 O(1) 으로 풀 수 있다. (대박..) LinkedList에서 중간 값(node) 를 구하는 로직이다. 낮은 값은 항상 한칸, 하나 더 큰 값은 항상 두칸씩 이동하다가 null 값을 만나면 순회를 멈추게 된다. 이렇게 하면서 중간값을 구하게 된다. LinkedList 문제에서..
https://leetcode.com/problems/all-possible-full-binary-trees/모든 가능한 이진 트리의 경우의 수를 구하는 문제이다. 이진 트리의 노드 수가 N이라고 주어 질때 N=1, N=3, N=5 의 경우를 그림으로 표현하면 아래와 같다. 그림에서 파악할 수 있듯이, N=5 의 경우 N=3이 root.left 와 root.right 에서 반복이 되고 있다. 즉, N=5에서는 N=3, N=1 에서 구한 값을 재활용하여 사용할 수 있다. N=7 또한 N=1, N=3, N=5의 값을 다시 활용하여 모든 경우의 수를 구할 수 있다. 또한 이진 트리는 root가 반드시 0, 그리고 자식 노드들이 항상 둘다 0 이거나 null 이므로, 노드의 개수는 항상 홀수라는 특성이 있다. ..
https://leetcode.com/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150 Spiral Matrix - LeetCode Can you solve this real interview question? Spiral Matrix - Given an m x n matrix, return all elements of the matrix in spiral order. Example 1: [https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg] Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Outpu leetcode.com 다양한..
스키장 갔다와서 오랜만에 릿코드 풀이! 확실히 여행 다녀오니까 머리가 잘 돌아간다 https://leetcode.com/problems/word-search/?envType=study-plan-v2&envId=top-interview-150 Word Search - LeetCode Can you solve this real interview question? Word Search - Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adja..
문제 요구사항 "O" 를 "X"로 flip 하라. 단, 가장 자리에 맞닿은 "O"의 경우 뒤집으면 안되며, 이 가장자리와 인접한 다른 "O"의 경우에도 뒤집지 않는다. 풀이 방법 (알고리즘 : BFS) 우선 M*N 배열에서 "O" 가 있는 칸의 위치 (i, j) 를 구한다. -> island 집합에 저장 가장자리에 있는 "O" 를 찾아서, "O"와 인접한 칸들까지 BFS로 찾아서 island 라는 집합에서 빼준다. 남아있는 좌표들은 X 로 flip 이 가능한 위치이므로 모두 변환해 준다. from collections import deque class Solution: def solve(self, board: List[List[str]]) -> None: N = len(board[0]) M = len(b..
