프로그래밍/자료구조14 Chapter14 그래프(Graph) 2018/03/07 - [프로그래밍/자료구조] - Chapter13 테이블(Table)과 해쉬(Hash) 14-1 그래프의 이해와 종류 그래프의 역사와 이야깃거리 버스와 지하철의 노선도, 출발지와 목적지를 정하면 그에 맞는 최적의 경로등 이러한 프로그램의 구현에 사용되는 것이 바로 그래프 알고리즘이다.그래프 알고리즘은 수학자 '오일러(Euler)'에 의해 고안되었다. 오일러는 1736년도에 그 유명한 '쾨니히스베르크의 다리 문제'를 풀기 위해서 그래프 이론을 사용하였다. "정점 별로 연결된 간선의 수가 모두 짝수이어야, 간선을 한 번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다." 정점 별로 연결된 간선의 수가 모두 짝수가 아니기 때문에 쾨니히스베르크의 다리에서는 처음 출발한 장소로 돌아오지 못하는.. 2018. 3. 8. Chapter13 테이블(Table)과 해쉬(Hash) 2018/02/28 - [프로그래밍/자료구조] - Chapter12 탐색(Search) 2 13-1 빠른 탬색을 보이는 해쉬 테이블탐색과 관련이 있지만 트리와 관련된 어떠한 것도 언급하지 않는다는 점이 구분된다. 테이블(Table) 자료구조의 이해 이AVL 트리의 탐색 연산이 O(log2n)의 시간 복잡도를 보이는 반면, 테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보인다. 표에 저장된 데이터가 키(key)와 값(value)이 하나의 쌍을 이룰때 '테이블'로 구분 짓는다. 자료구조의 '테이블'은 '사전 구조'라고도 불린다. 더불어 '맵(map)'이라 불리기도 한다. 좋은 해쉬 함수의 조건좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'라고도 말할 수 있다."좋은 해쉬 함수는 키의 일부분을 참.. 2018. 3. 7. Chapter12 탐색(Search) 2 2018/02/27 - [프로그래밍/자료구조] - Chapter11 탐색(Search) 1 12-1 균형 잡힌 이진 탐색 트리: AVL 트리의 이해이진 탐색 트리의 단점을 개선한 또 다른 이진 탐색 트리를 소개한다. 이진 탐색 트리의 문제점과 AVL트리 이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이진 탐색 트리는 균형이 맞지 않을 수록 O(n)에 가까운 시간 복잡도를 보인다.이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보인다. 이러한 탬삭 트리의 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 하며, 그 종류는 대략 다음과 같다.- AVL 트리- 2-3 트리- 2-3-4 트리- Red-Black 트리- B 트리 자동으로 균형을 잡는 AVL 트리와 균형 .. 2018. 2. 28. Chapter11 탐색(Search) 1 2018/02/23 - [프로그래밍/자료구조] - Chapter10 정렬(Sorting) 11-1 탐색의 이해와 보간 탐색단순히 탐색의 방법만을 열거하지 않는다. 탐색의 이해 "효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다. 그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'을 우선 고민해야 한다.' 보간 탐색(interpolation Search)- 정렬되지 않은 대상을 기반으로 하는 탐색 순차 탐색- 정렬된 대상을 기반으로 하는 탐색 이진 탐색 "이진 탐색처럼 그냥 중앙에서 탐색을 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작하자!" 탐색 키(Search Key)와 탐색 데이터(Search Data)보간 탐색의 구현이진 탐색의 경우 다음 문장을 통해서 탐색.. 2018. 2. 27. Chapter10 정렬(Sorting) 2018/02/20 - [프로그래밍/자료구조] - Chapter09 우선순위 큐(Priority Queue)와 힙(Heap) 10-1 단순한 정렬 알고리즘각각의 알고리즘이 갖는 특징에 관심을 두고 공부하는 것이 기억에 오래 남는다. 버블 정렬(Bubble Sort): 이해와 구현 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식 "정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내기!"왜 이름이 버블 정렬일까? 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어진 것이다. 버블 정렬(Bubble Sort): 성능평가 시간 복잡도에 대한 빅-오를 결정하는 기준은 '비교의 횟수'이다. 하지만 '이동의 횟수'까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고.. 2018. 2. 23. Chapter09 우선순위 큐(Priority Queue)와 힙(Heap) 08-1 트리의 개요스택, 큐와 같은 선형 자료구조들과 달리 트리는 비선형 자료구조이다. 트리(Tree)의 접근 "트리는 계층적 관계(Hierarchical 출처: http://ohdumak.tistory.com/ [오두막]2018/01/15 - [프로그래밍/자료구조] - Chapter08 트리(Tree) 09-1 우선순위 큐의 이해제목만 봐서는 앞서 구현한 '큐'를 확장하는 수준 같지만 '큐'의 구현과 '우선순위 큐'의 구현에는 많은 차이가 있기 때문이다. 우선순위 큐와 우선순위의 이해 앞서 공부한 '큐'의 핵심 연산 두 가지- enqueue 큐에 데이터를 삽입하는 행위- dequeue 큐에서 데이터를 꺼내는 행위 '우선순위 큐'의 핵심 연산- enqueue 우선순위 큐에 데이터를 삽입하는 행위- de.. 2018. 2. 20. 이전 1 2 3 다음
