Data Structure - 질문 Part 2

∙ List-Set 차이점

List는 중복된 데이터를 저장하고 순서를 유지하는 선형 자료구조이고, Set은 중복되지 않은 데이터를 저장할 수 있고, 일반적으로 순서를 유지하지 않는 선형 집합 자료구조다.

∙ Stack, Queue 개념 및 차이점 + 간단한 구현

Stack : 사전 정의 그대로 데이터를 층으로 쌓아올려서 후입선출(LIFO)의 형태를 갖는 자료구조. 데이터 입출력이 맨 위(stack top)에서만 일어나고 스택의 밑(stack bottom)이나 중간에서는 데이터 삭제가 불가능하다. 스마트폰을 사용할 때 '뒤로 가기' 버튼을 누르면 현재의 화면이 멈추고 이전 화면으로 돌아가게 된다. 스택 활용의 예시로 괄호검사, 후위표기법이 있다.

push(x), pop(), peek() (top 원소 읽기), isEmpty(), isFull()의 추상자료형 연산이 있다.

class Stack {
    constructor() {
        this.top = -1;
        this.bucket = [];
    }
    
    isEmpty() {
        return this.bucket.length == 0;
    }

    push(val) {
        this.bucket[++this.top] = val;
    }

    pop() {
        if(this.top < 0) {
            return -1;
        } else {
            let popVal = this.bucket[this.top];
            this.bucket = this.bucket.slice(0, this.top);
            this.top--;
            return popVal;
        }
    }

    peek() {
        return this.bucket[this.bucket.length-1];
    }
    
    clear() {
        this.top = -1;
        this.bucket = [];
    }
    
    print() {
        for(let i=0; i<this.bucket.length; i++) {
            console.log("item[" + i + "] : " + this.bucket[i]);
        }
    }
}

Queue : 가장 먼저 들어온 데이터순으로 나가게 되는 선입선출(FIFO)의 자료구조. 은행의 고객처럼 먼저 온 사람순으로 업무를 처리해야 하는 경우 사용된다.

class Queue{ 
	constructor(){
	  this.linearQueue = [];
	}
	toString(){
	  let result = "";
	  for(value of this.linearQueue){
		result = result + value + "\n";
	  }
	  return result;
	}
	enqueue(element){
	  this.linearQueue.push(element);
	}
	dequeue(){
	  return this.linearQueue.shift();
	}
	peek() {
        return this.linearQueue[this.linearQueue.length-1];
    }
	empty(){
	  if(this.linearQueue.length === 0){
		return true;
	  }
	  else{
		return false;
	  }
	}
  }

isEmpty(), isFull(), peek(), enqueue() (삽입), dequeue() (삭제)의 추상자료형 연산이 있다.

스택은 후입선출, 큐는 선입선출이라는 구조에서 차이가 발생한다.

∙ MST(최소 스패닝 트리)

∙ DFS, BFS

그래프 탐색은 기본적으로 하나의 정점을 기준으로 다른 모든 정점을 순서대로 한 번씩 방문하여 목표 노드를 찾는 것이다. 여기서 스타트하는 정점부터 어느 기준으로 그래프를 탐색할지에 따라 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)으로 나뉜다.

DFS

스타트 정점부터 한 방향의 깊이로 쭉 탐색을 진행하면서 더이상 엣지와 서브트리가 없는 단말노드를 찾는다. 크게 재귀 호출과 배열을 이용한 방문여부 체크를 통해 탐색한다. linked list로 구현되면 O(n + e), 2차원 행렬인 경우엔 O(n^2)의 시간 복잡도를 갖는다. 단 n은 노드 갯수, e는 간선 갯수

BFS

스타트 정점부터 가까운 정점을 방문하고 그 다음 가까운 정점을 방문하는식으로 순회하는 탐색이다. 큐를 이용해 방문한 노드는 앞단에서 꺼내고 뒷단에서는 방문노드의 인접정점을 push한다. 큐가 공백이 될 때까지 진행한다. linked list로 구현되면 O(n + e), 2차원 행렬인 경우엔 O(n^2)의 시간 복잡도를 갖는다.

∙ Hash Table

입력으로 들어온 key에 대해서 해싱함수의 산술적 연산을 거친 변환값을 인덱스 값으로 이용해 Hash Table에 저장된 해당 주소값에 직접 접근하는 자료구조이다. 테이블의 각 원소는 key(index)-value 값으로 구성된다. key 값만 알면 테이블을 조회해서 값을 바로 찾을 수 있다. 시간복잡도는 O(1).

∙ Hash 충돌(+overflow) 및 해결법

재산함수 : h(k) = k mod M = k % M(k는 key값, M은 테이블크기이자 소수, 홀수)

해시 충돌은 서로 다른 키를 가진 항목들이 같은 인덱스로 변환되어 해시테이블 내 주소가 동일한 것을 말한다. 이런 충돌이 누적되어 하나의 버킷에 있는 남아 있는 슬롯이 없으면 overflow가 발생한다. 다음 2 가지의 솔루션이 존재한다.

개방 주소법(opening addressing) : 두 개 이상의 해시 인덱스 값이 같은 버킷에서 충돌을 일으킨다면 테이블내 빈 상태의 버킷을 찾는다. 만약 빈 버킷을 찾는 탐색의 위치가 처음 시작위치로 돌아오면 테이블이 가득차있는 것이다.
특히 선형조사법에서는 모든 버킷을 차례대로 탐색 진행한다.

	h(k), h(k) + 1, h(k) + 2, h(k) + 3 ∙∙∙

이차조사법에서는 n^2의 꼴로 선형조사법의 집중현상을 완화한다.

	h(k), h(k) + 1, h(k) + 4, h(k) + 9 ∙∙∙
    

이중해시법에서는 오버플로우가 발생할 때, 별개의 해시함수를 사용해 해시 주소(인덱스) 값 저장 위치를 결정한다.

	step = C - (k % C) (C는 테이블 크기보다 약간 작은 소수)
	h(k), h(k) + step, h(k) + 2 * step ....
    

체이닝(Chainging) : 동적메모리 할당이 가능한 연결리스트를 이용해 해시 주소가 같은 키값들끼리 버킷에 묶어서 관리한다. 프로세스는 다음과 같다.

1 ) 해시 주소값이 버킷으로 들어오면 동적메모리 할당으로 새로운 노드 생성
2 ) 새로운 노드에 해시 주소값(key) 복사
3 ) 동일한 key 발생 시 오류 출력, 없다면 연결 리스트 끝에 포인터로 새로운 노드를 연결한다.

동적 메모리할당의 유연함으로 공간 사용 효율이 높고 오버플로우 발생시에 해당 버킷의 연결 리스트만 수정하므로 시간 효율이 좋다.

물론 해시 주소값이 여러 버킷에 균등하게 분포되어 있다면 탐색, 삽입, 삭제가 O(1)으로 끝나지만 한 버킷에 몰리면 최악의 경우 O(n)이 된다.

∙ Tree Map

이진트리를 기반으로 한 Map의 종류이다. 기본적으로 key - value 쌍으로 데이터를 저장하고, 이 데이터 객체를 저장할 때 자동 정렬이 발생한다. key는 숫자일 때 값의 오름차순, 문자열일 때 유니코드 오름차순이다. Hash Map보다 추가 삭제시에 효율성이 떨어지지만 정렬된 상태로 Map 객체를 유지하거나 정렬 조건의 데이터를 조회해야 한다면 TreeMap이 더 적절하다.

∙ Recursion - 하노이 탑, 최소공배수 최대공약수, 피보나치 구현

최소공배수, 최대 공약수

function solution(n, m) {
    const gcd = (big, small) => {
      let recur = (big % small);
      return (recur) ? gcd(small, recur) : small;
    }
    return [gcd(m, n), ((m * n) / gcd(m, n))];
}

하노이의 탑

function solution(n) { // n은 원판 갯수
    let answer = [];
    
    
    function hanoiTower(n , A , B , C){
        if(n === 1){
            return answer.push([A, C]);
        }else{
            hanoiTower(n - 1, A , C , B);
            answer.push( [A, C] );
            hanoiTower(n - 1, B , A , C);
        }
    }
    hanoiTower(n , 1, 2, 3);
    return answer;
}

피보나치 수열

function fibonacci(num) {
	if(num < 2) return num;

	return fibonacci(num-1) + fibonacci(num-2);
}

+) 팩토리얼

function factorial(n){
	if(n < 0) return;
	if(n === 0) return 1;
    
    return n * factorial(n - 1);
};

∙ Quick Sort 구현

참고)

빈출 문제
∙ https://okky.kr/article/673648
∙ https://butter-shower.tistory.com/184

DFS, BFS
∙ https://ratsgo.github.io/data%20structure&algorithm/2017/11/20/DFS/
∙ https://ratsgo.github.io/data%20structure&algorithm/2017/11/19/BFS/
∙ c언어로 풀어쓴 자료구조 379p

Stack, Queue 개념 및 차이점
∙ https://devowen.com/285
∙ https://atoz-develop.tistory.com/entry/자료구조-큐-정리-및-연습문제
∙ https://velog.io/@choiiis/자료구조-스택Stack과-큐Queue

Hash Table
∙ https://stdin2stdout.tistory.com/entry/QHash에-대해서-설명할-수-있나요
∙ https://krksap.tistory.com/1706

Quick Sort 구현
∙ https://im-developer.tistory.com/135

Hash 충돌 및 해결법
∙ c언어로 풀어쓴 자료구조 546p
∙ https://preamtree.tistory.com/20

Tree Map
∙ https://coding-factory.tistory.com/557