본문 바로가기
반응형

분류 전체보기153

Trie 자료구조와 문제풀이 [leetcode] Leetcode 에서 매일 하나씩 문제가 나오고 그걸 풀다보면 매주 마다 하나씩 테마가 있다고 느끼게 된다. 이번주는 trie라는 자료구조를 써야하는 문제가 자주 나왔고, 마침 내가 몰랐던 자료구조이기에 이번 기회에 한번 정리하고 넘어가려 한다. (물론 이전에도 한두문제 나왔었지만 그냥 포기하고 넘어갔었다.) 위키피디아를 긁어오자면, ? 머리에 물음표가 뜬다. 무슨소리인가. 트리인건 알겠는데. 같이 그려져 있는 그림을 가져와보자 그림을 살펴보면 ‘t’라는 단어로 시작되는 단어가 있는지(exist), 있다면 뭐가 있는지(search), 몇개 있는지(how many) 등을 트리를 통해 빠르게 접근가능하다는 장점이 있는 자료구조이다. 어떤 블로그를 보니 Retrieval 에서 trie라는 단어를 따왔다던데 단.. 2022. 6. 21.
점진적 뉴스 군집화 하기 (incremental news clustering) 요즘 관심 가지던게 하나 있는데 바로 점진적 문서 군집화 무슨 소리냐 뉴스의 경우, 계속 써지고 발간되고 사람들한테 제공된다. 지금까지 내가 해온건 어떤 시간대 (가령, 하루단위) 뉴스를 군집화(clustering) 한뒤, 비슷한 주제, 이슈로 묶여있길 바라며 군집을 살펴보는 일이였다. (오늘의 주요 이슈는 무엇인지 군집화된 뉴스를 통해 살펴보기 위해) 문제가 있다. 뉴스는 계속 만들어지고, 이슈는 계속 변한다. 특정 데이터를 통해 만든 문서 벡터 공간은 새로운 데이터가 나타나면 유효하지 않다 (새로운 feature가 생긴다는 얘기다. 벡터 공간을 통한 비교를 수행할 수 없다.) 위의 두문제를 해결하면서도 주요 이슈를 확인하기 위한 군집화를 위해 하루치 몰아서 하는게 아니라 특정시간대별로 군집화를 수행한.. 2022. 6. 6.
게임맵 최단거리 [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.
ㅇㅎ 게시물 수집하기 (fastapi, APScheduler, MySql) 개요 나는 커뮤니티를 자주 본다. 커뮤니티를 보다보면 게시물들 사이로 간간히 “ㅇㅎ” 라는 키워드가 붙은 게시물을 마주하게 되는데 “약한 후방주의” 라는 말의 줄임말이다. 후방 주의란? 남자들이 주로 접속하는 사이트들에는 하루에 적어도 하나씩 꼭 올라온다. 간간히 보이는 게시물은 보일때마다 무지성으로 클릭하게 되는데, 어느날 이런생각이 들었다. 하나로 모아서 보면 안될까? 좋은 생각이 떠오르면 그건 이미 누가 했다고 하던가... 이미 그런 사이트가 있었다. 모두의 후방 모두의 후방 모두의 후방 data.pureugong.com 하지만 나도 하나쯤은 만들어 보고 싶었다. 그래서 해당 사이트의 About 탭을 들어가 tech stack을 살펴본다. 오호 저런 기술로 구현하셨군... 하고 위로 좀만 올라가니 .. 2022. 5. 5.
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.
Arithmetic Slices [leetcode] 문제 https://leetcode.com/problems/arithmetic-slices/ Arithmetic Slices - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 아... 풀었는데 소 뒷걸음 치다 벌레 잡은 격이 느낌이다. 부분배열(contiguous subsequence of the array) 이 등차수열을 만족하는지 확인하고 맞다면 개수를 +1 해주는 문제였다. 부분배열을 검증하는 방법은 해당 배열의 모든 숫자와 등차수열 합공식에 넣은.. 2022. 3. 3.
반응형

티스토리툴바