Study/Data Structure 썸네일형 리스트형 자료구조 전체 10.1 그래프란?10.2 그래프의 정의와 용어10.3 그래프의 표현 방법10.4 그래프의 탐색10.5 깊이 우선 탐색10.6 너비 우선 탐색 10.1 그래프란? 그래프(graph)- 연결되어 있는 객체 간의 관계를 표현하는 자료구조 - ex) 트리, 전기회로 소자 연결, 지도 도시 연결 오일러 정리 - 오일러 문제: 모든 다리 "한번씩만" 건너서 처음 출발 장소로 return - bridge = edge or link 간선- region = vertex or node 정점- 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재!! 따라서 이건 오일러 경로 존재 x 10.2 그래프의 정의와 용어 그래프 정의 - G = (V, E)정점 (vertices) = node= 여러가지 특성 가질 수 .. 더보기 [자료구조 스터디] chap.13 탐색 13.1 탐색이란? 13.2 정렬되지 않은 배열에서의 탐색 13.3 정렬된 배열에서의 탐색 13.4 이진 탐색 트리 13.5 AVL 트리 13.6 2-3 트리 13.7 2-3-4 트리 13.1 탐색이란? 탐색 - 여러 개의 자료 중에서 원하는 자료를 찾는 작업 - 탐색용 자료구조: 배열, 연결리스트, 트리, 그래프 - 탐색키 (search key): 항목과 항목 구별해주는 키 13.2 정렬되지 않은 배열에서의 탐색 순차탐색 (sequential search) - 가장 간단, 직접적 탐색 방법 - 정렬x sequence을 처음부터 마지막까지 하나씩 검사하는 방법 - 평균 비교 횟수 : 탐색 성공 => (1+2+...+n)/n = (n+1)/2번 비교 / 탐색 실패 => n번 비교 ==>> O(n) - 시간.. 더보기 [자료구조 스터디] chap.12 정렬 12.1 정렬이란? 12.2 선택 정렬 12.3 삽입 정렬 12.4 버블 정렬 12.5 쉘 정렬 12.6 합병 정렬 12.7 퀵 정렬 12.8 히프 정렬 12.9 기수 정렬 12.10 정렬 알고리즘의 비교 12.11 정렬의 응용: 영어 사전을 위한 정렬 12.1 정렬 정렬 - 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것 (자료 탐색에서 필수!) - 정렬 대상 => 일반적으로 레코드(record) ( 예를 들면 학생들이 레코드면, 학번 이름 등이 필드) - 레코드는 필드라는 보다 작은 단위로 구성되고 키필드(이름 등)로 레코드와 레코드를 구별 - 모든 경우에 최적인 정렬 알고리즘은 X - 정렬 알고리즘 평가 기준 => 비교 횟수 빈도, 이동 횟수 빈도 (빅오표기법으로) 분류1 - 단순, 비효율.. 더보기 [자료구조 스터디] chap.10 그래프 I 10.1 그래프란? 10.2 그래프의 정의와 용어 10.3 그래프의 표현 방법 10.4 그래프의 탐색 10.5 깊이 우선 탐색 10.6 너비 우선 탐색 10.1 그래프란? 그래프(graph) - 연결되어 있는 객체 간의 관계를 표현하는 자료구조 - ex) 트리, 전기회로 소자 연결, 지도 도시 연결 오일러 정리 - 오일러 문제: 모든 다리 "한번씩만" 건너서 처음 출발 장소로 return - bridge = edge or link 간선 - region = vertex or node 정점 - 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재!! 10.2 그래프의 정의와 용어 그래프 정의 - G = (V, E) 정점 (vertices) = node = 여러가지 특성 가질 수 있는 객체를 의미 - V.. 더보기 [자료구조 스터디] chap.11 그래프 II 11.1 최소 비용 신장 트리 11.2 Kruskal의 MST 알고리즘 11.3 Prim의 MST 알고리즘 11.4 최단 경로 11.5 Dijkstra의 최단 경로 알고리즘 11.6 Floyd의 최단 경로 알고리즘 11.7 위상 정렬 11.1 최소 비용 신장 트리 신장트리 (spanning tree) - 그래프 내의 모든 정점을 포함하지만 사이클은 아닌 트리 - n개의 정점 신장트리 -> n-1개 간선 - 적은 링크만 사용한다고 최소비용은 x -> 링크 구축 비용( 간선 가중치)까지 고려해서 최소 신장 트리 선택해야함 신장트리 알고리즘 depth_first_search(v): 1. v를 방문되었다고 표시; 2. for all u ∈ (v에 인접한 정점) do 3. if (u가 아직 방문되지 않았으면) 4.. 더보기 이전 1 다음
