패스트캠퍼스 챌린지 (17) 썸네일형 리스트형 패스트캠퍼스 챌린지 17일차 Ch11. 자료구조 - 힙 1. 힙 (Heap) 이란? - 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) - 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 - 힙을 사용하는 이유 - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 - 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛) 이 걸림 - 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 - 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수.. 패스트캠퍼스 챌린지 16일차 5-5-6. 파이썬 전체 코드 테스트 - random 라이브러리 활용 - random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴 - ex: random.randint(0, 99): 0에서 99까지 숫자중 특정 숫자를 랜덤하게 선택해서 리턴 6. 이진 탐색 트리의 시간 복잡도와 단점 6-1. 시간 복잡도 (탐색시) depth (트리의 높이) 를 h라고 표기한다면, O(h) n개의 노드를 가진다면, ℎ=𝑙𝑜𝑔2𝑛 에 가까우므로, 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛) 참고: 빅오 표기법에서 𝑙𝑜𝑔𝑛 에서의 log의 밑은 10이 아니라, 2입니다. 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬.. 패스트캠퍼스 챌린지 15일차 5-5. 이진 탐색 트리 삭제 코드 구현과 분석 5-5-1. 삭제할 Node 탐색 - 삭제할 Node가 없는 경우도 처리해야 함 - 이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고, 함수를 종료 시킴 5-5-3. Case 3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때) - 기본 사용 가능 전략 - 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다. - 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다. - 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함 - 경우의 수가 또다.. 패스트캠퍼스 챌린지 14일차 5. 5-4 이진 탐색 트리 삭제 - 매우 복잡ㅎ다. - 경우를 나누어서 이해하는 것이 좋다. 5-4-1. Leaf Node 삭제 - Leaf Node: Child Node가 없는 Node - 삭제할 Node의 parent Node가 삭제할 Node를 가리키지 않도록 한다. 5-4-2. Child Node가 하나인 Node 삭제 - 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다. 5-4-3. Child Node가 두 개인 Node 삭제 - 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다. - 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent가 가리키도록 한다. 5-4.. 패스트캠퍼스 챌린지 13일차 ch10. 자료구조 - 트리 1. 트리(Tree) 구조 - 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 - 실제로 어디에 많이 사용되나? - 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 - Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) - Root Node: 트리 맨 위에 있는 노드 - Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 - Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 - Child Node: 어떤 노드의 상위 레벨에 연결된 노드 - Lea.. 패스트캠퍼스 챌린지 12일차 6-3. 빈번한 충돌을 개선하는 기법 - 해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대 - ex) 만약 슬롯이 8개일때, 50%이상에 데이터를 저장해야 한다면 2배의 슬롯을 정의한다. - hash_table = list([None for i in rangen(16)]) - def hash_function(key): return key % 16: *참고) 해쉬 함수와 키 생성 함수 - 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음 - 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해쉬 알고리즘) - 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능 7. 시간 복잡도 - 일반적인 경우(Collision이 .. 패스트캠퍼스 챌린지 11일차 4. 자료 구조 해쉬 테이블의 장단점과 주요 용도 - 장점 - 데이터 저장/읽기 속도가 빠르다(검색 속도가 빠르다) - 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다. - 단점 - 일반적으로 저장공간이 좀 더 많이 필요하다 - 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다. --> 가장 큰 단점 --> 공간과 탐색 시간을 맞바꾼다는 얘기는 이 단점 때문. -주요 용도 - 검색이 많이 필요한 경우 - 저장, 삭제, 읽기가 빈번한 경우 - 캐쉬를 구현할 때 (중복 확인이 쉽기 때문이다.) 6. 충돌(Collision) 해결 알고리즘(좋은 해쉬 함수 사용하기) - 해쉬 테이블의 가장 큰 문제는 충돌(Collision)의 경우입니다. 이 문제를 충돌 또는 해쉬 충.. 패스트캠퍼스 챌린지 10일차 * 블록체인에서 해쉬 구조를 확장해서 사용함. * 검색에서 해쉬 테이블 구조가 보다 좋은 이유: 배열의 경우 Trump의 값이 들어있는 것을 1번부터 찾아야함. 해쉬의 경우에는 바로 찾을 수 있다. 1. 해쉬 구조 - Hash Table: 키에 데이터를 저장하는 데이터 구조 - 키를 통해 바로 데이터를 받아올 수 있기 때문에 속도가 획기적으로 빨라짐 - 파이썬 딕셔너리 타입이 해쉬 테이블의 예. key를 가지고 바로 data를 꺼냄 - 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용(공간과 탐색 시간을 맞바꾸는 기법) - 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음. 딕셔너리 타입을 사용하면 되기 때문 2. 용어 - 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것 --> 아무리.. 이전 1 2 3 다음
