26-1 ) 자료구조론

 

 

 

슬슬 컴퓨터에게

두손두발 들게 만들기 시작한

'그' 과목

 

자료구조론

 

대학교 와서 1학년 때

C언어를 처음 배우고

컴퓨터 언어의 세계란...

 

 

(나랑 안 맞는 것 같다)

라는 결론을 내리고 고민을 많이 했다.

 

 

 

 

자료구조론을 들어도 되는가?

C프기 → C프 → 자료구조론

 

점점 C언어를 심화하고 응용하는데

아니 저는 아직 기초도 잘 모르는데

모래성이 점점 무너지는 느낌을 많이 받았다.

 

 

말 그대로 자료구조에 대해 다 배우는 것 같은데

배열, 리스트, 순회, 여러 정렬...

C언어 코드도 외우고 개념도 외우고

 

시험 진짜...

어카냐? 점수가 무섭다.

 

 

 

 

리스트도 여러 리스트가 있더라

난 리스트를 처음 알았는데

다양한 리스트의 활용을 알고

C언어 코드까지 외우는거 너무 벅차자나.

 

수업도 되게 빠르게 나가고

과제가 젤로 힘들었다.

(대부분 AI가 다했다고 할 수 있지.)

 

 

중간고사를 진짜 조지고(내가 당함)

기말고사는 그래도 개념이라도 외워가자는 마인드로

하긴했는데

 

...

 

 

 

 

---

 

 

과제는 그 수업날 교수님이

빠른 속도로 이거이거 해오세요 하면

 

C언어 코드로

결과 확인하는 거였는데

 

책이랑 PPT 자료에 있는 코드가

핵심만 담은 코드라서

뭔가 추가할 건 항상 있었다.

 

그치만 저는 잘 모르겠더라고욤

 

 

 

과제

 

 

매주 해서 내기는 하는데

솔직히 AI 선생님 없이는 절대 하지못했을

 

중간중간 배웠던 C언어 코드들 보면

이게 이거구나 싶기도 했지만

 

막상 코드 짜라고하면

너무 막막하기만 해서

많은 생각을 하게 만들었던 나에겐

넘나 어려웠던 자료구조...

 

컴공?

 

 

 

 

 

 

---

 

7장 연결리스트 (2)

1. 원형 연결 리스트

• 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트
• 한 노드에서 다른 모든 노드로의 접근이 가능 (한 노드에서 링크를 계속 따라가면 모든 노드를 거쳐 자기 자신 노드로 돌아옴)
• 노드의 삽입과 삭제가 단순 연결 리스트보다 간단

원형 연결 리스트의 변형

• 헤드 변수가 마지막 노드의 주소를 저장하도록 변경
• 헤드 포인터 변수가 리스트의 마지막 노드의 위치를 가리키고 있으므로, 마지막 노드를 탐색하지 않고 바로 찾을 수 있음
• 첫 번째 노드의 위치는 마지막 노드에 저장되어 있어 O(1) 시간에 찾을 수 있음
• 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 간단

원형 연결 리스트를 이용한 원형 큐 구현

• 배열을 이용 X → 원형 연결 리스트로 원형 큐 구현 가능
  • 장점 : 빈 공간 없이 필요한 만큼만 메모리 동적으로 할당, 저장할 수 있는 데이터 갯수에 대한 제약이 없음
  • 단점 : 링크 정보를 저장하기 위한 추가적인 공간 필요

단순 연결 리스트의 단점 → 선행 노드를 찾기 힘듦

1. 이중 연결 리스트

• 후속 노드 뿐만 아니라 선행 노드에 대한 위치 정보를 노드마다 모두 저장하는 리스트
  • 장점 : 선행 노드도 쉽게 찾을 수 있음
  • 단점 : 후행 노드 뿐만 아니라 선행 노드 위치 저장을 위한 링크 공간도 필요
  • 구현이 복잡

헤드 노드 (head node, dummy node)

• 이중 연결 리스트에서 데이터를 가지지 않고, 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드
• 헤드 포인터 변수와의 구별 필요
• 공백 상태에서는 헤드 노드만 존재

 

1. 연결 리스트를 이용한 연결 스택과 큐

linked stack : 배열을 이용한 스택은 크기에 제한이 있으나 연결 스택은 없음 (동적 메모리만 할당 받을 수 있으면 새로운 요소 삽입 가능), push 연산과 pop 연산

linked queue : front = rear = temp

 

 

8장 트리

선형 자료 구조 : 리스트, 스택, 큐 / 비선형적 자료 구조 : 트리, 히프, 그래프

1. 트리

• 계층적 자료 구조
• 부모-자식 관계의 노드들로 구성

<트리 용어>

• 노드 : 트리를 구성하는 요소
• 루트 : 부모가 없는 최상위 노드
• 서브 트리 : 전체 트리 중 일부 트리
• 단말 노드(=terminal node=리프 노드 = 자식이 없는 노드) : 단수(나 자신 1개)
• 비단말 노드(=자식이 있는 노드)
• 레벨 : 트리의 각 층 번호
• 높이 : 트리의 최대 레벨
• 차수 : 노드가 가지고 있는 자식 노드의 개수

<트리 종류>

• 일반 트리 : 각 노드의 자식 수에 제한이 없는 트리
• 이진 트리

1. 이진 트리

: 모든 노드가 2개의 서브 트리를 가지고 있는 트리 (공집합도 서브 트리가 될 수 있음)

• 모든 노드는 최대 2개까지의 자식 노드를 가짐(최대 차수가 2이하)
• 서브 트리 간의 순서가 존재 (왼 서브 트리와 오른 서브 트리는 서로 구별)

이진 트리의 순환적 정의 : (1) 공집합 이거나 / (2) 두 개의 이진 트리를 노드의 왼쪽 서브 트리와 오른쪽 서브 트리로 가진 트리

⇒ 정의에 의해 이진 트리의 서브 트리도 이진 트리의 성질을 만족

<이진 트리의 성질>

• 노드의 개수가 n개 이면 간선의 개수는 n-1개임
• 높이가 h인 경우, 최소 h개, 최대 2의 h제곱-1 개의 노드를 가짐
• n개의 노드를 가지는 이진 트리의 높이는 최대 n, 최소 log2(n+1)

<이진 트리의 분류>

(1) 포화 이진 트리 : 모든 레벨에서 노드가 가득 찬 이진 트리(완전 이진 트리), 높이 k의 포화 이진 트리는 2의 k제곱-1 개의 노드를 가짐

(2) 완전 이진 트리 : 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 모두 채워져 있음. 마지막 레벨 k에서는 노드가 왼쪽부터 차례대로 채워진 이진 트리

1. 배열을 이용한 이진 트리 구현 (배열 표현법)

높이 k인 트리를 위해 2의 k제곱-1개의 공간을 배열로 할당

1. 포인터를 이용한 이진 트리 구현 (링크 표현법)

⇒ 한쪽으로 치우쳐진 트리일 경우 유리

• 링크에 저장된 포인터를 이용하여 부모 노드가 자식 노드를 가리킴
• 빈 공간 없이 노드 수에 비례하여 필요한 만큼만 메모리 사용
• 저장할 수 있는 노드 수에 대한 제약이 없음 (필요 시 동적 메모리 할당)
• 링크 저장하기 위한 추가 공간 필요

 

1. 순회 (treversal)

: 트리의 노드를 체계적으로 방문하는 행위

• 전위 순회(preorder) : VLR, 노드→왼→오른 / 구조화된 문서 출력
• 중위 순회(inorder) : LVR / 수식 트리를 중위 표기법으로 출력
• 후위 순회(postorder) : LRV / 디렉토리 용량 계산

1. 레벨 순회 (level order)

• 각 노드를 레벨 순으로 순회하며 큐를 이용하여 구현

1. 수식트리

: 산술식을 트리 형태로 표현한 것 (논리, 비교 연산도 트리로 표현 가능)

• 비단말노드 : 연산자
• 단말노드 : 피연산자

⇒ 후위 순회 사용 : 두 서브 트리의 값을 순환 호출로 계산한 후 현재 노드에 해당되는 연산 수행

 

 

9장 히프

1. 히프(heap)

: 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전 이진 트리

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나(혹은 작거나) 같음
• 최댓값 또는 최솟값을 가장 먼저 출력하는 우선순위 큐라고 볼 수 있음

	삽입 연산 복잡도	삭제 연산 복잡도
요소를 정렬하지 않고 리스트에 저장	O(1)	O(n)
요소를 정렬하여 리스트에 저장	O(n)	O(1)
요소를 히프에 저장	O(log n)	O(log n)

 

 

히프의 종류

• 최대 히프 : 가장 큰 값을 먼저 찾는 히프 (부모 노드의 키값 ≥ 자식 노드의 키값)
• 최소 히프 : 가장 작은 값을 먼저 찾는 히프 (부모 노드의 키값 ≤ 자식 노드의 키값)

히프의 높이

• n의 노드를 가지고 있는 히프의 높이는 O(log n)
• 마지막 레벨 h를 제외하고는 각 레벨 i에 2의 (i-1)개의 노드 존재

히프의 구현

• 완전 이진 트리이므로 배열로 구현할 수 있음 (부모 노드와 자식 노드 쉽게 찾을 수 있음)
• 레벨 순회로 방문하는 순서를 각 노드의 번호로 할당하고 그 번호를 배열의 인덱스로 활용

히프의 삽입 연산 : 새로운 요소가 들어 오면, 새로운 요소를 히프의 마지막에 있다고 가정한 후 히프의 성질을 만족하도록 부모 노드들과 교환하여 상승시킴

히프의 삭제 연산 : 가장 먼저 루트 노드를 삭제하고, 마지막 노드를 루트 노드로 이동한 후, 루트에서 단말 노드로 이동하면서 경로에 있는 노드들을 교환하여 히프 성질을 만족 시킴

1. 히프 정렬

• 오름차순 정렬 : 정렬해야 하는 요소들을 최소 히프에 모두 삽입한 후 하나씩 꺼내 오면서 저장
• 내림차순 정렬 : 요소들을 최대 히프에 모두 삽입한 후 하나씩 꺼내 오면서 저장
• 시간 복잡도 : **O(n*log n)**로 빠른편

 

그래프 (1)

그래프 : 연결되어 있는 객체 간의 관계를 표현하는 자료구조

오일러 문제 : 위치(정점), 다리(간선) / 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재

• 정점(vertices) : 여러 가지 특성을 가질 수 있는 객체 (=노드)
• 간선(edge) : 정점들 간의 관계 (=링크

1. 그래프의 종류

• 무방향 그래프 / 방향 그래프
• 가중치 그래프(네트워크)
• 부분 그래프
• 연결 그래프 : 모든 정점 쌍에 대해 경로가 존재하는 그래프 (트리는 사이클이 없는 연결 그래프임)
• 완전 그래프 : 모든 정점이 서로 연결되어 있는 그래프
  • n개의 정점을 가진 무방향 완전그래프의 간선의 수 : nx(n-1)/2
• 인접 정점 : 하나의 정점에서 간선에 의해 직접 연결된 정점들
• 무방향 그래프에서 한 정점의 차수 : 해당 정점에서 연결된 간선의 수(= 해당 정점에서 인접한 정점의 수와 같음)
• 방향 그래프의 차수
  • 진입 차수 : 외부에서 들어오는 간선의 수
  • 진출 차수 : 외부로 나가는 간선의 수
  • 진입 또는 진출 차수의 합 = 간선의 수

1. 그래프의 경로 : 두 정점을 이어주는 정점의 나열
   • 단순 경로 : 경로 중에서 반복되는 간선이 없는 경로
   • 사이클 : 시작 정점과 종료 정점이 동일한 경로
2. 그래프 표현 방법

• 인접 행렬 방법 : 배열로 그래프 표현
• 인접 리스트 방법 : 연결 리스트로 그래프 표현, 간선의 개수가 적은 희소 그래프일 때 효율적인 방법

1. 그래프 탐색

: 하나의 정점에서 간선을 따라 다른 정점들을 한번씩 방문하는 행위, 특정 정점에서 다른 정점으로 간선을 따라 이동이 가능한지 그래프 탐색을 통해 확인할 수 있음

• 깊이 우선 탐색(DFS)
  • 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳에서부터 다른 방향으로 다시 탐색 진행
  • 갈림길로 되돌아가는 스택 필요
  • 스택을 이용하는 순환 함수 호출로 구현가능
• 너비 우선 탐색(BFS)
  • 시작 정점으로부터 가까은 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 탐색 방법
  • 큐를 이용하여 구현 가능

 

그래프 (2)

신장 트리 : 그래프 내의 모든 정점을 포함하는 트리, n개의 정점을 가지는 그래프의 신장 트리는 n-1개의 간선을 가짐

최소 신장 트리 (MST) : 네트워크에 있는 모든 정점들을 가장 작은 비용으로 연결한 트리 (간선의 개수 최소)

1. Kruskal의 MST 알고리즘

: 각 단계에서 그 순간 가장 좋다고 생각되는 것을 선택하는 탐욕적인 방법**(greedy method)**

• 그래프에서 사이클이 되는지 확인하는 방법 필요
  • 입력되는 정점들이 같은 집합에 속하면 사이클 형성
  • union-find 알고리즘 활용하여 같은 집합에 속하는지 파악

union(x, y) : 원소 x와 y가 속해 있는 집합을 합치는 연산

find(x) : 원소 x가 속해 있는 집합을 반환

• Kruskal의 MST 시간 복잡도 분석 : 간선들을 정렬하는 시간에 좌우됨, 사이클 테스트 등의 작업은 정렬에 비해 매우 신속하게 수행됨 ( 시간 복잡도 : O*log(e) )

1. Prim의 MST 알고리즘

: 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해 나감, 신장 트리 집합에 인접한 정점 중에서 최저 간선으로 연결된 정점을 선택하여 신장 트리 집합에 추가함

• Prim의 알고리즘 복잡도 : O(n의 제곱)

희소 그래프 Kruskal (간선 개수 e가 상대적으로 작음)

밀집 그래프

Prim (정점 n에 비해 e가 많으므로)

 

최단 경로

: 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로, 간선의 가중치로는 비용, 거리, 시간 등이 사용될 수 있음

1. Dijkstra의 최단 경로 알고리즘

: 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로 찾음

• 집합 S : 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합
• distance [u] : 시작 정점 v에서 S에 속한 정점들만을 잉요하여 정점 u까지 갈 때 예상되는 최단 경로 비용
• 매 단계 값에서 S에 속하지 않은 정점 중에서 가장 작은 distance 값을 가지는 정점을 하나 골라 S에 추가
• 새로운 정점이 S에 추가되면 distance값 갱신

Dijskstra 알고리즘 복잡도 : O(n의 제곱)

1. Floyd의 최단 경로 알고리즘

: 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 구함, 2차원 배열 A를 이용하는 3중 반복 루프로 구성

Floyed 알고리즘 복잡도 : 3중 반복문을 실행하므로 O(n의 3제곱)

• Floyd는 매우 간결한 반복 구문을 사용하므로 Dijkstra보다 빠르게 모든 정점 간의 최단 경로를 구할 수 있음

 

정렬

정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 자료 탐색에 있어서 매우 중요

• 레코드 : 정렬시켜야할 대상
• 레코드는 필드라는 보다 작은 단위로 구성
• 키 필드로 레코드와 레코드 구별

정렬의 특징 : 모든 경우에 대해 최적의 정렬 알고리즘은 없음

정렬 알고리즘의 평가 기준 : 비교 횟수, 이동 횟수

• 단순하지만 비효율적 : 삽입, 선택, 버블 정렬
• 복잡하지만 효율적 : 퀵, 히프, 합병, 기수 정렬

1. 선택 정렬

• 요소 교환을 통해 정렬 수행
• 정렬된 왼쪽 리스트와 정렬 안 된 오른쪽 리스트로 분류
• 오른쪽 리스트에서 가장 작은 요소와 가장 왼쪽 요소를 교환하여 왼쪽 리스트 요소 단계별 증가
  • 비교 횟수 : O(n의 제곱)
  • 이동 횟수 : 3(n-1)
  • 전체 시간적 복잡도 : O(n의 제곱)
  • 안정성을 만족하지 않음

 

 

1. 삽입 정렬

: 정렬 안된 리스트에서 가장 왼쪽에 있는 요소를 뽑아 정렬된 리스트에 올바른 위치에 삽입하는 과정을 반복

• 비교, 이동의 평균 복잡도 : O(n의 제곱)
• 많은 이동이 필요하므로 레코드가 클 경우 불리
• 안정된 정렬 방법(동일한 키 값을 가지는 레코드들의 상대적 위치는 바꾸지 않음)
• 대부분 정렬되어있으면 매우 효율적

1. 버블 정렬

: 인접한 2개의 레코드를 비교하여 순서대로 있지 않으면 서로 교환

• 비교, 이동의 평균 복잡도 : O(n의 제곱)
• 레코드의 이동 과다 (이동 연산은 비교 연산보다 더 많은 시간이 소요됨)

1. 셀 정렬

: 삽입 정렬이 어느 정도 정렬된 리스트에서 대단히 빠른 것에 착안

• 전체 리스트를 일정 간격의 부분 리스트로 나눔
• 나뉘어진 각각의 부분 리스트를 삽입 정렬함
• 복잡도 : O(n의 1.5제곱)
  • 불연속적인 부분 리스트에서 원거리 자료 이동으로 보다 적은 위치 교환으로 제자리 찾을 가능성 증대
  • 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입 정렬 속도 증가

 

1. 합병 정렬

: 리스트를 균등한 크기로 분할하고 분할된 부분 리스트를 정렬, 정렬된 부분 리스트를 합하여 전체 리스트를 정렬함

<분할 정복 기법>

• 분할 : 배열을 같은 크기의 2개의 부분 배열로 분할
• 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할정복기법 적용
• 결합 : 정렬된 부분 배열을 하나의 배열에 통합
• 복잡도 : O(n*log(n))
• 안정적이며 데이터의 초기 분산 순서에 영향을 덜 받음

1. 퀵 정렬

• 평균적으로 가장 빠른 정렬 방법
• 분할정복법 사용
• 리스트를 2개의 분 리스트로 분할하고, 각각의 부분 리스트를 순환 호출로 다시 퀵 정렬
  • 총 비교횟수 : n*log(n)
• 총 이동 횟수 : 비교 횟수에 비하여 적으므로 무시
• 중간값을 피벗으로 선택하면 불균등 분할 완화가능

1. 기수 정렬

: 레코드를 비교하지 않고 정렬 수행 하여 O(n*log(n))보다 작은 시간 복잡도를 가질 수 잇음

• 정렬 대상을 자리 숫자에 따라 버켓에 넣었다가 꺼내면서 정렬 완성
• 큐로 구현
• 버켓의 개수는 기수의 표현 방법에 좌우
• 버켓이 늘어나면 반복되는 패스의 수가 줄어 듬
  • 10진법 복잡도 : O(d*n)
  • 10이하의 수 : O(n)
• 실수, 한자 등으로 이루어진 데이터는 정렬하지 못함