[전산 공부] 자료구조

1) 연결리스트(Linked List)

각 노드는 데이터 필드 + 링크 필드(포인터)로 구성되어 있다.

포인터가 다음 노드를 가리키는 구조로, 전체 노드는 서로 연결되어 있다.

 

Q. 새로운 노드 삽입 (1 -> 2 사이에 3 삽입)

- 3 노드의 링크가 2를 가리키게 한다.

- 1의 링크가 3을 가리키게 한다. (즉, 1이 원래 3을 가리키고 있는 링크를 3 노드가 가져오면 된다.)

newNode(3 노드) -> link = preNode(1 노드) -> link;

 

---

2) 스택(Stack)

[ 수식의 표기법 변환 ]

 

연산 우선순위에 따라 괄호를 묶어서 그것을 한 묶음으로 보고 변환해주고 그걸 또 하나의 덩어리로 보고 전환

 

 

Q. 예시 문제

 

문제 해설

전위 표기법(prefix)-연산자가 앞에
중위 표기법(infix)-연산자가 가운데에
후위 표기법(postfix)-연산자가 뒤에

1. 연산자에 따라 묶는다.

(-(/(*A(+BC))D)E)

2. 연산자를 각 괄호 뒤로 뺀다(후위식)
(((A(BC)+)*D)/E)-

3. 괄호를 제거한다.

 

---

3) 트리(Tree)

• 트리의 차수란 특정 노드에 연결된 자식 노드의 수이다.
• 사이클이 없는 그래프 

1) 이진 탐색 트리

• 데이터의 값에 따라 자리가 정해져, 자료의 탐색, 삽입, 삭제가 효율적이다.
• 데이터가 입력되는 순서에 따라 첫 번째 데이터가 근노드가 된다.
• 데이터는 근노드와 비교하여 값이 작으면 좌측으로 연결하고, 값이 크면 우측으로 연결하여 이진 검색 트리로 구성한다.
• 정렬이 완료된 데이터를 이진 검색 트리로 구성할 경우 사향 이진 트리가 되어 비교 횟수가 선행 검색과 동일해 진다.
• 최악의 경우 시간이 오래 걸림.
• 시간복잡도 평균은 O(logN)이지만, 최악의 경우 O(N)

내부/외부 경로 길이 계산

내부 경로 길이 : 루트로부터 각 내부 노드 경로 길이의 합
외부 경로 길이 : 내부 경로 길이 + (2 * 노드의 개수)

 

 

2) AVL 트리

• 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리
• AVL 트리는 이진 탐색 트리의 속성을 가진다.
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 이다.
• 균형 인수가 [-1, 0, 1] 이다.
• 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다.
• AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다.
• 시간복잡도 평균은 O(logN), 최악의 경우에도 O(logN)

AVL 트리

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리.

 

AVL 트리는 균형 이진 검색 트리로서, 각 노드의 두 하위 트리의 높이 차이가 1을 넘지 않도록 유지됩니다. 삽입이나 삭제와 같은 연산 후에도 균형이 유지되어야 한다.

 

Q. 654321 순으로 데이터를 삽입할 때 최종 루트 노드는 무엇일까?

-> 4

 

1. 6 삽입: 루트 노드

2. 5 삽입:  왼쪽 서브트리로 추가

3. 4 삽입: 5의 왼쪽 자식으로 추가. 균형이 깨지므로 회전 발생

    6
   /
  5
 /
4

     5
    / \
   4   6

 

4. 3 삽입: 4의 왼쪽 서브트리로 추가.

      5
     / \
    4   6
   /
  3

 

5. 2 삽입: 3의 왼쪽 서브트리으로 추가. 균형이 깨져 회전 발생

      5
     / \
    3   6
   / \
  2   4

 

6. 1 삽입: 2의 왼쪽 서브트리으로 추가. 균형이 깨져 회전 발생

      4
     /  \
    2    5
   / \    \
  1   3    6

 

 

 

3) 2-3 트리

• 차수가 2 또는 3인 내부 노드를 갖는 트리

4) 레드 블랙 트리

 

5가지 속성

1. 모든 노드는 red 혹은 black
2. 루트 노드는 black
3. 모든 nil(leaf) 노드는 black
4. red의 자녀들은 반드시 black이어야 한다. (즉, 가 연속적으로 존재할 수 없다.)
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)
   1. 8번 노드를 예로 들어보자.
   2. 8번 노드에서 자손 nil 노드들까지 가는 경로는 5가지이다.
   3. 각각의 경로 모두 black의 수가 2개로 동일하다.

 

트리의 간선의 수

m = n - 1

 

---

4) 그래프(Graph)

방향/무방향 그래프의 최대 간선 수

방향 그래프: m = n(n-1)
무방향 그래프: m = n(n-1) / 2

 

 

크루스칼(Kruskal) 알고리즘

 

그래프의 간선들을 가중치의 오름차순으로 정렬하고, 정렬된 간선 중에서 사이클을 형성하지 않는 간선을 현재 간선 집합에 추가

 

* 크루스칼이랑 프림 알고리즘은 그리디 알고리즘에 기반한다.

 

 

 

---

5) 정렬(Sorting)

[ 시간 복잡도 ]

 

삽입정렬: 이미 정렬된 목록에서 빠르게 정렬할 수 있다.

 

[ 삽입 정렬 (앞 범위 비교) ]

 

투포인터라고 생각했을 때, 회전마다 end 값을 계속 올리고 그 범위 내에서 비교해서 한 칸 뒤로 이동시켜 정렬

 

 

[ 선택 정렬 (뒤 범위 비교) ]

 

투포인터라고 생각했을 때, 회전 마다 start값을 계속 올리고 그 범위 내에서 비교해서 그 값과 교환하여 정렬

큐를 이용해서 정렬

 

: 키(key) 값이 가장 큰 것과 가장 오른쪽 것의 위치 교환을 반복적으로 수행한다.

 

[ 버블 정렬 ]

 

파도 타듯이 1회전에서 계속 양옆 비교

 

[ 기수 정렬 ]

 

: 분배 방식의 정렬 방법으로 정렬할 원소의 킷값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법

 

[ 퀵 정렬 ]

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot) 로 설정한다.

동작 예시

• [Step0] 현재 피벗 값은 '5'. 왼쪽에서부터 '5'보다 큰 데이터를 선택하고, 오른쪽에서부터 '5'보다 작은 데이터를 선택한다. 그 다음 두 데이터의 위치를 변경한다.
• [Step1] 이 과정을 반복하다가 '1'과 '6'이 선택되듯이 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.
• [분할 완료] 왼쪽 데이터 묶음을 정렬하고 오른쪽 데이터 묶음을 정렬한다.

---

6) 해싱(Hashing)

해싱기법 종류

제산 함수, 폴딩 함수, 중간제곱 함수, 비트추출 함수, 숫자 분석 방법

• 제산법(Division Method): 나눗셈법이라고도 하며 버킷의 수에 근접하는 수로 키 값을 나눈 나머지 홈주소로 사용된다. / 정해지지 않은 키 값 사용
• 폴딩 함수: 탐색키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합) 연산하여 그 결과로 주소를 취하는 방법 / 키 값이 너무 길 때
• 중간제곱 방법(Mid-square Method): 식별자를 제곱한 후에 그 결과의 중간에 있는 적당한 수의 비트를 취하여 버킷 주소로 한다.
• 숫자분석 방법: 키가 취할 수 있는 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 선택하는 방법 / 형식이 정해진 키 값 사용
• 기수 변환법: 연속한 키의 덩어리를 광범위하게 분산시켜 랜덤화해서 어드레스를 만드는 것을 목적으로 고안한 방법

 

검색 시간

레코드 양이 적으면 검색 시간이 일정하지만, 레코드 양이 많아지면 충돌을 해결하기 위한 시간이 증가하게 된다.

 

시간복잡도

최악의 경우 (O(N))

 

해시 충돌 해결법

1) 개방 주소 방식(Open Addressing)(=선형 방식)

충돌이 일어난 자리에서 그 다음 버킷을 차례로 검색하여 처음 나오는 빈 버킷에 데이터를 넣는 방식

 

2) 폐쇄 주소 방식(Close Addressing)(=연결 처리법, 오버플로 공간 처리법 등)

해시 테이블에서 서로 다른 킷값의 데이터가 해시 함수에 의해 같은 버킷에 배치되어 충돌이 발생할 경우 포인터를 이용하여 같은 해시 함수 값을 갖는 레코드를 연결 리스트로 연결하는 방식이다.