"자료구조" 관련 글 11

STL
자료구조 2015. 9. 4. 20:58
STL 이란?? STL은 C++언어의 표준 템플릿 라이브러리( Standard Template Libaray)의 약자이다.STL을 간단하게 말하면 일반적으로 많이 사용되는 자료구조와 알고리즘을 모은 라이브러리STL은 1994년에 표준 위원회에서 초안이 통과되어서 만들어졌다. STL중에서 가장 많이 사용하는 라이브러리는 컨테이너 라이브러리이다.컨테이너는 int나 float등의 기본 자료형이나 구조체, 클래스 같은 사용자 정의형을 담는다.STL의 컨테이너에는 list, vector, deque, map, set등이 있다. list의 특징 1. 고정 길이인 배열에 비해서 가변적이다. ( 연결 리스트는 동적으로 크기를 변경 할 수있다.2. 중간에 데이터 삽입, 삭제가 용이하다. 단점 배열에 비해서 데이터의 삽입..
A-star 알고리즘
자료구조 2015. 8. 26. 15:58
A* 알고리즘이란?? - 전산학 분야에 있어서 A* 알고리즘은 주어진 출발지 노드에서부터 목적지 노드까지의 최단 경로를 찾아내는 그래프/트리 탐색 알고리즘 중 하나이다. 초록색 : 시작점 검은색 : 장애물 빨간색 : 도착점 길찾기 순서 1. 시작점에서 검색 된 사격형을 열린목록에 추가한다. 2. 시작점 근처에 붙어있고 지나갈 수 있는 모든 사각형들을 본다. 그리고 그 지나갈 수 있는 사각형들을 열린목록에 추가한다. 추가된 각각의 사각형들에게 지점A를 부모사각형이라고 저장함 (부모사각형은 나중에 길을 찾으며 거슬러 올라갈 때 중요하다.) 3. 시작점을 열린목록에서 빼고 필요없는 사각형들을 닫힌목록에 추가한다. 위의 그림은 인접한 모든 노드를 검색한 후 열린목록에 추가된 그림을 보여주는데 8개의 방향으로 검..
AVL 트리
자료구조 2015. 8. 24. 18:30
AVL 트리의 개요 - AVL 트리는 G . M. Adelson-Velskii와 E.M. Landis에 의해 1960년대에 고안되었다.- AVL 트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 멋진 트리이다. 이진 탐색 트리의 문제점과 AVL 트리 이진 탐색 트리의 탐색 연산은 을 가진다.하지만 이진 탐색 트리는 균형이 맞지 않을수록 의 시간복잡도를 보인다.따라서 이진 트리 탐색은 저장 순서에 따라서 탐색의 성능에 큰 차이를 보인다. 그래서 이진 탐색 트리의 단점을 보완한 트리는 밑에 열거한 트리등이 있다. * AVL 트리* 2-3 트리* 2-3-4 트리* Red-Black 트리* B트리 AVL트리와 균형 인수(Balance Factor) ..
Red Black Tree
자료구조 2015. 8. 19. 15:50
순수한 이진 탐색 트리의 단점은 불균형하며 검색 효율을 심각하게 저하시킨다. 이런 이진 탐색 트리의 단점을 보완한 것이 레드 블랙 트리이다. 레드 블랙 트리에서 노드는 트리 전체의 균형을 유지할 수 있게 하는 아주 중요한 비결이다. 레드 블랙 트리의 규칙 1. 모든 노드는 Red아니면 Black이다. 2. 루트 노드는 검은색이다. 3. 잎 노드는 검은색이다. 4. Red 노드의 자식들은 모두 검은색이다. 하지만 Black 노드의 자식이 Red일 필요는 없다. 5. 루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다. 레드 블랙 트리의 잎 노드는 모두 NIL로 표시되어 있다. NIL 노드는 아무 데이터도 가지고 있지 않지만, 색깔만 검은색인 더미 노드이다. 왜 아무 데이터도 가지고 ..
이진 트리(Binary Tree)
자료구조 2015. 8. 17. 21:40
이진 트리(Binary Tree) 모든 노드가 최대 2개의 자식을 가질 수 있는 트리이다. 이 이진 트리는 일반 트리처럼 데이터를 담는 용도로는 사용하기 곤란하지만, 예를 들어 수식 이진 트리, 아주 빠른 데이터 검색이 가능한 이진 탐색 트리가 있다. 이진트리와 일반트리의 차이점 일반 트리는 한 노드가 N개의 자식을 가질 수 있는 트리구조이지만 이진 트리는 모든 노드가 최대 2개의 자식을 가질 수 밖에 없는 트리구조를 가지고 있다. 또한 일반 트리는 데이터를 담을 수 있지만 이진 트리는 수식을 계산하거나 아주 빠른 데이터 탐색을 할 수 있다는 점에서 차이가 있다. 이진 트리의 종류 포화 이진 트리(Full Binary Tree) - 모든 레벨의 노드들이 꽉 차있는 이진 트리 형태 - 잎 노드들이 모두 같..
admin

티스토리툴바