포털:고등학교/과학 계열 전문 교과/정보과학(2015 개정)/관계의 표현과 자료 구조

자료구조

다양한 문제 상황에서 사용하기 위한 프로그램을 작성하기 위해서는 현실에서의 다양한 자료들과 그 자료들의 관계들을 표현하고 저장하는 것으로부터 시작된다.

자료 구조 :자료들 사이의 관계를 저장하기 위해 고안된 구조

자료 구조의 효과 : 자료들 사이의 관계를 저장, 자료를 보다 효과적으로 다룰 수 있음

자료 구조의 설계 : 자료 구조와 함께 사용될 수 있는 고유한 알고리즘들과 함께 설계 또는 효율적으로 자료들을 다룰 수 있는 알고리즘을 위해 거꾸로 설계

자료 구조는 선형 자료 구조와 비선형 자료 구조로 구분 가능하다. 자료 구조를 이해하면 문제 상황에 따라 필요한 자료 구조를 사용해 빠르고 효율적인 자료 처리 가능하다.

선형 자료 구조 : 자료를 저장하고 접근하는 관계가 하나의 선으로 연결한 것처럼 구성되는 자료 구조

선형 자료 구조 예시 : 배열, 리스트 스택, 큐

리스트 : 하나의 연결 관계에 따라 자료들을 한 줄로 연결시킨 형태로 추상화된 자료 구조, 자료 저장을 위해 메모리상의 연속된 공간을 할당해야 한다는 점에서 배열과 유사

리스트 기본 코드: 1. list<char> L; : //문자리스트 L 선언 2. L.push_back('c'); : //리스트 L의 마지막에 'c' 추가 3. L.insert(3,'d'); : //시작 지점부터 세 번째 위치의 원소 앞에 'd' 삽입

리스트의 장점 : 1. 자료를 찾기위해서는 연결 관계를 따라 순차적으로 이동해 가야 하지만, 중간의 연결을 재구성하여 원하는 자료들을 삽입, 삭제하는 작업을 빠르게 할 수 있음. 2. 연속적이지 않은 공간을 논리적으로 연속적인 것처럼 사용할 수 있음.

리스트 연결 구조에서의 기본적인 자료 처리 알고리즘: 자료의 삽입과 삭제 삽입은 리스트의 특정 위치에 원하는 자료 넣는 것, 삭제는 특정 위치에서 자료를 지우는 것

리스트 자료 구조의 자료 처리 함수: 삽입에는 push_front(x), push_back(x)가 있는데 이는 각각 첫 번째 원소 앞에 자료 x 삽입, 마지막 원소 다음에 자료 x삽입을 의미한다. 삭제에는 pop_front(), pop_back()이 있는데 이는 각가 첫 번째 원소 삭제, 마지막 원소 삭제를 의마한다. begin(), end()는 각각 첫 번째 원소의 위치와 마지막 원소의 다음 위치를 의미한다.

스택 : 가장 나중에 입력된 자료에 가장 먼저 접근하고, 가장 먼저 저장된 자료에는 가장 마지막에 접근하도록 설계된 후입 선출(Last in, First out) 형태로 추상화된 자료 구조

스택 특징 : 1.나중에 저장된 자료를 먼저 사용할 필요가 있을 때 사용할 수 있는 후입 선출 형태의 자료 구조. 2. 자료들을 쌓아 올리는 자료 구조 3. 전에 저장된 자료에 접근하기 위해서는 그 자료 이후에 쌓아 올려져 있던 자료들을 먼저 제거 해야함. 4. 자료의 삽입과 삭제가 한곳에서만 이루어진다. 스택 기본 코드 : 1. stack<char> S; : //문자 스택 S 선언 2. S.push('d'); : //스택 S의 가장 위에 'd'추가 3. S.pop(); ://스택 S의 가장 위 자료 제거

스택 구조에서의 기본적인 자료 처리 알고리즘: 'push'와 'pop'이 있다. push는 스택의 가장 위에 원하는 자료를 추가하는 작업, pop은 스택의 가장 위 자료를 삭제하는 작업 예를 들어 push(x)은 스택 가장 위에 자료 x추가를 의미하고 pop()는 스택 가장 위에 있는 자료 삭제를 의미한다. 추가적으로 empty()는 스택이 비어 있는지 확인하는 것이고 top()는 스택의 가장 위 자료값이다.

큐: 먼저 입력된 자료에 가장 먼저 접근하고, 가장 나중에 저장된 자료에는 가장 마지막에 접근하도록 선입 선출(First in, First out)형태로 추상화된 자료 구조

큐의 특징: 1. 순서대로 자료들을 넣는 구조 2. 먼저 저장한 자료를 먼저 사용할 필요가 있을 때 사용할 수 있는 자료 구조 3. 자료가 삽입되는 곳과 삭제되는 곳이 다름. 4. 자료가 입력된 순서대로 자료를 접근해 사용할 수 있음.

큐의 기본 코드 : 1. queue<char> Q; : //문자 큐 Q 선언 2. Q.push('d'); : //큐 Q의 마지막에 'd'추가 3. Q.pop(); : //큐 Q의 처음 자료 제거

큐 구조에서의 기본적인 자료 처리 알고리즘 : 자료의 'push'와 'pop'이 있다. push는 큐의 가장 뒤에 원하는 자료를 추가하는 작업, pop은 큐의 가장 앞에 있는 자료를 삭제하는 작업 추가적으로 size()는 큐에 들어 있는 자료 개수를 empty()는 큐가 비어있는지 확인하는 가능을 한다.

비선형 자료 구조 : 자료들 사이에 하나 이상의 연결 관계를 가질 수 있는 자료 구조. 대표적으로 트리, 그래프가 있다.

비선형 구조를 표현하고 정의하는데 사용되는 기호: 노드/정점은 자료를 나타내는 원이다. 링크/간선은 연결 관계를 표현하는 선이며 양쪽 방향 연결은 ↔또는 -를 사용함. 한쪽 방향 연결은 단방향 화살표를 사용한다.

트리와 그래프 : 이 둘은 자료들 사이의 하나 이상의 연결 관계를 표현하는 의미에서는 같지만, 순환이 없는 위계 관계로 해석할 수 있는 경우는 트리, 순환이 있고 부모가 둘 이상이 있는 연결 관계로 표현되는 경우에는 그래프로 부른다.

자료의 연결 관계를 표현하는 트리와 그래프에 사용되는 기본적인 표현과 구분: 표현은 생략한다. 1. 노드가 없어도 트리이면서 그래프이다. 2. 부모이면서 자식이면 그래프이다. 3. 선형 리스트는 트리이면서 그래프이다. 4. 순환이 있으면 그래프이다. 5. 부모가 둘 이상이면 그래프이다. 6. 루트 노드가 둘 이상이면 그래프이다. 이들은 배열이나 리스트를 이용해 저장할 수 있다.

트리 : 자료들 사이의 계층적 연결 관계를, 자료를 저장하고 있는 노드와 그 사이의 관계를 링크로 표현하는 추상화된 자료 구조.

트리에서 사용되는 용어: 1. 자식 노드: 다른 노드로부터 연결된 노드. 2. 부모 노드: 다른 노드로 연결되어 나가는 노드. 3. 형제 노드: 같은 부모를 가진 자식 노드들. 4. 루트 노드: 최상위 부모 노드. 5. 단말 노드: 자식이 없는 노드. 5. 깊이: 루트 노드로부터 그 위치까지의 결로 길이. 6. 높이: 루트 노드로부터 가장 깊은 노드까지의 경로의 길이. 7. 차수: 자식 노드의 개수.

2진 트리: 트리의 모든 노드의 차수가 2이하인 트리

완전 2진 트리: 트리의 가장 아래층을 제외한 모든 노드가 채워진 2진 트리로서 가장 아래층의 노드들은 왼쪽부터 오른쪽으로 순서대로 채워져 있다. 정보과학에서 다루어지는 가장 간단한 트리로 트리를 구성하는 모든 노드가 2개 이하의 자식노드만 가진다.

루트 노드의 번호를 1번으로 시작해서, 위에서 아래로 왼쪽에서 오른쪽으로 순서대로 번호를 붙인, 높이가 k인 완전 2진 트리의 예는 대락적으로 다음과 같다

                          1:a
                    2:b         3:c
               4:d      5 :e  6:f   7:g
           8:h     9:i

높이가 k인 완전 2진 트리의 최대 노드의 개수는 2의 k+1승 - 1개 이고 n번 노드의 왼쪽 자식 노드의 번호는 2*n n번 노드의 오른쪽 자식 노드의 번호는 2*n+1 n번 노드의 부모 노드의 번호는 [n/2]이다.

2진 트리는 1차원 배열을 이용해 자료들을 저장하고 다룰 수 있는데, 1번 배열을 루트 노드로 하여 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 자료들을 저장하는 방법을 일반적으로 사용한다.

히프 : 완전 2진 트리를 기반으로 만들어진 것으로 모든 부모 노드가 그 자식 노드의 자료값보다 더 높은 순위의 자료값을 가지는 특성을 만족하는 특별한 구조를 말한다.

히프의 최상위 루트는 트리의 모든 노드의 값 중에서 가장 높은 순위를 가지는 값을 가지며 순서에 따라 최대 히프와 최소 히프로 구분하기도 한다.

히프를 만드는 방법: 여러가지가 있지만 기존에 만들어져 있던 히프의 마지막에 새로운 자료를 추가하고 추가된 자료의 모든 조상 노드들과 값을 비교하며 조정하는 재귀적 방법을 사용하여 만들 수 있다.

그래프: 자료들 사이의 연결 관계를, 자료를 저장하고 있는 정점과 그 사이의 관계를 간선으로 표현하는 추상화된 자료 구조(여기서 정점과 간선은 트리에서의 노드와 링크와 같다)

그래프 특징: 1. 정점들 사이에 연결되는 간선들 사이에는 우선순위가 없고 트리에서의 계층적 관계뿐만 아니라 순환적 연결 관계까지도 모두 포함하는 자료구조 이다. 2. 그래프에서의 연결 관계들을 각 정점을 연결하는 간선의 유무와 연결 방향으로 표현 가능하며, 2차원 배열이나 리스트를 이용해 저장하고 다룰 수 있다.

그래프의 4가지 형태: 방향성과 가중치가 모두 없는 형태, 방향성은 있으나 가중치가 없는 형태, 방향성이 없고 가중치가 있는 형태, 방향성과 가중치가 모두 있는 형태로 구분한다. 이러한 그래프들은 자료와 자료들 사이의 관계들뿐만 아니라 현실의 복잡한 상황들을 간단히 표현하고, 컴퓨터로 저장해 다양한 알고리즘과 방법으로 처리할 수 있는 가장 기본적인 자료 구조임. https://img1.daumcdn.net/thumb/R720x0.q80/?scode=mtistory2&fname=http%3A%2F%2Fcfile25.uf.tistory.com%2Fimage%2F21029250584C0F24136E16

가중치가 없는 무방향 그래프를 배열로 저장하는 방법 : 4개의 정점과 5개의 간선으로 이루어져있고 정점의 연결 관계를 1/0로 저장한다

 1 2 3 4

1 0 1 1 1/ 2 1 0 1 1/ 3 1 1 0 0/ 4 1 1 0 0/

가중치가 있는 방향 그래프를 배열로 저장하는 방법: 4개의 정점과 6개의 간선, 정점의 연결 관계와 가중치를 값/0로 저장한다.

  1  2  3  4

1 0 5 4 0/ 2 5 0 0 3/ 3 0 2 0 0/ 4 1 0 0 0/

그러나 이렇게 2차원 배열을 사용해 그래프를 저장하면 큰 메모리 공간을 필요로한다. 인접 리스트 방법을 사용하면 메모리 공간의 크기를 효과적으로 줄일 수 있다.

가중치가 없는 방향 그래프를 인접 리스트 형태로 저장하는 방법 4개의 정점과 6개의 간선, 각 정점에 연결되는 다른 정점들을 리스트처럼 연달아 연결한다 1: 2 3 2: 1 4 3: 2 4: 1