기본적인 자료구조

자료구조(Data Structure)

• 단순 자료구조
• ex) Integer, Float, Char 등등...
• 복합 자료구조
• Stack,Queue,List,Graph 등등...

복합 자료구조

• 배열 구조와 연결된 구조
• 배열 구조
• 인접한 메모리 공간에 나열하는 구조
• 직접 접근(Direct Access)를 지원
• 연결된 구조
• 메모리 공간에 흩어진 자료들을 연결고리(Link)를 이용해 연결한 구조
• 순서 접근(Sequential Access) 방법을 지원
• 용량의 변경이나 항목의 추가 및 삭제가 쉬움
• 선형 구조와 비선형 구조
• 데이터들을 순서적으로 나열하여 저장하는 형태
• 데이터에 접근하는 방법에 따라 스택,큐,덱 등과 리스트로 나누어짐.

선형 자료구조(Linear Data Structure)

• 리스트(List) 또는 선형 리스트(Linear List)
• 항목들이 차례대로 나열되어 있는 선형 자료 구조
• 각 항목들은 순서 또는 위치(Position)을 가짐
• 어떤 위치에서도 항목의 삽입이나 삭제가 가능함
• 집합(Set)과의 다른 점
• 항목들 사이에 순서가 있다.
• 중복을 허용함.
• 스택(Stack)
• LIFO:Last-In First-Out
• 리스트에서 다른 통로는 모두 막고 한쪽만 열어둔 구조와 같음
• 일반적으로 열어둔 쪽을 스택 상단(Top)이라고 함
• 항목의 접근이 Top을 통해서 삽입(Push())과 삭제(Pop())이 발생하기 때문에 위치를 지정해 줄 필요가 없다
• 큐(Queue)
• FIFO:First-In First-Out
• 뒤(Rear)에서 데이터가 추가되고 앞(Front)에서 데이터가 하나씩 삭제되는 구조
• 리스트에서 다른 통로는 모두 막고 입력은 후단에서만 출력은 전단에서만 이루어지도록 제한한 구조
  따라서, 스택과 마찬가지로 삽입(Enqueue())과 삭제(Dequeue()) 연산에서 위치를 지정해줄 필요가 없다
• 우선순위 큐(Priority Queue)
• 우선순위의 개념을 큐에 도입한 자료구조
• 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조
• 삭제 연산에서 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어진다
  특별한 언급이 없으면 일반적으로 최대 우선순위 큐를 의미한다
• 우선순위 큐에선 특정 순간의 가장 우선순위가 높은 항목만 알 수 있으면 된다
  따라서 선형 자료구조로 보기 어려우며, 실제 가장 효율적인 우선순위 큐의 구현 방법은 트리 구조를 사용하는 힙(Heap)이다
• 그래프(Graph)
• 연결 된 객체들 사이의 관계를 표현할 수 있는 가장 복잡한 형태의 자료구조
• 수학적으로는 G = (V,E)로 나타내며, V(G)는 정점(Vertex)들의 집합을, E(G)는 간선(Edege)들의 집합을 의미함
• 정점은 객체(Object)를 표현하고, 간선은 객체들 사이의 관계를 나타낸다.
• 정점 A와 B를 연결하는 간선은 (A,B)와 같이 표현한다
• 그래프는 오직 정점과 간선의 집합이며, 시각적 표현은 이해를 돕는 역할만을 한다
• 그래프의 종류
• 무방향 그래프(Undirected Graph)
• 간선에 방향이 표시되지 않은 그래프
• (A,B)와(B,A)는 동일한 간선이다.
• 방향 그래프(Directed Graph)
• 간성에 방향성이 존재하는 그래프
• 화살표로 표시되며, 한 방향으로만 갈 수 있다
• 위상 정렬 문제에서 사용됨
• 가중치 그래프(Weighted Graph)
• 간선에 비용이나 가중치가 할당된 그래프를 의미하며, 네트워크(Network)라고도 한다
• 간선이 두 정점 사이의 연결 유무뿐만 아니라 연결강도까지 나타냄
• 최단거리, 최소비용 신장트리, TSP 문제 등에서 사용됨
• 그래프의 용어
• 인접 정점(Adjacent Vertex)
• 간선에 의해 직접 연결된 정점
• 정점의 차수(Degree)
• 정점에 연결된 간선의 수
• 무방향 그래프에서는 정점에 인접한 정점의 수를 의미함
• 방향 그래프에서는 진입 차수(In-Degree, 들어오는 간수의 수)와 진출 차수(Out-Degree, 외부로 나가는 간선의 수)로 세분화 됨
• 경로
• 간선을 따라 갈 수 있는 길
• 정점의 나열로 표시
• 경로의 길이
• 경로를 구성하는데 사용된 간선의 수
• 가중치 그래프의 경우 간선의 총 가중치의 합이 됨
• 단순 경로(Simple Path)와 사이클(Cycle)
• 경로 중에서 반복되는 간선이 없는 경로를 의미함
• 단순 경로의 시작 정점과 종료 정점이 같다면 사이클(Cycle)이라 함
• 연결 그래프(Connected Graph)
• 모든 정점들 사이에 경로가 존재하는 그래프
• 그렇지 않은 그래프를 비연결 그래프라고 함
• 트리(Tree)
• 사이클을 가지지 않는 연결 그래프
• 연결 그래프에서 사이클이 없으면 그래프의 임의의 두 정점을 연결하는 경로는 오직 하나뿐이다
• 완전 그래프(Complete Graph)
• 모든 정점 간에 간선이 존재하는 그래프
• 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n(n-1)/2가 된다
  ex) n=4이면 간선의 수는 4(4-1)/2 = 6이다
• 그래프의 표현
• 인접 행렬
• 정점들의 연결 관계를 가장 간단한 방법
• 정점의 개수가 n이라면 nxn 행렬이 필요함
  각 항목들은 행과 열에 해당하는 정점들 사이의 간선 정보를 나타냄
• 인접 리스트
• 트리(Tree)
• 트리(Tree) 또는 자유 트리(Free Tree)는 그래프의 일종으로 사이클이 없는 연결 그래프(Connected Acyclic Graph)이다
• 정점들중에 하나를 루트(Root)로 설정하면 루트를 가진(Rooted) 트리가 된다
• 트리에서는 정점(Vertex)라는 표현보다는 노드(Node)란 용어를 더 많이 사용함
• 직장의 조직도, 컴퓨터의 폴더 구조와 같은 계층 구조를 표현하기에 적절함
• 노드의 개수가 n이면 간선의 수는 반드시 n-1개이다
• 트리의 두 노드 사이에는 단 하나의 단순 경로가 있다
• 트리의 용어
• 루트(Root) 노드
• 계층 구조에서 가장 높은곳에 있는 노드
• 부모(Parent) 노드와 자식(Child) 노드
• 간선으로 직접 연결된 노드중에 상위노드와 하위 노드
• 형제(Sibling) 노드
• 동일한 부모 노드를 가진 노드
• 조상(Ancestor) 노드와 자손(Descendent) 노드
• 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드와 어떤 노드 하위에 연결된 모든 노드
• 단말(Terminal, Leaf) 노드
• 자식 노드가 없는 노드
• 자식이 있는 경우 비단말 노드
• 노드의 차수(Degree)
• 어떤 노드가 가지고 있는 자식의 수
• 트리의 차수
• 트리가 가지고 있는 모든 노드의 차수 중에서 가장 큰 차수
• 레벨(Level)
• 트리의 각층에 번호를 매기는 것
• 루트를 기준으로 한 층을 내려갈때마다 1씩 증가
• 트리의 높이(Height)
• 트리가 가지고 있는 최대 레벨
• 트리의 표현
• 임의의 개수의 자식을 가지고 있는 트리를 일반 트리라고 함
• 자식 노드의 개수가 항상 2개 이하인 트리를 이진 트리(Binary Tree)라고 함
• 집합(Set)
• 리스트와 비슷하지만 원소들 사이에 순서가 없고 중복을 허용하지 않음
• 어떤 위치를 가지지도 않고 일렬로 나열한다는 의미도 적용할 수 없으므로 선형 자료구조로 볼 수 없다
• 집합은 S={ elem0, elem1, elem2,...,elem(n-1)}과 같이 표현된다
• 가장 중요한 연산들은 어떤 원소가 집합 S에 속하는지 검사하는 연산과 두 집합의 합집합, 교집합, 차집합등을 구하는 연산들이다
• 집합의 구현 방법은 리스트, 비트벡터(Bit Vector) 등을 사용해서 구현할 수 있다
• 맵(Map)
• 맵(Map) 또는 딕셔너리(Dictionary)는 자료를 저장하고 탐색키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 탐색을 위한 자료구조
• 맵은 엔트리(Entry)라는 키를 가진 레코드(Keyed Record)의 집합이다
• 엔트리(Entry)는 키(Key)와 값(Value)으로 구성 됨
• 맵을 구현하는 가장 효율적인 방법은 해싱(Hashing)이다.
  해싱은 많은 공간을 이용해 탐색 효율을 높이려는 전략을 사용함