본문 바로가기

리트코드18

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.

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.

게임맵 최단거리 [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.

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.

K-diff Pairs in an Array [leetcode] 문제 풀이 리스트 안 숫자들 중 차이의 절대값이 k를 만족하는 숫자 쌍 의 개수를 찾는 문제다. 한국말로 한문장 정리하니 “의” 로 연결된게 많아 국어지문 푸는것 같다. 다시 정리하자. 리스트 안 숫자들 중 ⇒ ex. [3,1,4,1,5] 차이의 절대 값 ⇒ ex. |3 - 1| = 2 k를 만족하는 숫자 쌍 count! ⇒ ex. |3-1| == 2 ? (count +1) : nothing! 문제를 보면 리스트의 중복된 숫자가 있어도 1개로 친다고 한다. 그럼 로직상 중복체크도 필요하다는 얘기다. 나는 이렇게 풀었다. 현재 비교할 숫자 = nums[i] 비교 당해야 할 숫자들 = nums[i+1:] (중복을 피하기 위해 i 번째 이후 숫자들만 사용) 중복을 피하기 위해 num_set 생성 ⇒ num_s.. 2022. 2. 9.

이전 1 2 다음

티스토리툴바