분류 전체보기 (213) 썸네일형 리스트형 [Leetcode]_169. Majority Element 문제 https://leetcode.com/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150 LeetCode - The World's Leading Online Programming Learning Platform 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 풀이 다수의 요소의 갯수를 반환하는 문제이니 요소의 갯수가 가장 많은 것을 반환하면 된다고 생각했다. hash를 이용하.. [좌충우돌, 파이썬으로 자료구조 구현하기] Heapify 구현하기 주어진 배열이나 이진트리를 힙 구조로 재배열 하는 것을 heapify라 한다. h = [] arr = [21, 33, 17, 27, 9, 11, 14] for i in arr: heappush(h,i) print(h) >>> [9,17,11,33,27,21,14] 위 코드처럼 배열의 원소를 차례로 heappush해서 힙 구조의 배열을 별도로 만드는 것은 쉽다. 이제는 주어진 배열 자체를 힙 구조로 만들자. 즉, 배열의 원소를 제자리 교환을 이용하여 힙 구조로 만든다. heappush에서 사용한 방식과 같이 마지막 노드에서 루트 노드로 가면서 힙 구조를 만들 방법을 생각해보자. 마지막 노드 3이 부모 노드보다 크므로 왼쪽 노드로 넘어간다. 값이 1인 노드는 부모 노드보다 작으므로, 서로 교환한다. 위로 올.. [좌충우돌, 파이썬으로 자료구조 구현하기] 힙(heap) 구현하기 큐(Queue)는 선입선출의 자료구조이다. 들어가는 자료에 우선순위를 매겨서 들어간 순서와 관계없이 나갈 때는 우선순위가 높은 자료가 먼저 나가는 구조를 우선순위 큐(Priority Queue)라고 한다. 힙(heap)이란, 우선순위 큐를 구현한 자료구조이다. 힙은 다음과 같은 규칙에 따라 구성한 이진트리이다. 규칙 1. 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다. (레벨 순서로 노드를 삽입한다.) 위 그림은 모두 이진트리인데, (a)는 힙이지만 (b)는 힙이 아니다. 왜냐하면 (b)는 왼쪽에서 부터 채워져야한다는 규칙을 벗어났다. 규칙 2. 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙(min heap)이다. (최대 힙은 부모 노드가 자식.. [Leetcode]_80. Remove Duplicates from Sorted Array 2 문제 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II - LeetCode Can you solve this real interview question? Remove Duplicates from Sorted Array II - Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place [https://en.wikipedia.org/wiki/In-place_algorithm] such that each unique elemen leetcode.com 풀이 26. Remove Duplicates from Sorted .. [Leetcode]_26. Remove Duplicates from Sorted Array 문제 Remove Duplicates from Sorted Array Remove Duplicates from Sorted Array - LeetCode Can you solve this real interview question? Remove Duplicates from Sorted Array - Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place [https://en.wikipedia.org/wiki/In-place_algorithm] such that each unique element ap leetcode.com 풀이 오름차순으로 정렬된 배열이 주어지고 해당 배열을 앞에서부터 유니크한 요.. [좌충우돌, 파이썬으로 자료구조 구현하기] 형제 노드가 없는 노드 찾기 문제 이진트리가 있을 때, 형제 노드가 없는 노드의 키를 출력하라. 형제 노드가 없는 노드가 없으면 -1을 출력하라. 37 / 20 / 113 출력: [20, 113] 풀이 형제 노드를 찾으려면 레벨 순서 순회를 해야한다. 레벨 순서 순회를 하면서 left 노드가 있을 때, right 노드가 없으면 결과 리스트에 해당 노드를 추가해준다. 반대의 경우도 마찬가지이다. def find_has_no_sibling(tree): res, q = [], [tree.root] while q: node = q.pop(0) if node.left: q.append(node.left) if not node.right: res.append(node.left.data) continue if node.right: q.appen.. [좌충우돌, 파이썬으로 자료구조 구현하기] 이진 트리에서 키를 삭제하기 문제 크기가 n인 이진트리가 주어질 때, 주어진 값(key)를 삭제하고 레벨 순서상 가작 마지막값으로 대체하는 함수를 만들어라. 풀이 삭제할 키를 가진 노드르 찾아야한다. 마지막 노드와 마지막 노드의 부모 노드를 찾아야한다. 마지막 노드를 찾아야 삭제할 곳에 마지막 노드 값으로 대체할 수 있게 된다. 또한, 마지막 노드의 부모노드를 찾고 마지막 노드가 왼쪽 노드인지, 오른쪽 노드인지 찾아서 알맞게 해당 자식노드를 None값으로 만들어줘야한다. 문제에서 레벨 순서상이라고 했으니, 특정 노드 찾는 것은 레벨 순수 순회를 이용하여 찾는다. 즉, 삭제할 키를 가진 노드를 찾기, 마지막 노드 찾기에서 레벨 순서 순회를 2번 사용해줘야한다. def delete_key(tree,key): q = [tree.root].. [좌충우돌, 파이썬으로 자료구조 구현하기] 이진트리에 키 삽입하기 문제 [https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/?ref=lbp] 이진트리와 키가 주어질 때, 이진트리의 레벨 순서에서 가장 먼저 사용할 수 있는 위치에 키를 삽입하는 함수를 만들어라. 풀이 문제에서 "레벨 순서"에서 가장 먼저 사용할 수 있는 위치라고 했으니 레벨 순서로 푼다. 위 그림의 예시를 보면 11번의 오른쪽 자식이 레벨순서에서 가장 먼저 사용할 수 있는 위치이다. def insert_key(tree,key): new_node = Node(key) if not tree.root: tree.root = new_node else: q = [tree.root] while q: node = q.pop(0) if no.. 이전 1 ··· 22 23 24 25 26 27 다음 목록 더보기
