반응형

IT 기술/DS & Algorithm 5

B 트리, B+ 트리 비교

1. B 트리, B+ 트리 개념 비교B 트리B+ 트리균형잡힌 m-차 트리로, 모든 노드에 키와 데이터를 저장하는 트리 구조B트리 확장 구조로, 리프 노드에만 실제 데이터 저장, 내부 노드는 인덱스 역할하는 구조 2. B 트리, B+ 트리 상세 비교 항목B 트리B+ 트리데이터 저장모든 노드리프 노드내부 노드 역할데이터 저장, 인덱스인덱스 역할리프 노드 연결없음linked list 연결검색 경로루트 -> 내부 노드루트 -> 리프범위 검색느림 (리프 간 연결 없음)빠름 (리프 간 연결)공간 효율적은 노드에 분산 저장인덱스는 작지만 리프는 큼장점- 삽입/삭제 처리 단순- 노드 수 작음- 검색/범위 검색 빠름- 정렬된 순서 유지 쉬움단점- 범위 탐색 비효율적- 내부 노드 변경 많음- 리프 노드가 커서 디스크 ..

A * 알고리즘

1. 다익스크라 알고리즘의 확장, A* 알고리즘의 개념- 시작점에서부터 현재 정점까지의 최단거리와 현재 정점에서 목표점까지의 추정잔여 거리를 활용해 최단거리 구하는 알고리즘 2. A * 알고리즘 개념도 및 계산 원리가. A * 알고리즘 개념도 나. A* 알고리즘 계산 방식비용 함수g(n)시작 노드에서 현재 노드 n까지 거리h(n)현재 노드 n에서 목표 노드까지 예상거리f(n)g(n) + f(n), 총 예상 비용계산 방식1시작 노드를 리스트에 넣고 탐색 시작2리스트에서 f(n)이 가장 작은 노드 꺼냄3현재 노드가 목표 노드면 경로 반환4이웃 노드의 g(n), h(n), f(n) 계산5더 나은 경로의 f(n) 리스트에 추가6리스트에 더 이상 더 나은 f(n) 없을 때까지 반복 3. A*, Dijkstra,..

스택, 큐의 자료 입출력 원리

1. Last-In, First Out, 스택정의모든 데이터의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조개념도- Top: 리스트의 끝으로 삽입과 삭제 발생- Bottom: Top의 반대쪽 리스트의 끝- Push: 스택에서 값을 삽입(입력)- Pop: 스택에서 값을 삭제(출력)입출력 원리# push stack.append('A') # top = 0 stack.append('B') # top = 1# pop top_item = stack.pop() # 'B' 반환, top = 0- append(): 끝에 데이터 추가 (top += 1)- pop(): 끝에 데이터 제거 (top -= 1) 2. First-In, First Out, 큐정의- 데이터를 한쪽 끝에서 삽..

Red-Black 트리

1. 자기 균형 이진 탐색 트리, 레드-블랙 트리 개념- 각 노드에 레드 또는 블랙 색상 속성이 부여된 이진 탐색 트리로 특정 규칙을 통해 항상 균형 형태를 유지하는 트리특징) worst-case guarantees, 실시간 처리에 유용 2. 레드-블랙 트리 개념도 및 규칙가. 레드-블랙 트리 개념도 나. 레드-블랙 트리 규칙번호조건설명1Root Property루트 노드는 모두 블랙이다2External Property모든 리프(NULL)은 블랙이다3Internal Property레드 노드의 자식은 항상 블랙이다4Depth Property노드에서 리프 노드까지 가는 모든 경로에는 동일한 블랙 노드가 있다 3. Double Red 해결 방법 Restructuring, Recoloring구분설명Restruc..

트리 순회

1. 트리구조의 노드 탐색 기법, 트리 순회의 개념- Node와 Edge로 구성된 트리 형태의 자료구조에서 모든 노드를 빠짐없이 한 번씩 방문하여 node를 탐색하는 방법특징) 검색 성능 예측 가능, 깊이 우선 순회, 너비 우선 순회 2. 트리 순회의 유형 및 탐색 매커니즘가. 트리 순회의 유형구분유형탐색 순서깊이 우선 순회(DFS)pre-order루트 -> 왼쪽 자식 -> 오른쪽 자식in-order왼쪽 자식 -> 루트 -> 오른쪽 자식post-order왼쪽 자식 -> 오른쪽 자식 -> 루트너비 우선 순회(BFS)level-order루트부터 레벨별 왼쪽 -> 오른 나. 트리 순회 매커니즘3. 코드 예제preorderinorderpostorderdef preorder(node): if node: ..

반응형