알고리즘 학습을 위한 기초지식 - 자료구조(2)

배열 / 리스트 

1) 배열의 정의

배열 : 동일한 자료형을 갖는 여러 개의 데이터를 하나의 변수로 모아 놓은 데이터의 집합체
이 때 하나의 변수는 원소와 인덱스로 구성되는데, 
원소는 자료 집합체에서 각 원소의 항목 값인 데이터를 의미하며, 인덱스는 위치를 가리키는 숫자로
자료 집합체에서 각 원소가 저장된 방을 접근하기 위한 방 번호에 해당하는 것

2) 배열의 활용

배열은 크게 1차원 배열과 다차원 배열로 나뉜다.

1차원 배열에서는 1개의 첨자를 사용한다. 
배열의 원소들은 컴퓨터가 가지고 있는 메모리의 연속적인 기억공간에 나뉘어 순차적으로 저장

2차원 배열은 2개 이상의 첨자들을 가지는 배열이며구현이 간단한 장점이 있다.
2차원 배열부터는 배열을 저장할 때 행 우선 저장, 열 우선 저장으로 나뉨
-행 우선 순서 저장 : 첫 행에 있는 각 열의 원소를 차례대로 컴퓨터 메모리에 저장하고 다음 행으로 이동하여 각 열에 있는 원소부터 차례대로 컴퓨터 메모리에 저장하는 방식
-열 우선 저장 : 첫 열에 있는 각 행의 원소를 차례대로 컴퓨터 메모리에 저장하고 다음열로 이동하여 각 행의 원소를 차례대로 컴퓨터 메모리에 저장하는 방식

 

3) 연결리스트의 정의

리스트는 배열과 다르게 데이터를 담고 있는 공간을 추가로 저장 또는 삭제
리스트는 인덱스를 가지지 않고 데이터가 순차적으로 저장된 집합

리스트는 구현에 따라 선형리스트와 연결리스트로 나뉜다.

- 선형리스트(순서 리스트) : 1개 이상의 원소들이 순서를 가지고 구성되는 구조
1:1 관계의 개념을 갖고 있으며 a = (a1,a2, ... an) 과 같이 표현할 수 있다. 
또 논리적인 순서와 물리적인 순서가 동일 (ai 는 i번째 원소를 나타내고 an의 n은 리스트의 크기가 됨) 
=> 논리적인 순서와 물리적인 순서가 동일하기 때문에 1차원 배열을 이용해서 구현.

- 연결리스트 : 노드 간의 포인터 연결을 통해서 구현되는 리스트인데, 
(노드는 데이터링크를 통합해서 부르는 하나의 집합)
노드는 원소 값을 저장하는 데이터 필드와 다른 노드의 연결을 위한 포인터가 저장된 링크 필드를 가진다.
연결리스트의 다른 점은 선형리스트의 논리적인 순서만 지원.
연결리스트는 시작은 head 에 두고, 마지막 노드는 null 가리킨다.

 

4) 리스트 간의 장단점

• 선형리스트가 갖는 장점
  - 순차적인 구조를 가지고 있어 1차원 배열로 간단하게 구현가능
  - 또 각각의 값을 동시에 접근하고 싶을 때 배열은 순차적 접근이 아닌 직접 접근으로 원하는 위치에 비교적 빠르게 접근할 수 있다.
• 단점
  - 이런 구조로 인한 단점은 삽입과 삭제가 많은 경우가 발생하게 되면,
  - 삽입, 삭제를 할 때마다 논리적인 순서를 맞춰줘야 하고 결국 데이터의 이동이 많아지기 때문에 구현이 어려워지게 된다.
• 연결리스트가 갖는 장점
  - 이런 경우에는 포인터를 사용하며 노드 간의 연결을 통해서 구현되는 연결리스트를 사용하면 용이하게 삽입과 삭제를 할 수 있다. 
  - 연결리스트는 선형리스트의 논리적 순서만을 지원하고 메모리상의 물리적인 순서가 논리적인 순서와 다르기 때문에 삭제나 삽입 시 이동하고자 하는 노드의 링크만을 넣어서 삽입하면 간단하게 처리할 수 있다.
• 단점
  - 연결리스트는 선형리스트와 반대되는 장단점을 가진다. 연결리스트에서 찾고자 하는 데이터가 n 번째라면 직접 접근이 아닌 순차적 접근을 하기 때문에 접근속도가 오래 걸릴 수 있다.
  +)  
• 단일 연결리스트(단방향) : 특정 노드에서 찾고자 하는 노드가 선행 노드일 때 특정 노드에 표시한 후 처음부터 다시 찾아가게 되는 단점이 있다. null 값을 없애고 첫 번째 노드를 가리키게 하면 첫 번째로 원형 연결 리스트가 된다. 원형으로 돌아 다시 첫 노드로 접근하는 특징은 있지만, 많은 차이는 없음
• 양방향인 이중 연결 리스트 : 이런 점을 보완한 이중 연결리스트는 1개의 노드에 2개의 링크가 선행 노드, 후행 노드를 연결하고 있어 움직임에 제약이 덜한 장점

 

전위 순회 / 중위 순회 / 후위 순회 

D - 현재 노드를 방문해서 데이터를 읽는 작업 

L - 현재 노드의 왼쪽 서브트리로 이동하는 작업 

 R - 현재 노드의 오른쪽 서브트리로 이동하는 작업

1) 전위 순회(Preorder) : 전위 순회는 D-L-R의 순서로 노드를 방문한다. 이진트리의 모든 노드들을 DLR의 순서로 전부 방문한다. 현재 노드이자 루트 노드인 A를 순회 한 후 왼쪽 서브트리를 방문하고 마지막으로 오른쪽 서브트리를 방문하는 순서이다. A를 순회 했다면 왼쪽 서브트리로 넘어가게 된다. 이 때 B가 루트 노드로 있는 모든 서브 트리들을 전위 순회 한다. 루트 노드가 된 B를 순회하고 B의 왼쪽 서브트리 D로 이동한다. B의 오른쪽 서브트리인 E를 순서대로 순회하면 A의 왼쪽 서브트리 순회는 끝이 나고 A의 오른쪽 서브트리로 넘어가서 똑같은 과정을 반복한다. 

위 이진트리의 전위 순회 결과는 A->B->D->E->C->F 

 

2) 중위 순회(Inorder) : 중위 순회는 L-D-R의 순서로 노드를 방문한다. 루트 노드가 A이므로 A의 왼쪽 서브 트리인 B를 먼저 순회 후 루트 노드 A를 순회, 마지막으로 C의 서브 트리를 순회 하는 순서이다. 먼저, 왼쪽 서브트리로 이동하여 B가 루트노드이자 현재노드(D)가 되고, D가 왼쪽 서브 트리(L)가 된다. 그러므로 D를 가장 먼저 순회 한 뒤, B를 순회하고 오른쪽 서브 트리인 E를 순회한다. 루트 노드의 왼쪽 서브 트리 순회가 끝났으니 A를 순회하고 오른쪽 서브트리로 넘어가서 재귀적으로 방문한다. 이제 C가 현재 노드(D)가 되었으니 왼쪽 서브트리 F를 먼저 순회하고 가장 마지막으로 C가 순회되고 작업은 끝난다.

위 이진트리의 중위 순회 결과는 D->B->E->A->F->C 

 

3) 후위 순회(Postorder) : 후위 순회는 L-R-D의 순서로 노드를 방문한다. 현재 노드이자 루트 노드인 A를 가장 나중에 순회 한다. 왼쪽 서브 트리에서 B가 루트가 되는 서브 트리들을 LRD의 순서로 순회한다. 순서를 따르면 D, E를 차례로 순회하고 B를 순회한다. 왼쪽 순회 작업이 끝났으므로 A의 오른쪽 서브 트리를 후위 순회하는 작업을 반복한다. 오른쪽 서브트리의 순회가 끝나면 마지막으로 원래의 루트 노드인 A를 순회한다.

위 이진트리의 후위 순회 결과는 D->E->B->F->C->A 

 

깊이 우선 탐색과 너비 우선 탐색

(탐색은 정점 A에서 시작한다. 같은 수준의 여러 노드 중에서 다음 노드를 선택할 경우에는 알파벳 정렬 순서가 앞선 것을 우선 선택)

1) 깊이 우선 탐색(Depth first search)

깊이 우선 탐색이란 최근의 방문하지 않은 인접 정점을 우선적으로 방문하는 것으로 정점 A에서 시작한다면, A에서 도달할 수 있는 정점은 B 또는 C이나 B가 알파벳 정렬 순서가 앞서기 때문에 B를 방문 한다. B에서 인접한 정점 D, E 중 D로 방문하고 나면 D와 더 이상 인접한 정점이 없기 때문에 다시 탐색했던 B로 되돌아가서 방문하지 않은 최근의 인접한 정점인 E를 방문한다. E는 방문하지 않은 최근 정점은 G이므로 G, G는 F, F는 C로 더 이상 수행할 수 없을 때 까지 반복한다.

위 그래프의 깊이 우선 탐색의 결과는 A->B->D->E->G->F->C 

 

2)너비 우선 탐색(Breadth first search)

너비 우선 탐색이란 방문하지 않은 가장 오래된 주변 정점을 우선적으로 방문하는 탐색이다. 시작점 A를 중심으로 인접한 정점은 B와 C이나 알파벳 정렬 순서는 B가 우선이므로 B로 이동한다. B에서 이동할 수 있는 정점은 C,D,E 총 세 곳이 되지만 가장 오래된 정점인 C를 우선적으로 탐색한다. C로 이동하게 되면 F 또한 주변정점이 된다. 하지만 가장 오래되고 알파벳 정렬이 우선인 D로 먼저 이동한다. 같은 순서로 모든 노드를 방문할 때까지 탐색한다.

위 그래프의 너비 우선 탐색 결과는 A->B->C->D->E->F->G