Chap13 그래프의 응용 1. 스패닝 트리 (신장트리) 원래 그래프의 노드는 모두 포함. 간선은 최소로, 연결그래프를 유지하며 노드수-1개로 줄인 트리. 사이클 없음. 종류 깊이 우선 스패닝 트리 : dfs로 방문한 간선들로 만듦 너비 우선 스패닝 트리 : bfs로 방문한 간선들로 만듦 2. 최소 스패닝 트리 간선의 가중치(비용) 합을 최소로 하는 스패닝 트리 구하는 방법 종류 Kruskal 알고리즘(간선 수 e) 모든 엣지들 중 비용이 최소인 엣지들부터 추가해가며 사이클이 만들어지지 않도록 추가여부를 선택함 엣지를 크기순으로 정렬해두고 써도 되지만 min heap을 만들어 사용하면 더 효율적. 이 경우 heap구성시간 O(e) + 최소 엣지 탐색 시간 O(loge) = O(e+loge)소요. Prim..
DSA/Data Structure
Chap12 그래프, 그래프 탐색 1. 그래프의 개념 그래프 G1의 노드 V(G1) = {0,1,2,3,4} 그래프 G1의 간선 E(G1) = {(0,1) ..} ()는 무방향. {..} 는 방향이 있는 간선. G1은 방향그래프. 분리된 그래프 : 모든 루트가 연결되어있지 않고 분리되어있지만 하나의 그래프임. 연결된 그래프 용어 정리 완전 그래프 : 간선 수가 최대. 모든 각 노드에 모든 노드로의 간선이 존재. 완전그래프인 방향그래프에 n개의 노드가 있으면 간선의 수는 n(n-1), 무방향이면 n(n-1)/2 인접 : 두 노드를 직접 연결하는 간선이 존재하면 두 노드는 인접하다고 함 부속 : 두 노드를 직접 연결하는 간선이 존재하면 그 간선에 양쪽 노드가 부속된다고 함. 부분 그래프 : 그래프의 간선들과..
Chap11 검색(탐색) 선형 검색 앞에서부터 하나씩 찾아봄 이진 검색 절반씩 잘라서 중간값을 탐색해나가는 방법 해시 탐색 해시테이블(크기 = 버킷*슬롯) 버킷 : 해시될 키 값의 범위. 해시함수에 들어갔다 나온 값이 같으면(동의어) 같은 버킷에 저장됨 슬롯 : 같은 버킷에 저장될 수 있는 키 값 개수 충돌 : 동의어가 나타나서 다른 값이 같은 버킷에 저장되는 경우 오버플로우 : 충돌로 저장하려는 값의 슬롯이 이미 꽉 찬 경우 오버플로우가 일어남 식별자밀도=적재밀도 : 같은 말. 테이블 크기에 비해 저장된 데이터 수 비율을 의미.(키값=식별자=데이터) 해시 함수 : 계산이 편해야 하고 충돌을 최소화할 수록 좋음. mid-square : 식별자를 제곱해서 가운데 부분 값을 사용함 division : 나머지..
Chap10 정렬 선택 정렬 첫번째 자리에 올 값, 두번째 자리에 올 값.. 순서로 탐색해서 발견 시 해당 위치의 값과 자리 교환 비교 n(n-1)/2 회 교환 n-1 회 => O(n^2) 버블 정렬 맨 첫 값부터 바로 옆 값과 비교해 교환할지 말지 결정. 끝까지 가면 마지막 값부터 정렬 완료됨. 반복 비교 n(n-1)/2 회 교환 n(n-1)/2 회 (최악 : 비교할 때마다 교환) => O(n^2) 개선 - 중간 단계에서 정렬 완료된 경우. 현 단계에서 데이터 이동이 일어나지 않으면 다음 단계들을 수행하지 않고 종료 삽입 정렬 앞에서부터 현재 값을 앞쪽이 이미 정렬되어있는 값들 사이의 알맞은 위치에 삽입함(삽입하는 과정은 현재 위치에서 바로 앞 값과 비교해서 교환 결정하며 앞쪽으로 보냄. 계속 비교 교..
Chap8 트리 트리 삽입삭제가 편함 이진검색의 장점을 이용해 빠른 검색 가능 루트의 레벨 = 1 차수 : 노드의 부속트리 개수. 리프노드는 차수가 0임 부모, 자식, 조상, 자손 관계 등.. 트리 저장(구현)방법 n-링크표현법 모든 노드에 무조건 n개의 링크를 두고 각 자식노드의 링크를 저장함(남는 공간 있음) 왼쪽자식노드-오늘쪽형제노드 표현법 모든 노드에 링크 두개씩. - 효율적 왼쪽링크에는 첫번째 자식노드, 오른쪽 링크에는 자신의 형제노드를 연결함 차수가 n인 어떤 트리라도 이 방법을 이용하면 이진트리형태로 저장해 낭비되는 공간을 줄일 수 있음(간선을 다시 그리고 시계방향으로 45도 정도 돌림) 이진트리 자식노드의 수가 2개 이하(0~2개)인 트리 자식노드에 순서가 있음 - 똑같이 자식노드가 1개라..
