자료구조

자료구조란 컴퓨터 상에 자료를 저장하기 위해서 만들어지 논리적인 틀이다.
자료구조에는 다음과 같은 것들이 있다.
크게 선형구조와 비선형구조로 나뉘는데

선형구조
- 리스트
  - 선형 리스트
  - 연결 리스트
    - 스택
- 큐
- 데크
비선형구조
- 트리
- 그래프

선형구조

선형 리스트

선형 리스트는 우리가 일반적으로 생각하는 배열이라고 생각하면된다. 메모리 상에서 연속적으로 위치해서 붙어있는 데이터 구조라서 각 데이터에 접근하는 속도가 월등히 빠르다.
선형 리스트의 단점은 데이터를 삽입하고 삭제하는데 번거롭고 데이터를 다 이동시켜야하기 때문에 이때는 그렇게 빠르지 않다는 점이다.

연결 리스트

이것도 배열의 형태인데 연속으로 배열시키지 않고 임의의 기억 공간에 기억을 시키되 각 노드의 포인터를 이용하여 서로 연결한 자료구조이다. 노드의 삽입, 삭제 작업이 선형 리스트보다 더 용이하다.
포인터를 써야 하기 때문에 기억공간을 더 필요로 한다. 그렇지만 선형리스트보다 자료를 검색하는 속도는 느릴 수밖에 없다.

스택

스택의 경우 LIFO(Last in First out) 형태의 자료구조이며 꺼낼때는 pop() 넣을때는 push()라는 메서드를 주로 프로그래밍에서 사용한다.

큐

스택과는 다르게 한쪽 끝에서는 넣고 다른 한쪽에서는 나오는 형태이다. 일방 통행 터널을 생각하면 편하다. 따라서 먼저 들어간 것이 먼저나오는 FIFO(First in First Out)의 형태를 띈다.

데크(deque)

큐와 같은 모양인데 큐는 일방 통행이었다면 양방향으로 나가고 들어오는 것을 모두 할 수 있는 자료구조를 말한다.

트리(tree)

트리는 데이터를 계층화 시킨 자료구조이다.
트리는 다음과 같이 두가지로 구성되어 있다.

노드
링크

가장 최상위에 있는 노드를 root node라고 한다. 그리고 다른 노드들은 그냥 노드들인데, 트리를 타고 쭉 내려가다보면 언젠가는 가장 밑에있는 자식이 없는 노드를 만난다. 그 노드들은 leaf node,한국말로 단말 노드라고 한다.
노드에서는 용어가 중요하다.

링크 : 노드를 연결하는 선
노드의 크기: 자신을 포함한 모든 자손 노드의 개수
노드의 깊이: 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨: 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수: 부(하위) 트리 개수 혹은 간선의 수
트리의 차수: 트리가 갖는 총 차수
트리의 높이: 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리의 성질

노드가 n개 있다면 링크는 항상 n-1개 있다.

트리의 순회 방법

중위(In Order)
전위(Pre Order)
후위(Post Order)

트리 순회방법을 활용한 수식표현법

전위 표기법(prefix)
중위 표기법(infix)
후위 표기법(postfix)

이진트리

각 노드는 2개의 자식노드를 가진다.
이진트리는 2가지 종류가 있다.
포화 이진트리 : 모든 레벨에서 노드들이 채워져있는 트리
완전 이진트리 : 마지막 레벨을 제외하고 모든 노드가 채워져있는 트리

그래프

트리가 노드와 링크로 구성되어있다면 그래프는 노드와 간선(Edge)로 구성되어있고 연결되어있는 객체간의 관계를 표현할 수 있는 자료 구조를 말한다.

그래프의 종류

무방향 그래프 : 정점을 연결하는 선에 방향이 없다.
방향 그래프 : 정점을 연결하는 선에 방향이 있다.
그래프는 중복을 허용하지 않고 2개 이상의 경로가 가능하다.
완전 그래프에서 무방향 그래프의 경우 n개의 정점이 있는 경우 최대 간선의 수는 n(n-1)/2이다. 방향 그래프의 경우에는 n(n-1)이다.

저작자표시 비영리 변경금지 (새창열림)