푸으름

Algorithm 공부 #20 - 이진 트리 이진 트리(Binary Tree) ● 각 노드의 자식 노드의 개수가 2개 이하인 트리 ● 편리하고 직관적인 자료구조 형태는 배열 ● 이진 트리의 종류 1. 편향 이진 트리 : 트리의 노드들이 한쪽 방향으로만 편향돼 생성된 트리, 탐색 속도가 저하되고 공간이 많이 낭비 2. 포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 모두 꽉 찬 트리 3. 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 ● 이진 트리의 순차 표현 1. 루트 노드 : index = 1; 2. 부모 노드 : index = index / 2; (단, 현재 노드가 루트 노드가 아닐 때) 3. 왼쪽 자식 노드 : index ..

Algorithm 공부 #19 - 트리 트리(tree) ● 노드와 에지로 연결된 그래프 ● 순환(cycle)구조를 가지고 있고, 1개의 루트 노드가 존재 ● 루트 노드를 제외한 모든 노드들은 단 1개의 부모 노드를 가짐 ● 트리의 부분 트리(서브 트리)역시 트리의 특징을 따름 ● 트리의 구성 요소 1. 루트 노드 : 트리에서 가장 최상단에 위치하는 노드 2. 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 위치하는 노드 3. 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 위치하는 노드 4. 리프 노드 : 자식 노드가 없는 가장 하위에 위치하는 노드 5. 노드 : 데이터의 index와 value를 표현하는 요소 6. 에지 : 노드와 노드의 연결 관계를 나타내는 선 7. 서브 트리 : 전체 트리에 ..

Algorithm 공부 #18 - 그래프(최소 신장 트리) 최소 신장 트리(minimum spanning tree) ● 그래프에서 모든 노드를 연결할 때 사용한 에지들의 가중치의 합을 최소로 하는 트리 ● 사이클이 포함되면 최소 가중치를 계산할 수 없으므로 사이클을 포함시키지 않는다 ● N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 N-1개 ● 최소 신장 트리 구현 방법 1. 에지 중심으로 저장하므로 에지 리스트로 그래프 표현, 사이클 표현을 위해 유니온 파인드도 함께 사용 2. 그래프를 가중치를 기준으로 오름차순 정렬 3. 가중치가 낮은 에지부터 연결하기(이때 바로 연결하지 않고 두 노드의 사이클 여부를 판단해야 함) 4. 사이클이 생성되지 않는다면 두 노드를 연결, 사이클이 생기면 연..

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜) 벨만-포드 알고리즘(Bellman-ford-moore Algorithm) ● 그래프에서 최단거리를 구하는 알고리즘 ● 음수 가중치 에지가 있어도 수행가능 ● 시간 복잡도 O(VE), 음수 사이클 여부 판단 가능 ● 벨만-포드 구현 방법 1. 에지 중심으로 동작하므로 그래프를 에지 리스트로 표현(tuple로 출발지점, 도착지점, 가중치 삽입) 2. 최단 거리 배열을 초기화(출발 지점은 0으로, 나머지는 무수히 큰 값으로 초기화) 3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(일반적으로 출발 노드), N-1번 에지 사용 횟수를 반복하기 4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트 최단거리 업데이트 ..