Computer Science34 이진 탐색 트리 (Binary Search Tree) - 탐색, 삽입, 삭제 이진 탐색 트리(Binary Search Tree) - 각 노드의 왼쪽 subtree의 key 값은 노드의 key 값보다 작거나 같아야 하고 - 각 노드의 오른쪽 subtree의 key 값은 노드의 key 값보다 커야 한다. - 모든 노드에서 만족해야 함. search 연산에서 장점이 있음 O(h) -> 높이를 적정하게 유지하는 것이 중요. class BST: def __init__(self): self.root = None self.size = 0 def __len__(self): return self.size def __iterator__(self): return self.root.__iter__() # yield def find_loc(self, key): # key 값 노드가 있다면 해당 노드 r.. 2022. 1. 2. 이진트리 - 정의와 순회 이진트리를 노드와 링크를 통해 직접 구현하도록 한다. key, left, right, parent class Node: def __init__(self, key): self.key = key self.parent = None self.left = None self.right = None def __str__(self): return str(self.key) 이진트리 순회(trabersal) 1. preorder (전위) 2. inorder (중위) 3. postorder (후위) preorder -> MLR inorder -> LMR postorder -> LRM preoder : F B A D C E G I H inorder : A B C D E F G H I postorder : A C E D B H.. 2022. 1. 1. 힙 자료구조 - insert 연산 1. 힙의 모양성질 만족 2. 모든 부모의 key가 자식의 key 보다 커야함 이러한 힙에서 만약 14가 들어오고자 하면, 새로 들어온 14 때문에 힙 성질을 만족하지 못한다. 따라서 이를 적절히 변경해줘야 함. 14를 위로 올려 보내면서 자기 자리를 찾도록 해야 한다. def insert(14): A.append(14) A.heapify(9) # up # A[k]를 root 방향으로 이동하면서 heapify def heapify(k): # A[k]를 heapify # 아직 루트에 도달하지 않았고, 부모의 key 값이 나보다 작을 때 while k > 0 and A[(k-1)//2] < A[k] : A[k], A[(k-1)//2 = A[(k-1)//2], A[k] k = (k-1)//2 참조 - http.. 2022. 1. 1. 힙 자료구조 - make heap 연산 https://hkim-data.tistory.com/187 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 이전 포스팅에 이어서 make heap 연산에 대해 알아보자 힙 성질을 만족하기 위해, heapify - down을 계속해서 진행하면 된다. 리스트의 맨 오른쪽 인덱스부터 A[0]까지 계속해서 반복 1. 리프노드면 내버려둠 2. 자식 노드가 있을 때 나보다 클 때 A [2*k+1]과 A [2*k+2] 값 중 큰 것이랑 변경 3. 변경 후 리프 노드가 아니면 또 아래랑 비교해줘야 함 def make_heap(A.. 2022. 1. 1. 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다. H[k] - 왼쪽 자식 노드 : H[2*k+1] - 오른쪽 자식 노드 : H[2*k+2] - 부모 노드 : H[(k-1) //2] 힙 (heap) : 힙 성질(heap property)를 만족하는 이진트리 힙 성질 1. 모양이 힙의 형태 (왼쪽부터 채운 형태) 2. 모든 부모 노드 키값은 자식 노드 키값보다 커야 함 힙의 루트노드에서는 가장 큰 값이다. A[0] 제공연산: 1. insert : O(logn) 2. find-max : return A[0] - O(1) 3. delete-max : O(logn) 참조 - .. 2021. 12. 31. 트리 자료구조 (용어 설명 및 표현법) 순차적 자료구조 : 배열, 연결 리스트 트리는 부모와 자식의 형태로 나타내는 자료구조 - 연결 리스트는 자식이 최대 1까지 있는 특수한 형태의 트리 자식이 최대 2개까지 있는 경우 이진트리(binary tree) 경로(path) : ex 3에서 12로 갈 때 3 -> 2 -> 7 -> 8 -> 12 경로 길이 (path length) = 4 (경로상의 에지 개수) 이진트리를 코드상에서 저장 표현법 3 : Class 활용 참고 - https://www.youtube.com/watch?v=w-1w4ood7Bc&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=20 2021. 12. 31. 해시 테이블 - collision resolution method 해시 함수에 의해 특정 인덱스 값이 정해지게 되면 c - universal function이기 때문에 충돌이 발생할 수 밖에 없다. 충돌이 발생했다는 것은 내가 삽입하려고 하는 슬롯에 이미 다른 key value 데이터가 저장되어 있는 것. 그럼 다른 어느 곳에 저장해야 될까? 에 대한 것을 collision resolution method이다. 대표적인 방법 중 하나 Open addressing인데 그 방식은 3가지로 나눌 수 있다. 1. linear probing - 한칸씩 2. quadratic probing - 제곱칸씩 3. double hashing - 해시함수 두개 set 함수 : key 값이 해시테이블에 있으면 update하고 아니면 insert (upsert) set(key, value=N.. 2021. 12. 31. #5 python의 메모리 할당과 관리 (Garbage Collection) https://hkim-data.tistory.com/183 #4 python의 메모리 할당과 관리 (Class와 self) https://hkim-data.tistory.com/182 #3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 -.. hkim-data.tistory.com 지난 포스팅에 이어 이번엔 python의 가비지 컬렉션이 어떻게 동작하는지 알아보도록 하겠다. python에서는 가비지 컬렉션을 레퍼런스 카운팅을 통해 Number of references가 0이 될 때 메모리 할당을 해제.. 2021. 12. 30. #4 python의 메모리 할당과 관리 (Class와 self) https://hkim-data.tistory.com/182 #3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모.. hkim-data.tistory.com 지난 포스팅에 이어서 이번엔 class 수준에서 어떻게 메모리가 할당되고 삭제되는지 알아보자. 위와 같이 Car 클래스를 선언했다고 하자. Car 클래스에서는 생성자 init 메서드와 getWheels 메서드가 있다. main .. 2021. 12. 29. #3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + hkim-data.tistory.com 이전 포스팅에 이어 이제 실제 Stack과 Heap 메모리에서 어떻게 동작하는지 알아보자. 백그라운드 메모리 구성은 모든 프로세스가 일부 메모리와 함께 운영 체제에 의해 할당된다. 마찬가지로 python 인터프리터는 실행을 위해 메모리를 할당받는데, 이는 파이썬의 버전.. 2021. 12. 29. #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + 갑자기 머리 하얘짐 으로 대답을 제대로 못했다. 충격을 받고 다 hkim-data.tistory.com 이전 포스팅에 이어서 실제로 python에서 어떻게 메모리가 할당되고 해제되는지 알아보고자 한다. Everything is object in Python C에서는 x = 10을 실행하게 되면 x에 주소 값이 할당되고, 그 메모리에 10이라는 값이 들어간다. 그러나 python에서는 x = 10을 실행하게 되면 1. 10이라는 integer 객체가 메모리에 생성된.. 2021. 12. 29. #1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + 갑자기 머리 하얘짐 으로 대답을 제대로 못했다. 충격을 받고 다시 정리를 해야겠다는 생각이 들었다. 코드 영역 : 실행할 프로그램의 코드가 저장됨 데이터 영역 : 전역변수와 정적변수가 저장됨 힙 영역 : 사용자가 동적으로 할당하는 변수나 메소드가 저장된다. C 에서는 malloc 스택 영역: 지역변수나 매개변수가 저장된다. python에서는 Python memory manager 에 의해 메모리가 관리된다. Python 메모리 할당과 관리에 대해 기초적인 것을 다음 포스팅에서 정리 해 보겠다. 2021.12.29 - [Comuter Science] - #2 python의 메모리 할.. 2021. 12. 29. 제곱수, 2의 n 제곱인지 확인 제곱수인지 확인 def isSquare(n): return int(n ** 0.5) ** 2 == n 2의 n 제곱인지 확인 def isPowerOf2(n): return (n&(n-1))==0 2의 제곱은 비트로 나타낼 때 맨 왼쪽 비트만 1이고, n이 2의 제곱이라면 n-1 은 맨 왼쪽 비트가 0이고 그 오른쪽 비트들은 모두 1이게 됨. 따라서 n이 2의 거듭제곱이라면 n과 n-1을 and 연산 했을 때 0이 나오게 됨. 2021. 12. 29. 해시 테이블 해시 테이블은 매우 빠른 삽입, 삭제, 탐색 연산을 제공하는 자료구조 python에서는 dict를 사용 key와 value의 형태로 해시 테이블에 저장 ( 해시 테이블은 보통 배열을 사용, 이 슬롯의 크기를 m이라 함) 해시 테이블에 저장할 때 hash Function을 이용해서 특정한 인덱스(Hash Code)를 지정해주게 됨 python에서는 hash(key)를 입력하게 되면 특정 key가 출력됨 hash function 1. perfect hash function : 이상적인 h.f key -> slot 이 1:1로 매치됨 즉, collision이 발생하지 않음 -> 비현실적 2. universal hash function : x란 key 값과 y란 key 값이 있다고 했을 때 f(x) == f(y.. 2021. 12. 29. 양방향 연결 리스트 구현 https://www.youtube.com/watch?v=zWrFVf9_YTQ&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=16 교수님 자료를 보고 리뷰한 포스팅 단방향 연결 리스트의 단점 - 만약 tail 노드를 지우고 싶다고 했을 때, tail 노드를 안다고 하더라도 tail 노드 앞의 prev 노드를 알지 못하기 때문에 결국 head부터 끝까지 search 하며 찾아야 한다. O( n ) 시간 소요 - 이를 해결하기 위해 왼쪽 방향 오른쪽 방향의 양방향 연결 리스트가 필요하게 됨. - 단점 : 링크가 양쪽으로 있어서 복잡성이 증가함 Splice 연산 def splice(self, a, b, x) : 조건 1 : a ->.. -> b : a에서 앞으로 가다 보면 .. 2021. 12. 28. 이전 1 2 3 다음
