본문 바로가기
728x90
반응형

전체 글323

146. LRU Cache "가장 오랫동안 사용하지 않은 데이터(Least Recently Used)를 먼저 삭제한다"는 원칙을 가진 캐시 시스템을 설계하는 문제입니다.이 문제는 단순히 논리적인 코드를 짜는 것을 넘어, "데이터를 어떻게 저장해야 모든 동작을 O(1)에 끝낼 수 있는가?"라는 자료구조 선택 능력을 평가합니다. 🏗️ 1. 핵심 자료구조의 조합하나의 자료구조만으로는 O(1)을 달성할 수 없기 때문에, 두 가지를 섞어 사용합니다.Hash Map (Python의 dict):역할: 특정 키(key)가 캐시에 있는지 확인하고, 해당 노드의 주소값을 즉시 찾기 위해 사용합니다.성능: 검색 O(1)Doubly Linked List (이중 연결 리스트):역할: 데이터의 순서를 유지합니다. 최근에 사용한 것은 오른쪽(Tail 쪽).. 2026. 2. 1.
211. Design Add and Search Words Data Structure 1. 왜 재귀(Recursive) 방식이 필요한가요?일반 문자는 한 길만 따라가면 되지만, .을 만나면 현재 노드의 children에 있는 모든 자식 노드를 다 뒤져봐야 합니다. class WordDictionary: def __init__(self): self.root = TrieNode() def addWord(self, word: str) -> None: node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] .. 2026. 1. 30.
208. Implement Trie (Prefix Tree) + Trie delete 함수 1단계: 빈 Trie에 "CAT" 삽입처음에는 루트 노드 하나만 있고, children은 비어 있습니다. {}'C' 삽입: 루트의 children에 'C'가 없으므로 새 노드를 만듭니다.root.children = {'C': TrieNode()}'A' 삽입: 'C' 노드의 children에 'A'가 없으므로 새 노드를 만듭니다.C_node.children = {'A': TrieNode()}'T' 삽입: 'A' 노드의 children에 'T'가 없으므로 새 노드를 만듭니다.A_node.children = {'T': TrieNode()}종료: 'T' 노드의 is_end= True로 바꿉니다. 2단계: "CAN" 삽입 (중요!)이미 "CAT"이 있는 상태에서 "CAN"을 넣으면 'C'와 'A'는 이미 존재하는.. 2026. 1. 30.
56. Merge Intervals 📌 문제 설명intervals 배열이 주어지고,각 원소는 [start, end] 형태입니다.겹치는 interval을 모두 병합해서 반환하세요.Input: intervals = [[1,3],[2,6],[8,10]]Output: [[1,6],[8,10]] 정렬: 시작 기준 정렬 완료 [[1,3], [2,6], [8,10]]초기값: merged = [[1,3]]다음 구간 [2,6] 확인:1,3의 끝(3)이 2,6의 시작(2)보다 큽니다. (겹침!)merged의 마지막을 [1, max(3, 6)] 즉, [1, 6]으로 업데이트합니다.다음 구간 [8,10] 확인:1,6의 끝(6)이 8,10의 시작(8)보다 작습니다. (안 겹침!)merged에 [8,10]을 새로 추가합니다.최종: [[1,6], [8,10]]cl.. 2026. 1. 18.
Python(is...() 시리즈) 파이썬 문자열 객체에서 제공하는 is...() 시리즈 함수들은 문자열이어떤 성분으로 구성되어 있는지 확인하여 True/False를 반환하는 함수들입니다. 함수명알파벳/한글숫자공백/특수문자비고isalpha()✅❌❌문자만 있을 때isdigit()❌✅❌숫자만 있을 때isalnum()✅✅❌문자+숫자 조합 가능isspace()❌❌✅공백만 있을 때 2026. 1. 18.
128. Longest Consecutive Sequence 📌 문제 설명정수 배열 nums 가 주어질 때연속된 숫자들로 이루어진 가장 긴 수열의 길이를 반환하세요.⚠️ 조건:정렬 ❌O(n) 시간 복잡도가장 중요한 제약 조건은 O(n) 시간에 풀어야 한다는 점입니다. 보통 정렬을 하면 O(n log n)이 걸리므로, 정렬 없이 해결하기 위해 해시 셋(Set)을 활용해야 합니다.Input: nums = [100,4,200,1,3,2]Output: 41. 핵심 아이디어: "숫자의 시작점 찾기"배열에 있는 모든 숫자를 Set에 넣으면 어떤 숫자든 O(1)만에 찾을 수 있습니다. 여기서 핵심은 어떤 숫자가 연속된 시퀀스의 '시작점'인지 확인하는 것입니다.숫자 x가 있을 때, x - 1이 Set에 없다면? → x는 새로운 연속 시퀀스의 시작점입니다.x - 1이 이미 있다.. 2026. 1. 18.
238. Product of Array Except Self 📌 문제 설명정수 배열 nums 가 주어질 때각 인덱스 i에 대해 nums[i] 를 제외한 나머지 원소들의 곱을 반환하세요.⚠️ 조건:나눗셈 사용 금지O(n) 시간 복잡도추가 배열 사용 가능Input: nums = [1,2,3,4]Output: [24,12,8,6]Input: nums = [-1,1,0,-3,3]Output: [0,0,9,0,0] ⭐ 구현 포인트배열을 두 번 순회합니다.첫 번째 순회에서는 각 인덱스 기준 왼쪽 요소들의 곱을 저장하고,두 번째 순회에서는 오른쪽 요소들의 곱을 누적하면서기존 값에 곱해 최종 결과를 만듭니다.나눗셈 없이 O(n) 시간에 해결할 수 있습니다. class Solution: def productExceptSelf(self, nums: List[int]) -.. 2026. 1. 18.
347. Top K Frequent Elements 설명문자열 s 가 주어질 때연속으로 중복된 문자를 모두 제거하세요. Input: "abbaca"Output: "ca"class Solution: def removeDuplicates(self, s: str) -> str: stack = [] for k in s: if stack and stack[-1] == k: stack.pop() else: stack.append(k) return "".join(stack)⏱ 시간 복잡도문자열 한 번 순회 → O(n)📦 공간 복잡도Stack → O(n) 2026. 1. 18.
728x90
반응형

티스토리툴바