성댕쓰 똑똑한 생활

Queue를 이해하기 위해 stack을 알아야한다. stack은 FILO이다. Queue는 FIFO이다. 데이터를 Queue에 넣는 행동 enqueue 빼는 행동 dequeue이다. enqueue, dequeue모두 O(n) time complexity를 갖는다. 이를 구현하기 위해 doubly linked list를 사용하면된다.(LRU cache 참고) # FIFO policy Queue를 implementation 하여라 # 함수 : enqueue() dequeue() class QueueNode: def __init__(self, val:int) -> None: self.val = val self.left = None self.right = None class Queue: def __init__(..

똑똑한 개발/Algorithm 과 Data Structure 2021. 8. 3. 21:10

LRU cache 문제는 key-value를 저장하는 자료구조를 만드는 문제이다. put(key, value)로 저장하고 get(key)로 value를 리턴한다. 자료구조를 만들 때 max size를 설정하는데, 저장개수가 이 보다 크면 저장 데이터 한 개를 지우고 저장한다. 데이터를 지울 때는 규칙이 있다. Least Recently Used 즉, 가장 오래전에 사용한 데이터를 지운다. 문제이름 LRU cache는 지우는 규칙을 가리킨다. 사용한 순서를 알기 위해서 array를 사용할 수 있다. 그러나 array는 가장 먼저 사용한 아이템을 지우고 빈 자리를 메워야하는 제약때문에 O(n) time complexity가 필요하다. 문제에서 원하는 time complexity는 O(1)이다. doubly ..

똑똑한 개발/Algorithm 과 Data Structure 2021. 8. 2. 21:26

리스트의 끝까지 가면서 카운트를 알아낸 뒤, 중간까지 순회하는 방법이 있다. 위의 방법은 2path iteration이다. 길이를 알기위해 1번 답을 구하기 위해 1번 iterate했기 때문이다. 1path iteration으로 풀려면 아래와 같은 방법이 있다. array를 사용한다. 리스트를 array에 담으면 자동으로 length를 알게되고 미들인덱스 value를 리턴하면 된다. time complexity, space complexity는 O(n)이다. 1path iteration에 space complexity를 O(1)로 줄이는 방법도 있다. fast & slow pointer 방법이다. fast pointer는 2칸씩 움직이고 slow pointer는 1칸씩 움직인다. # Title : Lin..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 29. 23:01

Merge sort는 주어진 element array를 나눈뒤 합치면서 정렬하는 방법이다. time complexity는 O(nlogn)이다. stable한 성질을 가지고있다. # Title : Merge Sort # Chapter : Sorting # 문제: 주어진 array를 Merge sort 하여라 from typing import List def mergeSort(nums:List[int]) -> List[int]: # split length = len(nums) if length == 1: return nums mid = length // 2 left_nums = nums[:mid] right_nums = nums[mid:] sorted_left = mergeSort(left_nums) sor..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 29. 21:38

정렬된 두 개의 링크드 리스트를 합치는(정렬하여) 문제이다. # Title : 두개의 정렬된 linked Lists 합치기 # Chapter : Linked List # 문제 : 주어진 두개의 정렬된 LinkedList를 정렬이 된 상태로 합쳐라 # L1 : 1→3→5→7 # L2 : 1→2→3→4 # L1+L2 : 1→1→2→3→3→4→5→7 from typing import List class ListNode: def __init__(self, val) -> None: self.val = val self.next = None def createList(in_list:List[int])-> ListNode: if len(in_list) == 0: raise RuntimeError('in_list mus..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 27. 22:11

리스트의 노드를 삭제하는 방법은 previous 노드를 삭제 노드의 next 노드와 연결해주면 된다. 하지만, 이 경우 head의 노드를 삭제하는 것이 불가능하다. 이를 해결하기 위해 recursive 방법을 쓸 수 있다. def recursive(self, node: ListNode) -> ListNode: if not node: return None next_node = self.recursive(node.next) if node.val == self.__val: return next_node else: node.next = next_node return node iterative 방법으로도 구현가능하다. head node 앞에 dummy node를 만들어서 사용하면 문제가 된 edge case를 처..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 24. 22:36

구현하려는 동작 첫 번째 동작은 addAtHead이다. head가 가리키던 노드를 새로운 노드의 next가 가리키게 만들고 head가 가리키는 노드를 새로운 노드로 만든다. 두 번째 동작은 addBack이다. 링크드 리스트에 새로운 노드를 추가한다. 세 번째 동작은 find이다. 노드를 찾아 반환한다. 네 번째 동작은 addAfter이다. node, value를 파라미터로 받는다. node 다음에 value를 가진 새로운 노드를 추가한다. 마지막 동작은 deleteAfter이다. 편의상 delete 대신 구현하는 동작으로 파라미터로 받은 노드 다음의 노드를 삭제한다. from typing import Coroutine class ListNode: def __init__(self, val) -> None:..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 20. 21:47

링크드 리스트는 값과 주소를 가진 노드로 이루어져있다. 탐색에 O(n) time complexity가 필요하다. 배열과 비교해보면 탐색에 필요한 time complexity는 같다. 그러나 random access에 필요한 값은 링크드 리스트 O(n) 배열 O(1)로 다르다. insertion과 deletion에 필요한 time complexity는 O(1)이다. 하나의 노드가 하나의 노드에 대한 정보를 가지고 있으면 singly linked list, 두 곳의 정보를 가지고 있으면 doubly linked list라고 부른다. 링크드 리스트는 tree나 graph의 기본 데이터 스트럭트가 된다. 링크드 리스트를 python으로 구현해 본 코드 # Title : Linked List Intro # 1. ..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 20. 20:48

N Queens 문제는 NxN 매트릭스에 N개의 queen을 서로 공격할 수 없는 위치에 놓는 모든 방법을 구하는 문제이다. 참고로 queen은 가로, 세로, 대각석으로 공격이 가능하다. basic solution 매트리스 모든 위치를 decision space로 생각하고 백트래킹 적용한다. 단, 중복 확인을 피하기 위해 현재 decision space 는 이전 위치의 다음 위치부터로 하는 제한을 둔다. queen은 각 행에 1개씩만 올 수 있다는 사실을 이용하여 1단계 더 최적화 가능하다. queen의 위치 위반 규칙을 이용하여 1단계 더 최적화 가능하다. hash set을 사용하여 칼럼과 대각선이 규칙을 위반하는지 체크가능하다. 로우는 위에서 한 작업 덕분에 체크하지 않아도 된다. # Title : ..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 19. 23:22

백트랙킹을 이용하여 스도쿠 퍼즐을 푸는 문제이다. # Title : Sudoku 풀이 # Chapter : Backtracking # Link : # ChapterLink : # 문제 : 주어진 sudoku를 풀어라 (inplace로서 input object에 답을 넣어라) # [['. ','5','1','3','. ','9','. ','. ','6'], # ['. ','2','. ','8','7','1','3','4','5'], # ['. ','. ','. ','2','. ','. ','. ','. ','. '], # ['2','1','9','7','6','4','. ','3','. '], # ['. ','. ','. ','1','3','. ','. ','. ','. '], # ['7','3','. '..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 17. 22:36