교대최소제곱법

파이썬 라이브러리는 어떻게 구현할까? 무조건 작은 숫자가 0번 인덱스, 1번이 트리의 루트는 고정이다. 그리고 부모가 인덱스 k일 때 2k의 값은 2k+1보다 크다는 공식을 통해 구현된다 + 23.11.14 왜 트리의 루트를 0번 인덱스부터 시작하지 않을까? 루트를 1에서 시작하면 부모 노드를 찾을 때 단순히 i // 2만 해주면 되는 반면 루트를 0에서 시작하면 (i-1) // 2를 해야하는 번거로움이 있다. 삽입 연산은 → heappush 가장 마지막 인덱스에 값을 넣고 (현재 인덱스) // 2로 부모 인덱스를 찾아서 비교한다 이때 비교의 기준이 작은 것이 올라가면 최소힙, 큰 것이 올라가면 최대힙이 된다. 삭제 연산은 → heappop 파이썬 같은 경우 이미 하나를 빼서 0번 인덱스에 넣어놓는다 0..

B- tree가 무엇인가? 자료구조 중 하나 이진트리와 다르게 하나의 노드에 최대 M개의 자식을 가지는 트리 예를들어 값이 [10, 20]이 있으면 10보다 작은 서브트리, 10과 20 사이의 서브트리, 20보다 큰 서브트리 이렇게 3개의 자식이 생기는 트리가 B-트리이다. 삽입의 경우 M개의 제한을 걸어두고 값이 M개 이상이 되면 (노드는 최대 M-1개 까지 값을 가질 수 있다) 분할이 이루어진다 분할 과정은 가운데 값이 부모 노드로 올라가서 합쳐지는 방식으로 부모노드도 초과할 경우 계속 올라가는 방식으로 삽입이 진행된다 삭제는 더 어렵다, 자세한 것은 블로그 참조 [자료구조] 그림으로 알아보는 B-Tree [자료구조] 그림으로 알아보는 B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은..

해시 함수란? 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다. → 데이터를 효율적으로 관리하기 위한 방법 + 해시값(hash value) = 해시 코드(hash code) = 다이제스트(digest) = 해시(hash) 그럼 해시 테이블은? 바꾸기만 하면 의미가 없기 때문에 키와 값을 연결해 놓은 테이블이다. 왜 쓰나요? 무결성 검사, 비밀번호 저장 같은 보안이 필요한 경우 사용 해시 테이블의 종류 Direct Addressing Table 가장 간단한 해시테이블, 최대 키 값만큼 리스트를 만들어서 기억하는 방식 (DP에서 활용하는 방식) → 메모리 낭비가 심하다 Hash ..

자료구조 종류 배열(리스트) 링크드 리스트 스택 큐 우선순위 큐 그래프 인접 행렬 그래프 → 2차원 배열 지도나 행렬이 주어졌을 때 ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 인접 리스트 그래프 → 링크드 리스트 일부 간선의 정보만 주어졌을 때 ex) [(a, b, d1), (a, c, d2), (b, d, d3)] 트리 이진트리 힙 트리의 변형으로 최대, 최소 값을 찾기 위해 고안됨 → 우선순위 큐 해쉬 + 해쉬와 링크드 리스트 링크드는 리스트 안에 각자 다음 노드를 표시해 놓는 것 해쉬는 키와 밸류를 이어 놓은 테이블을 따로 생성하는 것 정렬 종류 선택 정렬, selection sort 전체를 순회하면서 가장 작은 값을 저장해서 순회가 끝났을 때 저장 시간복잡도 무조건 O(n..