search

kyurimki / CS_Study

0 stars 0 forks source link

자료구조(Data Structure) 정리 #1

Open kyurimki opened 2 years ago

kyurimki commented 2 years ago

[Contents] 1.

2.

3.

4.

5.

jaejlf commented 2 years ago

Graph

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료 구조

그래프를 탐색한다 = 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

너비 우선 탐색 (BFS, Breadth-First Search)

루트 혹은 임의의 노드에서 시작하여 인접한 노드를 모두 탐색한 후, 다음 depth를 탐색

  • 큐를 이용하여 구현 (즉, FIFO 원칙으로 탐색)
  • 최단거리 구하기 문제에서 활용
  • 탐색 대상의 규모가 크지 않고, 목표 대상이 멀지 않을 때 활용

장점


단점


인접 행렬 BFS

인접 리스트 BFS



깊이 우선 탐색 (DFS, Depth-First Search)

루트 혹은 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후 돌아와 다른 노드로 탐색하는 방식

  • 재귀함수 혹은 스택 으로 구현
  • 노드 방문 시 visited 여부를 반드시 검사해야한다. ⇒ 그렇지 않을 경우, 무한 루프에 빠질 가능성 !
  • 경로의 특징을 저장해두어야 하는 문제에서 활용
  • 탐색 대상 그래프의 규모가 클 경우 활용

장점


단점


인접 행렬 DFS

인접 리스트 DFS



BFS vs DFS 비교



다익스트라(Dijkstra)

동작 원리

  1. 시작 노드와 이웃한 모든 노드들의 거리를 비교한 후, 시작 노드를 방문한 노드로 체크한다.
  2. 방문한 노드들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고 해당 정점을 방문한 정점으로 선택한다.
  3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.
  4. 2-3번 과정을 반복한다.



Spanning Tree

= 신장 트리 그래프의 최소 연결 부분 그래프 (즉, 그래프에서 일부 간선을 선택해서 만든 트리)


MST (Minimum Spanning Tree)

= 최소 신장 트리 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것

  • 간선의 가중치의 합이 최소여야 한다.
  • n개의 정점을 가지는 그래프에 대해 반드시 n - 1개의 간선만을 사용해야 한다.
  • 사이클이 포함되어서는 안된다.


크루스칼 알고리즘

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

  • 각 단계에서 사이클을 이루지 않는 최소 비용 간선 선택
  • 간선 선택을 기반으로 하는 알고리즘
  • 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법


구현

  1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
  2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
    1. 즉, 가장 낮은 가중치를 먼저 선택한다.
    2. 사이클을 형성하는 간선을 제외한다.
  3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.


프림 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

  • 정점 선택을 기반으로 하는 알고리즘
  • 이전 단계에서 만들어진 신장 트리를 확장하는 방법


구현

  1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
  2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
    1. 즉, 가장 낮은 가중치를 먼저 선택한다.
  3. 위의 과정을 트리가 n - 1개의 간선을 가질 때까지 반복한다.
younglove321 commented 2 years ago

Sorting Algorithms

1. Bubble Sort (버블 정렬)

버블정렬은 가장 쉬운 정렬 알고리즘이지만 시간복잡도가 좋은 퍼포먼스를 내지 못해서 실제로는 잘 사용되지 않는다. 버블 정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다.

시간복잡도 : O(n²) 공간복잡도: 히나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)이다.

2. Heap Sort (힙 정렬)

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

  1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.

  2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.

  3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.

  4. 2와 3을 반복한다.

3. Merge Sort (병합 정렬)

병합 정렬은 분할정복(Divide and Conquer)의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병합정렬을 사용한다면 아래와 같은 3단계의 과정을 거치게 된다.

  1. Divide(분할) : n개의 원소를 갖는 배열을 n/2 개의 원소를 갖는 작은배열 2개로 나눈다.
  2. Conquer(정복) : 각각의 작은 배열들을 정렬한다.
  3. Combine(병합) : 정렬된 작은 배열들을 병합한다.

Not-in-place 알고리즘 : 별도의 데이터 저장소 필요 In-Place는 입력리스트 내부에서 정렬이 이뤄지는 경우를 가리키며, 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우. 병합정렬의 경우 입력리스트를 분할해 이를 정렬하고 다시 합치는 과정에서 분할된 리스트를 별도로 저장해 두어야 한다.

4. Quick Sort (퀵 정렬)

합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다. 정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.

  1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.
  2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
  3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다. 3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.

퀵정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용된다. 이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로 공간복잡도는 O(nlogn)이다

• 퀵정렬은 최악의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정된다면 원소 n개에 대해서 n번, (n-1)번, (n-2)번...1번 의 비교가 필요하므로 시간 복잡도가 O(n^2) 된다. • 하지만 평균 시간 복잡도는 O(nlogn)으로 매우 빠르다. pivot 값이 적절히 설정된다면 그 속도가 매우 빠르다. 따라서 pivot값을 잘 설정하는 것이 중요하다. • 퀵 정렬은 중복된 키값이 순서대로 바뀌지 않을 수 있어 (예를 들어 {7,7,1}을 오름차순으로 퀵정렬해보라) not-stable 하다.

5. Radix Sort (기수 정렬)

데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법이며 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능. 각 자리수를 기준으로 점차 정렬을 진행한다.

정렬할 숫자의 자릿수를 d라고 하면 시간 복잡도는 O(dn)으로 표현. 예)가장 큰 수가 12345라면, 자리수는 5이므로 O(5n)

기수정렬은 '버킷'이라는 추가적인 공간할당이 필요하다. 가장 일반적으로 사용되는 것이 Queue

6. Selection Sort (선택 정렬)

현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 주어진 자료들 중에 현재 위치에 맞는 자료를 찾아 선택하여 위치를 교환하는 정렬 알고리즘이다.

정렬 순서가 맞지 않으면 무조건 자리를 바꿔줬던 버블정렬과 달리, 1회 iteration마다 최소값(혹은 최대값)을 찾고 단 한번만 해당 요소 위치를 바꿔줌 --> swap의 수 상당히 감소

한번 순회를 돌게되면 알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하게 되므로 그 다음 순회부터는 1번 인덱스부터 순회를 돌며 반복하면 된다.

  1. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다.
  2. 그다음 두 번째로 작은 원소를 찾아서 선택하여 두 번째 원소와 자리를 교환한다.
  3. 그다음에는 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환한다.
  4. 이 과정을 반복하면서 정렬이 완성된다.

정렬 알고리즘 간 비교

(시간복잡도, 공간복잡도, 효율성 ... ) 단순(구현 간단)하지만 비효율적인 방법 :삽입 정렬, 선택 정렬, 버블 정렬 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

kyurimki commented 2 years ago

Tree

calicedev commented 2 years ago

1. 배열 (Array)

2. 연결리스트 (linked list)

3. stack

4. queue

shpark0308 commented 2 years ago

탐색

▪ 이분탐색

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

▪ 순차탐색

int sequentialSearch(int dataArr[], int length, int findData) {
        for(int i = 0; i < length; i++) 
                if (dataArr[i] == findData) return i; 
        return -1; 
}

▪ 해시탐색

▪ heap

[ 힙 종류 ]
image https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

▪ hashing / hashtable