Study/DataStructures
-
그래프Study/DataStructures 2017. 4. 28. 17:06
그래프 - 원소 간의 관계를 표현 -> 정점, 간선으로 이루어진 자료 구조 - 선형이나 트리로 표현할 수 없는 연결 구조를 표현할 수 있다. -> 비선형 자료 구조 - 그래프는 사이클이 있을 수 있다. / 트리에서는 사이클이 존재하지 않음. - 차수 : 정점에 연결된 간선의 수 -> 진출 차수 : 정점에서 나가는 간선의 수 -> 진입 차수 : 정점으로 들어오는 간선의 수 그래프의 종류 무방향 그래프 - 두 정점을 연결하는 간선의 방향이 없는 그래프 - 정점 A와 정점 B를 연결하는 간선 (A, B) = (B, A) 방향 그래프 - 두 정점을 연결하는 간선의 방향이 있는 그래프 - 정점 A와 정점 B를 연결하는 간선 A -> B : / B -> A : 완전 그래프 - 각 정점에서 다른 모든 정점을 연결한 ..
-
이진 트리Study/DataStructures 2017. 4. 28. 05:07
이진 트리 - 모든 노드의 차수를 2 이하로 제한한 트리 - 부모-자식 관계가 하위로 계속해서 이어지는 계층 구조 - n개의 노드는 n-1개의 간선을 가진다. - 높이가 h인 트리의 노드의 최소 개수는 h+1, 최대 개수는 이진 트리의 종류 - 완전 이진 트리 -> 높이가 h이고, 노드의 개수는 ~개 - 포화 이진 트리 -> 높이가 h일 때, 노드의 개수가 최대 노드 개수()이다. -> 공백 노드가 없기 때문에 노드를 더이상 추가할 수 없다. - 편향 이진 트리 -> 노드의 개수가 최소 개수이고, 왼쪽 또는 오른쪽 서브 트리만 가지고 있다. 이진 트리의 구현 1. 순차 자료 구조 - 배열 : 인덱스를 이용해 노드에 쉽게 접근 가능. 부모 노드와 자식 노드를 찾기 쉬움. - 완전 이진 트리의 경우, 메모리..
-
시간 복잡도Study/DataStructures 2017. 4. 28. 00:36
시간 복잡도 - 프로그램을 실행하여 완료하는데 걸리는 시간. - 컴파일 시간 + 실행 시간 - 컴파일 시간은 프로그램의 특성과 크게 관련 없음 -> 고정적인 시간 - 실행 시간은 명령문의 실행 빈도수 계산 -> 실제 실행 시간이 아닌 이유 : 실행하는 컴퓨터의 성능에 따라 달라질 수 있기 때문에. - 빅오 표기법, 세타 표기법, 오메가 표기법 -> 최악, 평균, 최선 - 빅오 표기법 -> 실행 빈도수를 구하고, n에 대한 항에서 계수를 생략하여 표시한다. -> log n < n < n log n < n^2 < 2^n 순으로 커진다.
-
순차 리스트 / 연결 리스트Study/DataStructures 2017. 4. 19. 20:03
1. 순차 리스트 - 논리적인 순서와 물리적인 순서가 같은 구조.- 메모리에 연속적으로 저장된다. ex) Array - 구현이 비교적 간단하고, 인덱스를 사용하여 랜덤 액세스가 가능하다. - 논리적인 순서와 물리적인 순서가 동일하기 때문에 삽입, 삭제가 되는 경우,물리적인 순서를 논리적인 순서에 맞추기 위한 데이터의 이동이 필요하다.(물리적인 순서를 맞추기 위한 오버헤드 발생) - 예를 들어, 1 ~ 10 까지의 데이터를 저장하고 있는 순차 리스트가 있다고 가정한다. 맨 앞의 1을 삭제한다면, 그 다음에 존재하는 2 ~ 9의 데이터가 하나씩 앞으로 당겨지는 이동이 발생한다. 반대로 3과 4 사이에 데이터가 삽입된다면, 4 ~ 10의 데이터가 뒤로 하나씩 이동해야 하는 일이 발생한다. 2. 연결 리스트 -..