본문 바로가기
반응형

algorithm82

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.
Reservoir Sampling? 날 괴롭히지마 [leetcode] n개중에 랜덤 한 k를 뽑는다고 할 때 Array list에서는 random.randInt(0, n) 식으로 랜덤 한 index를 추출, 해당 index를 접근해 값을 반환하는 식으로 구현할 수 있다. 이때 확률은 k/n 을 만족한다. 문제의 조건을 조금 바꿔서 linked list에서 특정 노드의 value를 랜덤 하게 k개를 선택하려고 할 때 해당 랜덤 선택 확률이 k/n (n = length of linked list)를 만족하려면? 단순하게 생각하기 linked list를 순회하면서 노드들의 value를 따로 저장해 둔다. (Linked list → Array list) 동일하게 Array의 length로 random.randInt(0, n) 식으로 index를 추출한다. 해당 index를 접근해.. 2023. 3. 13.
binarySearch를 정렬된 리스트에 insert를 위해서만 사용한 나 조금 무례할지도 [leetcode] 알고리즘 문제를 풀다 보면 정렬된 배열에서 특정 숫자가 들어갈 자리 찾는 문제를 자주 만나게 된다. 그런 문제들 만날 때마다 ‘아 또 binary search 쓰라는 말이구나’ 하고 기계적으로 코드를 치는데 오늘 만난 문제는 좀 달랐다. 풀이도 신박했어서 그거에 대해서 써보려고 한다. 그냥 배열 순회하면서 하나씩 비교하면 금방 찾겠네~ 아 껌이네~ 근데 medium?? 특이한 요구사항이 하나가 있다. Your solution must run in O(log n) time and O(1) space. 문제가 단순해 보여서 그런지 머릿속으로는 ‘그냥 순회하면서 하나씩 비교하면 바로 나오지 않나?’ 밖에 생각나지 않았다. 그렇지만 그럼 O(n) 이기 때문에… class Solution: def singleNo.. 2023. 2. 22.
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.
반응형

티스토리툴바