본문 바로가기

분류 전체보기161

힙(heap)의 기본 구현 * 배열을 사용하여 힙을 구현한다. - 구현시, root node index는 1로 설정한다 - parent node's index = child node's index // 2 - left child node's index = parent node's index * 2 - right child node's index = parent node's index * 2 + 1 class Heap: def __init__(self, data): self.heap_array = list() self.heap_array.append(None) self.heap_array.append(data) def move_up(self, inserted_idx): if inserted_idx + \ self.heap_array.. 2020. 10. 10.
힙(heap)의 기본 * 힙(heap): 이진 트리의 일종으로, 최댓값 또는 최솟값을 빠르게 찾기 위해 고안되었다 완전 이진 트리의 성격을 가진다 * 완전 이진 트리(complete binary tree): 자식 노드를 삽입할 때 가장 왼쪽의 노드부터 삽입하는 트리 * 시간 복잡도: 힙에 데이터를 넣고, 최댓값 또는 최솟값을 찾으면, O(log n)의 시간 복잡도를 가짐 * 힙 구조의 유형: 최대 힙(Max Heap), 최소 힙(Min Heap) * 힙과 이진 탐색 트리의 비교 - 힙은 최대/최솟값에 초점을 맞추어 이를 빠르게 구하기 위한 구조 - 이진 탐색 트리는 탐색을 빠르게 하기 위한 구조 - 이미지 출처: www.fun-coding.org/Chapter11-heap.html - 내용 출처 : FASTCAMPUS 2020. 10. 10.
Vim(Vi)에서 Dos CR-LF 를 Unix Newline으로 변환하기(개행문자 변환) 윈도우 환경에서 작성한 파일을 유닉스/리눅스 환경에서 읽으면 에러가 나는 경우가 있다. vi를 이용해 해당 파일을 열어보면 ^M 이라는 글자가 찍혀있는 것을 볼 수 있는데, ^M의 존재가 이러한 에러의 원인이 되는 경우가 있다. 에러가 왜 발생하는지를 알기 위해서 먼저 아래 내용을 이해하자. (*개행문자 = 줄바꿈 문자) DOS(도스) 개행문자 = 윈도우 개행(Newline)문자 = \r\n = CR + LF = 캐리지리턴 + 라인피드 = Window EOL UNIX(유닉스) 개행문자 = 리눅스 개행문자 = \n = \LF(라인피드) = Unix EOL 위와 같이 서로 다른 환경에서는 개행문자 표현이 다르다는 것을 알 수 있다. 표현이 다르기 때문에 윈도우의 파일의 내용을 리눅스에서 제대로 이해할 리가 .. 2020. 10. 8.
트리(tree) 기본 구현 * 객체지향 프로그래밍으로 트리를 구현함 class Node: def __init__(self, value): self.value = value self.left = None self.right = None class NodeMgmt: def __init__(self, head): self.head = head def insert(self, value): self.current_node = self.head while True: if value < self.current_node.value: if self.current_node.left != None: self.current_node = self.current_node.left else: self.current_node.left = Node(value).. 2020. 10. 8.

티스토리툴바