본문 바로가기

LeetCode25

number dictionary 선언시… 나는 여태껏 python dictionary를 사용할 때, key값이 어떤 값이던간에 key:value 형태로 사용하곤 했다. key 값이 숫자건 문자건 key가 생성되어 있다면 value를 추가(혹은 수정) key가 없다면 key에 대해 정의한뒤 value를 추가 하는 식으로 말이다. (defaultDict 안쓰는 고집이 있다.) 가령 예를 들어, 무방향 그래프에서 각 노드 간 연결이 아래와 같이 주어진다고 할 때 connections = [[0,1],[0,2],[1,2]] 이걸 dictionary 형태로 구성한다면 connections = [[0,1],[0,2],[1,2]] num_dict = {} for conn in connections: a,b = conn[0], conn[1] if a not .. 2023. 3. 26.

LRU cache와 Double-Linked List 그리고 Ordered Dict [leetcode] tl;dr LRU cache 내부 구조는 double-linked list + dictionary(hash table) 형태로 구성 python의 collections.OrderedDict 는 double-linked list + dictionary(hash table) 형태 (삽입된 순서를 보장, 순서를 바꿀 수 있는 내부 함수 제공) 오늘 리트코드로 푼 문제의 제목은 LRU Cache 였다. LRU cache란? 우선, cache가 뭔지 정의되어야겠지? cpu는 연산할 때 사용하는 데이터를 디스크에서 가져오는데, cpu 연산속도에 비해 디스크에서 데이터 조회해 가져오는 속도는 절망적이다. 그래서 중간에 “디스크보다 훨씬 빠르게 조회할 수 있지만 적재는 적게 되는 공간”을 두는데 그게 바로 메모리다. .. 2023. 3. 18.

circular-queue 자료구조와 문제풀이 [leetcode] 진짜 백만 년에 알고리즘 문제풀이에 대해서 글을 쓴다. 그동안 잘 안 썼는데, 문제 푸는 것보다 글 쓰는 게 더 어렵다고 느껴졌기 때문이다. 그렇지만 이번에 쓰는 이유는 내가 잘 안 쓰는 자료구조이기도 하고, 학교 다닐땐 알고리즘 코딩 테스트에서 못 풀었었는데 지금은 푼 기념으로 정리하고자 글을 적는다. 이번에 쓸 자료구조는 queue의 변형인 circular-queue 다. 우선 queue 란, stack 자료구조와 다르게 first-in first-out (FIFO)의 입출 로직을 갖는 자료구조를 얘기한다. 여기에 빈 배열이 있다고 치자. [ ] 차례로 1,2,3 의 숫자를 집어넣는다 치면 (enqueue라고 한다.) [1,2,3]으로 들어가고, 꺼낼 땐 (dequeue라고 한다.) 1 ← [2, 3.. 2022. 9. 28.

Trie 자료구조와 문제풀이 [leetcode] Leetcode 에서 매일 하나씩 문제가 나오고 그걸 풀다보면 매주 마다 하나씩 테마가 있다고 느끼게 된다. 이번주는 trie라는 자료구조를 써야하는 문제가 자주 나왔고, 마침 내가 몰랐던 자료구조이기에 이번 기회에 한번 정리하고 넘어가려 한다. (물론 이전에도 한두문제 나왔었지만 그냥 포기하고 넘어갔었다.) 위키피디아를 긁어오자면, ? 머리에 물음표가 뜬다. 무슨소리인가. 트리인건 알겠는데. 같이 그려져 있는 그림을 가져와보자 그림을 살펴보면 ‘t’라는 단어로 시작되는 단어가 있는지(exist), 있다면 뭐가 있는지(search), 몇개 있는지(how many) 등을 트리를 통해 빠르게 접근가능하다는 장점이 있는 자료구조이다. 어떤 블로그를 보니 Retrieval 에서 trie라는 단어를 따왔다던데 단.. 2022. 6. 21.

게임맵 최단거리 [programmers&leetcode] 문제 풀이 처음 이 문제를 프로그래머스에서 마주쳤을때는 풀지 못했다. 나중에 풀고 넘어가야할 문제로 넘겼는데 오늘 leetcode 에서 비슷한 문제를 만나게 되고, 해당 문제의 hint를 보게 되어 ‘이렇게 푸는 거 구나!’ 싶어서 풀게 되었다. 그럼 저 문제를 풀기 전에 hint를 주었던 leetcode 오늘의 문제부터 살펴보기로 하자. hint 부분에 Do a breadth first search to find the shortest path. 라고 적혀 있는걸 보고 bfs로 푸는구나 하고 알게 되었다. leetcode의 문제를 보면 각 점 좌표에서 여덟방향으로 0이 있는지 조사후 해당 경로를 다음 단계에서 움직일 예정이라고 리스트에 저장한다. 예를 들어, 3*3 행렬(0-index)의 [1,1] 의.. 2022. 5. 16.

tree 문제 2개 (dfs & bfs) [leetcode] DFS 가장 깊은 노드 끼리 합산 뒤, 반환하는 문제다. 이 문제의 경우 dfs( Depth First Search )를 통해 풀면 된다. 재귀 함수를 사용하고, 함수의 반환 값은 [ 노드의 값, 노드의 깊이 ] 를 반환 한다. left 와 right 값을 반환 받았을때 노드의 깊이 를 비교한 뒤, left 노드의 깊이 > right 노드의 깊이 일 경우 left 노드 정보 ( [ 노드의 값, 노드의 깊이] ) 를 반환 left 노드의 깊이 == right 노드의 깊이 일 경우 노드 값 합산 ( left+right노드의 값, left(right) 노드의 깊이] ) 를 반환 left 노드의 깊이 < right 노드의 깊이 일 경우 right 노드 정보 ( [ 노드의 값, 노드의 깊이] ) 를 반환 해당 조.. 2022. 5. 16.

tree 문제 2개 [leetcode] 첫번째 문제 Increasing Order Search Tree 이진 트리를 가장 작은 수부터 차례대로 오른쪽 자식 노드로 이어 붙이는 문제였다. 이진 트리의 경우, 숫자 크기에 따라 현재 노드보다 작으면 left, 크면 right 로 붙어있다. 그렇기 때문에 아래 규칙으로 재귀를 만들면 된다. left 노드의 가장 오른쪽 (right leaf) 의 오른쪽 가지에 node를 이어 붙인다. left 가 존재하지 않으면 해당 순서를 무시 node의 오른쪽 가지에 right 노드를 이어 붙인다. right 가 존재하지 않으면 해당 순서를 무시 left를 반환한다. (새로운 root가 된다.) left가 없었다면 node 를 반환 def reConnect(self, node): if node == None: r.. 2022. 4. 17.

Score of Parentheses [leetcode] 문제 문제풀이 설명 하...또 쉬워보여서 도전했다가 오지게 오래걸려서 풀었다. (그래도 풀었다는게 대견쓰) 규칙에 따라서 괄호를 숫자로 변경한 뒤, 모든 숫자의 합을 구하는 문제다. (규칙은 위에 써져 있다.) 분명 말하지만 이미 밸런스한 상태라 스택이 필요없다. 괄호를 어떻게 치환하는지가 관건이다. 처음에는 “()”를 “|” 로 치환했었다. 그렇게 변경할 경우 | 양옆에 괄호를 보고 값을 구할 수 있을거라 생각했었지만, (()()) 의 경우에는 ( | | ) 로 변하고, (()(()())) 인 경우에는 ( | ( | | ) ) 등 로직을 구성하는데 있어서 언제 더하고, 언제 기다릴지 에 대한 로직이 뚜렷하게 보이지 않았다. 몇번의 불통 끝에 하나 발견한 사실은 처음 등장하는 “)(” 을 기준으로 양옆으.. 2022. 3. 17.

Linked List Cycle [leetcode] 코드 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: num_list = [] curr = head while True: if curr == None: return False if curr not in num_list: num_list.append(curr) curr = curr.next else: return True 문제 풀이 과정 설명 나는 지나는 모든 노드를 리스트에 저장한 뒤, 사이클이라면 리스트에 중복되는 노드가 분명.. 2022. 3. 9.

이전 1 2 3 다음

티스토리툴바