분류 전체보기339 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. 2월 초대장 배포 (마감) i n v i t a t i o n 티스토리 초대장 + 남은 초대장 수 : 00 안녕하세요! 티스토리에 보금자리를 마련하시려는 여러분께 초대장을 배포해 드리려고 합니다. 나만의, 내 생각을, 내 기억을 담는 소중한 블로그를 만들고 싶다면 티스토리로 시작해보세요! 티스토리 블로그는 초대에 의해서만 가입이 가능합니다. 원하시는 분은 댓글에 E-mail 주소를 남겨주시면 초대장을 보내드립니다. 남겨주실 때에는 꼭 비밀댓글로 남겨주세요! 초대장을 보내드리고 바로 개설하시지 않으신 분들은 초대장을 회수할 수도 있으니 바로 개설해주세요!단, 복사 붙여넣기를 방지하기 위해 맨아래 사는 지역을 말씀해주세요! 단, 복사 붙여넣기를 방지하기 위해서 사는 지역을 꼭 적어주세요! 출처: http://ohdumak.tistor.. 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. 이전 1 ··· 41 42 43 44 45 46 47 ··· 57 다음
