윤깡패 블로그

세그먼트 트리(Segment Tree) 자료구조 주어진 데이터의 질의값 구하기(구간 합, 최대・최소)나 데이터 업데이트를 빠른 시간 복잡도 안에서 수행하기 위해 고안해 낸 자료구조 * 더 큰 범위는 '인덱스 트리'라고 불린다. 세그먼트 트리 종류 구간 합 A[N] = A[2N] + A[2N + 1] 최대 A[N] = max(A[2N], A[2N + 1]) 최소 A[N] = min(A[2N], A[2N + 1]) 세그먼트 트리 핵심 이론 트리 배열의 크기 2ᵏ ≥ N을 만족하는 k의 최솟값을 구한 후 2ᵏ * 2를 트리 배열의 크기로 정의 (N : 데이터의 개수) [ 예시 ] N = 8의 경우, 2³ ≥ 8 ⇒ 배열의 크기 : 2³ * 2 = 16 시작 인덱스 : 2ᵏ [ 예시 ] k = 3의 경우 시작 ..

이진 트리(Binary Tree) 자료구조 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리 이진 트리의 종류 편향 이진 트리 노드들이 한쪽으로 편향돼 생성된 이진 트리 - 탐색 속도가 저하되고 공간이 많이 낭비된다. 포화 이진 트리 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리 완전 이진 트리 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 이진 트리의 순차 표현 1차원 배열의 형태로 표현 트리의 노드와 배열의 인덱스 사이 상관관계 (N = 노드 개수) 루트 노드 : index = 1 부모 노드 : index = index / 2 (제약 조건 : 현재 노드가 루트 노드가 아님) 왼쪽 자식 노드 : index = index * 2 (제약 ..

최소 신장 트리(Mininum Spanning Tree) 자료구조 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 신장 트리 * 신장 트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 그래프(Graph) 자료구조 그래프(Graph) 자료구조 그래프(Graph) 자료구조 노드와 노드 사이에 연결된 에지의 정보를 가지고 있는 자료구조 노드(Node) : 데이터를 표현하는 단위 에지(Edge) : 노드를 연결 에지 리스트(Edge List) 노드를 배열에 저장하 soobin0821.tistory.com 최소 신장 트리 특징 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없기 때문) N..

그래프(Graph) 자료구조 노드와 노드 사이에 연결된 에지의 정보를 가지고 있는 자료구조 노드(Node) : 데이터를 표현하는 단위 에지(Edge) : 노드를 연결 에지 리스트(Edge List) 노드를 배열에 저장하여 에지 표현 에지를 중심으로 그래프 표현 특징 + 구현하기 쉽다. - 특정 노드와 관련된 에지를 탐색하기는 쉽지 않다. ⇒ 노드 중심 알고리즘에는 잘 사용하지 않는다. 응용 문제 - 벨만-포드(노드 사이의 최단 거리를 구하는 알고리즘) 알고리즘, 크루스칼(최소 신장 트리를 찾는 알고리즘) 알고리즘 에지 리스트로 가중치 없는 그래프 표현하기 - 배열에 출발 노드, 도착 노드 저장 [ 예시 ] 1에서 2로 뻗어나가는 에지 : [1, 2] 4에서 5로 뻗어나가는 에지 : [4, 5] * 방향이..

스택(Stack) 자료구조 삽입과 삭제 연산이 후입선출(LIFO : Last-In First-Out)로 이뤄지는 자료구조 * 후입선출 : 가장 나중에 삽입된 데이터를 가장 먼저 삭제한다. ⇒ 삽입과 삭제가 한 쪽에서만 일어난다. - 새 값이 스택에 들어가면 top이 새 값을 가리킨다. - 스택에서 값을 빼낼 때 pop는 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다. 스택 용어 top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 top : top 위치에 현재 있는 데이터를 단순 확인하는 연산 큐(Queue) 자료구조 삽입과 삭제 연산이 ..

트리(Tree) 자료구조 노드와 노드가 에지로 연결된 그래프의 특수한 형태 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 정보의 단위 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리의 최상단 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 : 트리의 최하단 노드 (자식 노드가 없는 노드) 서브 트리 : 전체 트리에 속한 작은 트리 트리의 특징 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다. 데이터베이스 시스템이나..