다양한 백엔드 지식들 - 1 (자료구조 중점)

lsw·2021년 8월 31일

소트 시간복잡도 우선순위큐 트리 힙

백엔드 지식

목록 보기

1/1

1. 우선순위 큐의 동작방식

스택 : 후입 - 선출

큐 : 선입 - 선출

우선순위 큐 : 우선순위가 높은 노드 선출

1.1. 우선순위 큐란?

프로그래머가 데이터를 근거로 각 자료의 우선순위를 결정하여 출력을 이행할 수 있는 자료구조

1.2. 다양한 방식 기반의 우선순위 큐의 구현

배열기반
연결리스트 기반
힙을 이용한 구현

배열기반 구현의 장/단점

구현 방법이 간단하나 한칸 씩 미는 작업이 반복되는 번거로움 과 새로운 데이터의 삽입위치를 찾기 위해 모든 데이터와 우선순위 비교가 이루어져야 한다.

(연결리스트기반 구현의 단점 역시 배열기반 구현의 단점과 유사하며 노드 의 수가 많아질 수 록 비례하여 성능이 저하된다.)

1.3. 힙을 이용한 우선순위 큐의 구현 - 삽입과 삭제

삽입

삽입되는 데이터는 최초에 우선순위가 가장 낮다고 가정하여 리프노드레벨 가장 우측에 추가되며 이후 부모노드와의 키값 대소비교를 통해 "최소힙 또는 최대힙의 조건을 만족할 때 까지" 위치를 조정하게 된다.

(*리프노드레벨 : 최하위 노드 레벨)

삭제

최우선순위 데이터(루트노드 데이터)를 삭제하고 말단 노드에 위치한 가장 작은 우선순위의 데이터로 그 자리를 대체한 후 이번엔 top → down 방식으로 루트노드 레벨 부터 차례로 자식노드와 키의 대소를 비교해 가며, 마찬가지 "힙의 조건을 만족할 때 까지" 위치를 조정하게 된다.

(*루트노드 : 최상위 노드)

1.4. 힙을 이용한 우선순위 큐의 구현 - 삽입과 삭제의 알고리즘 (in C & 최대힙 의 경우)

이미 정렬되어있는 트리임을 가정함

구조체 정의(structure)

// structure definition
#define MAX_ELEMENT 100
// element : 데이터 혹은 자료의 우선순위를 의미(key)
typedef struct{
  int key;
}element;

// heaptree : 힙 트리를 의미(완전 이진 트리)

typedef struct{
  int heap_size;
  element heap[MAX_ELEMENT];
}heaptree;

구조체 : 데이터를 담은 100개의 노드 트리가 정의되었다.

삽입(insert)

// 삽입 메서드 정의
void insert(heaptree *h, element newdata){
  int i = ++(h->heap_size); 
// 삽입 시 heap_size는 +1
// i == 2일 때 level2 와 level1 노드의 비교가 이뤄진다. 따라서 i !== 1의 조건이 붙는다
// 새데이터의 키값과 부모노드의 키값을 비교한다. i가 낮아질수록. 즉, 반복문이 거듭될수록 레벨을 낮아진다.
  while(i != 1 && newdata.key > h->heap[i/2].key){
// 키값이 자식(new) > 부모 일 경우 부모노드의 키값이 한레벨 아래(자식노드의 본래 레벨)로 재조정된다.
    h->heap[i] = h->heap[i/2];
// 레벨이 낮아진다.
    i /= (double)2;
  }
// 키값이 부모 > 자식(new)일 경우 반복문은 멈추게 되며 최종 비교 시의 i레벨에 새로운 데이터가 정착한다.
  h->heap[i] = newdata;
}

삭제(delete)

import { element, heap } from 구조체정의 파일
// 삭제 메서드 정의
element delete_root_node(heaptree *h){
  int parent=1, child=2;
// 삭제할 키값, 루트노드 자리를 대체할 리프노드의 키값을 저장할 변수 선언
  element saveRootKey, saveLeafKey; 
// 루트노드의 키값을 저장
  saveRootKey = h->heap[1];
// 마지막 노드의 키값을 저장, 해당 노드는 없어지므로 후위연산을 해줌
  saveLeafKey = h->heap[(h->heap_size)--]; 
// 최대 리프노드까지 비교해준다.
  while(child <= h->heap_size){
/* 
새로이 루트노드값이 된 saveLeafKey값과과 자식노드 값을 비교하는 과정에서 좌측-우측 자식노드가 
수치상 정렬된 것이 아니기에 그 중 더 큰 값을 골라냄
*/
    if(child < h->heap_size && h->heap[child].key < h->heap[child+1].key){
      child++; // 비교대상을 우측 자식노드 선정
    }
    if(saveLeafKey > h->heap[child].key){
      break; // 더이상의 비교가 필요하지 않음(반복문 탈출)
    }
// 자식노드의 키값 > 부모노드의 키값 일 시 두 노드의 키값을 맞바꿈.
    h->heap[parent] = h->heap[child]; 
    parent = child;
    child *= 2; // 한 레벨 내려간다.
  }
// 더이상의 비교가 필요하지 않은 시점에서의 parent노드에 임시 루트노드(saveLeafKey)가 정착한다.
    h->heap[parent] = last_item; 
  return delete_item;
}

2. 힙이란 무엇인가?

완전이진트리의 일종으로 우선순위큐의 구현을 위해 고안 된 특수한 자료구조

2.1. 최소 힙 / 최대힙

최소힙 : 부모노드의 우선순위가 자식노드의 우선순위보다 작거나 같은 완전이진트리 형태의 힙구조
최대힙 : 부모노드의 우선순위가 자식노드의 우선순위보다 크거나 같은 완전이진트리 형태의 힙구조

3. B+트리란 무엇인가

3.1. m-way tree

데이터베이스의 데이터는 디스크에 위치한다. 다만 in memory DB(가령 redis, memcach)의 캐시데이터는 디스크에 존재하지 않는다.

이 디스크에 특정 위치에 있는 레코드를 찾기 위해서 인덱싱을 하는데 이 때 차수가 높아지게 되면(block level 1 - block level 2 - ... - block level n) 멀티 인덱싱이 필요하다. 이를 효과적으로 해결하는 방법이 m-way tree이다.

이진트리란 m=2 인 m-way 트리를 말한다. 여기서 m 은 루트노드의 자식노드 개수를 말한다.

인덱싱

검색의 기준이되는, 키값 역할의 인덱스(index)를 이용하여 레코드를 검색하는 방법이다. 예를 들어 대한민국 성인 남성을 키 순으로

[~170]

[170 ~ 180]

[180~ 190]

[190 ~]

으로 나눠서 쿼리한다고 하면 여기서 인덱스는 키(height)가 된다.

멀티인덱싱

2개 이상의 인덱스를 이용하여 쿼리하는 방법을 멀티인덱싱이라 부른다.

{
KCE: '#height <= :height' and '#sex = :sex', // 실제 검색 
EAN: { '#height: height, #sex: sex' }, // 인덱스 설정(키, 성별)
EAV: { ':height': 180, ':sex': 'male' } // 인덱스 = value에서 value값
}

키와 성별을 인덱스로 설정해 키가 180보다 작은 남성을 검색한다.

3.2. B트리

m-way tree도 차수가 높아지면 효율이 급감하게 된다. 따라서 B트리 라는 일정 규칙이 있는 m-way tree를 규정하게 되는데

B트리의 규칙
1. 루트 노드는 최소 2개 이상의 자식노드를 가진다.
2. 루트 노드를 제외한 노드는 최소 [M/2]개의 자식노드를 가진다. (* [ ] : 소수점 버림 )
3. 모든 리프노드들의 레벨은 같아야 한다. (하나의 리프노드만 삐죽 튀어나와있으면 안됨)
4. 노드의 자료수가 K+1개이면 K개의 자료를 가져야 한다.
5. 자료는 정렬상태로 저장된다.
6. 입력자료가 중복되지 않는다.
7. Creation process가 bottom-up 형식이다
  
  *bottom-up creation process
8. 노드에 키를 주입하고 자리가 부족하여 남게되는 키를 위해 새로운 노드뭉치를 우측에 생성한다.
9. 왼쪽(기존)노드의 최우측 키(중간값)를 부모노드로 승격시키고 왼쪽노드의 나머지 키들을 좌 / 우 노드로 구분한다.

3.3.1. B+트리

간단히 "B+ 트리 = B트리 + 데이터의 연결리스트" 로 표현할 수 있다.

B+ 트리는 B트리의 특성 다시를 그대로 가지며 순차검색(sequential search)에 특장점을 갖는 형태로 발전한 자료구조이다.

B+ 트리의 특징
1. 모든 노드에 레코드 포인터가 있는 B트리와 달리 리프노 에만 레코드 포인터가 있다.
2. 그렇기 때문에 리프노드에 모든 노드의 키값이 포함되어야 한다.
3. 리프노드들은 왼쪽에서 오른쪽으로 연결리스트를 활용하여 연결되어 있어 인덱스된 순차적 파일을 비교하는데 용이하다.
4. B+ 트리의 비단말노드는 해당 데이터의 빠른 접근을 위한 인덱스 역할만(가교 역할) 할 뿐이다.(인덱스는 있지만 실제 데이터나 키값이 없다.)
5. 삽입 시 노드에 빈자리가 있다면 그대로 삽입, 없다면 키 값들을 적당히 분리하는(위 bottom-up creation process) 방식을 취한다. 다만 중간값의 부모노드 승격 시 해당 키 값은 부모노드, 새로 할당된 노드뭉치의 최 좌측 노드에 모두에 포함되어야 한다.(리프노드는 모든 키 값을 포함해야 한다는 규칙 준수하기 위해)
6. 키 값을 일일히 비교하지 않고 데이터에 접근하여 처리할 수 있다.
7. B트리와 달리 삽입과 삭제가 리프노드에서만 이루어진다.

3.3.2. B+트리의 검색 / 삽입 / 삭제

검색

B트리에서의 검색방법과 매우 유사하다.

삽입

B트리에서의 삽입방법과 유사하지만 노드가 분리될 시 부모노드로 승격되는 중간값(키)이 새로 생성되는 노드뭉치의 최 좌측 노드에도 포함되어야 한다.

삭제

재배치와 합병이 필요하지 않은경우 리프노드에서만 삭제된다.(비단말 노드는 유지)
재배치가 이루어진다 하더라도 키 값만 삭제되지 트리의 구조자체는 유지된다.
합병의 경우에도 인덱스의 키 값이 삭제된다.

3.3.3. B+트리의 단점

B트리에선 자료 검색의 Best Case가 루트노드에서 끝날 수 있지만 B+트리의 경우 반드시 리프노드레벨까지 검색이 이뤄져야 한다는 점이 단점이다.

multiple-way-tree → B tree → B+ tree

4. 시간복잡도란?

4.1. 알고리즘 처리의 소요시간

알고리즘이란 어떤 목적을 달성하기 위한 일련의 과정이라 볼 수 있고 이 때 그 과정의 소요시간은 세 가지 측면에서 바라볼 수 있다.

컴퓨터의 처리속도
사용되는 언어 또는 프레임워크의 컴파일러의 처리속도
시간복잡성(시간복잡도 : 알고리즘을 수행하기 위해 프로세스가 처리하는 연산 수에 관한 근사함수)

4.2. 시간복잡도

시간복잡도란?

알고리즘 수행을 위해 프로세스가 처리하는 연산의 수와 관련된 함수로 input 개수 n에 해당하는 연산 수를 계수, 상수항 등을 제외하여, 결과에 지대한 영향을 미치는 부분만 점근적으로(Asymptotically) 남겨 표현한 것이 바로 이 시간복잡도이다.

알고리즘의 효율 가늠

알고리즘의 효율을 가늠할 때 실행시간을 기준으로 하면 앞선 소요시간의 측면 1,2에 지대한 영향을 받게 되는데 이는 외부 요인으로(Outer factor) 여겨지며 실질적으로는 연산의 수와 관련된 함수인 시간복잡도를 효율 가늠의 기준으로 세우는 것이 바람직하다.

시간 복잡도의 세가지 표현방법

최상의 경우(Best case) : Ω(Omega)
평균의 경우(Average case) : Θ(Theta)
최악의 경우(Worst case) : O(Big O)

5. 힙소트와 버블소트의 동작방식과 그에 대한 비교

5.1. 힙소트의 동작방식

앞서 힙을 다루며 삽입과 삭제의 원리와 그것의 알고리즘을 살펴보았다. 이를 그대로 이용하여

(최대힙을 기준으로 정렬할 경우)

삽입 알고리즘을 통해 최대힙의 기준에 부합하도록 완전이진노드에 모든 값을 정렬한다.
삭제 알고리즘을 통해 루트노드의 키값(데이터 혹은 레코드로 표현할 수 있다)을 반환값으로 설정해 별도 생성해 둔 배열의 끝부터 순차적으로 저장한다.
배열을 다 채운 후 순차적으로 읽어들이면 데이터가 오름차순으로 정렬되었음을 알 수 있다.

5.2.1. 버블소트의 동작방식

배열의 첫번째 인덱스 값부터 시작한다.
i-1번째 인덱스가 i번째 인덱스보다 값이 크다면 두 인덱스의 값을 교환한다.
2의 과정을 right(초기: int right = n)까지 반복한 후 right의 값을 -1 한다. (비교: 1-2 ⇒ 2-3 ⇒ 3-4 ⇒ n-1 - n)
2,3의 과정을 right가 1이 되지 않을 때 까지 반복한다. (right ≠ 1)
결과적으로 가장 우측 인덱스부터 차례로 큰 값들이 위치하게 돼 오름차순 정렬이 되었음을 확인할 수 있다

5.2.2. 버블소트 알고리즘

우선 버블소트와 동작방식이 비슷한 Selection sort의 알고리즘을 먼저 살펴보자

Selection sort

#include <stdio.h>
#define MAX_SIZE 100

// method declaration
void selection(int * ptr, int size);

int main(){
  int list[] = {2,9,7,8,3,6};
  int size = sizeof(list) / sizeof(int);
  selection(list, size);
  for(int i = 0 ; i < size ; i++){
    printf("%d ", list[i]);
  }
  return 0;  
}

// method definition
void selection(int * ptr, int size){
  int left=0, right=size-1, largest, temp, position;
  for(int i = 0 ; i < size-1; i++){
// set the value of 'largest', 'temp'(will be used in exchanging process)
    largest = ptr[0], temp = ptr[right];
    for(int j = 1 ; j < right ; j++){
    if(ptr[j] > largest){
      largest = ptr[j];
      position = j;
    }
   }
   ptr[right] = largest; // sorting(ascending way)
   ptr[position] = temp; 
// last position's element fills the new largest value's pre-position
   right--; // to fill the array's last index, last index -1, last index -2 .....
  }
}

Bubble sort

void bubble(int list[], int size){
  int temp;
  int right = size;
  while(right != 1){
    for(int i = 1 ; i < right ; i++){
      temp = list[i];
      if(list[i] < list[i-1]){
// change each one's position(back and forth)
        list[i] = list[i-1];
        list[i-1] = temp;
      }
    }
    right--; // last index, last index-1, last index-2...
  }
}

int main(){
  int list[] = {5,3,2,7,6,1};
  bubble(list, sizeof list / sizeof(int));
  for(int i = 0 ; i < sizeof list / sizeof(int) ; i++){
    printf("%d ", list[i]); 
  }
  return 0;
}

lsw

미생 개발자