얌생

루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법

큐를 통해 구현한다. ( 해당 노드의 주변부터 탐색해야하기 때문 )

• 최소 비용 ( 즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때 )에 적합

시간 복잡도

• 인접 행렬 : O ( V^2 )
• 인접 리스트 : O ( V+E )

코드

#include <stdio.h>

int map[1001][1001], bfs[1001];
int queue[1001];

void init(int *, int size);

void BFS(int v, int N) {
	int front = 0, rear = 0;
	int pop;

	printf("%d ", v);
	queue[rear++] = v;
	bfs[v] = 1;

	while (front < rear) {
		pop = queue[front++];

		for (int i = 1; i <= N; i++) {
			if (map[pop][i] == 1 && bfs[i] == 0) {
				printf("%d ", i);
				queue[rear++] = i;
				bfs[i] = 1;
			}
		}
	}

	return;
}

int main(void) {

	init(map, sizeof(map) / 4);
	init(bfs, sizeof(bfs) / 4);
	init(queue, sizeof(queue) / 4);

	int N, M, V;
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		int start, end;
		scanf("%d%d", &start, &end);
		map[start][end] = 1;
		map[end][start] = 1;
	}

	BFS(V, N);

	return 0;
}

void init(int *arr, int size) {
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

DFS

 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법

스택 or 재귀함수를 통해 구현한다.

• 모든 경로를 방문해야 할 경우 사용에 적합

시간 복잡도

• 인접 행렬 : O( V^2 )
• 인접 리스트 : O ( V+E )

V는 접점, E는 간선을 뜻한다.

#include <stdio.h>

int map[1001][1001], dfs[1001];

void init(int *, int size);

void DFS(int v, int N) {

	dfs[v] = 1;
	printf("%d ", v);

	for (int i = 1; i <= N; i++) {
		if (map[v][i] == 1 && dfs[i] == 0) {
			DFS(i, N);
		}
	}

}

int main(void) {

	init(map, sizeof(map) / 4);
	init(dfs, sizeof(dfs) / 4);

	int N, M, V;
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		int start, end;
		scanf("%d%d", &start, &end);
		map[start][end] = 1;
		map[end][start] = 1;
	}

	DFS(V, N);

	return 0;
}

void init(int *arr, int size) {
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

힙 정렬은 완전 이진 트리를 기본으로 하는 힙( Heap ) 자료구조를 기반으로 한 정렬 방식을 말한다.

완전 이진 트리

삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

힙 정렬은 불안정 정렬에 속한다.

시간복잡도

평균 : O(nlogn)

최선 : Ω(nlogn)

최악 : O(nlogn)

과정

1. 최대 힙을 구성한다.

2. 현재 힙 루트에 가장 큰 값이 존재. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄인다.

3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.

루트를 마지막 노드로 대체 ( 11 -> 4 ), 다시 최대 힙을 구성

이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것을 힙 정렬이라 한다.

public void heapSort(int[] array) {
    int n = array.length;
    
    // max heap 초기화
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    
    // extract 연산
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

1번째 heapify

 - 일반 배열을 힙으로 구성하는 역할

   자식노드로부터 부모노드 비교

 n / 2-1 부터 0 까지 인덱스가 도는 이유 

   - 부모 노드의 인덱스를 기준으로 왼쪽 자식노드 ( i2 + 1 ), 오른쪽 자식 노드 ( i2 + 2 )이기 때문

2번째 heapify

 요소가 하나 제거된 이후에 다시 최대 힙을 구성하기 위함

 루트를 기준으로 진행 ( extract 연산 처리를 하기 위함 )

public void heapify(int array[], int n, int i) {
    int p = i;
    int l = i*2 + 1;
    int r = i*2 + 2;
    
    //왼쪽 자식노드
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //오른쪽 자식노드
    if (r < n && array[p] < array[r]) {
        p = r;
    }
    
    //부모노드 < 자식노드
    if(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

다시 최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap하며 재귀로 진행한다.

퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다.

하지만 힙 자료구조가 많이 활용되고 있고, 이때 합께 따라오는 개념이 힙 정렬이다.

힙 정렬이 유용할 때

- 가장 크거나 가장 작은 값을 구할 때

• 최소 힙  or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능하다.

- 최대 k 만큼 떨어진 요소들을 정렬할 때

• 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다.

전체 코드

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    heapSort(array);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
 
    if (l < n && array[p] < array[l]) {
        p = l;
    }
 
    if (r < n && array[p] < array[r]) {
        p = r;
    }
 
    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 
public static void heapSort(int[] array) {
    int n = array.length;
 
    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
 
    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

배열 - 메모리상에 원소를 연속하게 배치한 자료구조다.

배열의 성질

• O(1)에 k번째 원소를 확인 및 변경이 가능
• 추가적으로 소모되는 메모리의양( =overhead )가 거의 없다.
• 메모리 상에 데이터들이 붙어있으므로 캐시 적중률이 높다
• 메모리 상에 연속한 구간을 잡아야 하므로 할당에 제약이 걸린다.

기능과 구현

• 임의의 위치에 있는 원소를 확인 하거나 변경할때 O(1)이 걸린다.
• 원소를 끝에 추가 = O(1)
• 마지막 원소를 제거 = O(1)
• 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거 = O(N)

일반적으로 구현했을 때 안정 정렬에 속하며, 분할 정복 알고리즘의 하나다.

합병 정렬 알고리즘의 구체적인 방법

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

두 개의 정렬된 부분 리스트를 합해 전체가 정렬된 리스트가 되게 하는 방법이다.

합병 정렬은 다음의 단계로 이루어진다.

• 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.

분할 정복 방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

분할 정복 방법은 대개 순환 호출을 이용해 구현한다.

퀵 정렬 알고리즘의 구체적인 방법

하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

두 개의 정렬된 부분 리스트를 합해 전체가 정렬된 리스트가 되게 하는 방법이다.

퀵 정렬은 다음의 단계로 이루어진다.

• 분할 : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 ( 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들 )로 분할한다.
• 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소 ( 피벗 )는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

삽입 정렬의 구체적인 개념

삽입 정렬은 두 번째 자료부터 시작해 그 앞 ( 왼쪽 )의 자료들과 비교해 삽입할 위치를 지정한 후 자료를 뒤로 옮기고

지정한 자리에 자료를 삽입해서 정렬하는 알고리즘이다.

void InsertionSort(int list[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int j;
		int key = list[i];

		for (j = i - 1; j >= 0; j--)
		{
			if (list[j] > key)
			{
				list[j + 1] = list[j];
			}
			else
			{
				break;
			}
		}

		list[j + 1] = key;
	}
}

슬라이딩 윈도우 알고리즘

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘.

배열이나 리스트의 요소 중 일정 범위의 값을 비교할때 사용하면 유용하다.

• 선형 공간 ( 1차원 배열 )을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다.

예제 )

const n = 10; // N일 - 배열의 길이
const k = 3; // W 창문의 넓이
const arr = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15]; // 1차원 고정배열

function solution(n, k, arr) {
  let result = 0; // 길이 k의 부분 수열의 요소 전체 합의 최댓값
  let sum = 0; // 특정 부분 수열의 전체 합

  // 배열의 가장 왼쪽부터 k까지의 값의 합을 sum에 담음
  for (let i = 0; i < k; i++) {
    sum += arr[i];
  }

  result = sum;

  // k는 고정적이므로 새롭게 갱신되는 arr[i]와 기존 arr[i - k]를 빼줌
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    // 최대 합을 비교해서 갱신
    result = Math.max(result, sum);
  }

  return result;
}

console.log(solution(n, k, arr));

참고 :https://velog.io/@ninto_2/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

선택 정렬( Selection Sort )은 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 선택 정렬과 삽입 정렬를 헷갈릴 수 있는데, 선택 정렬은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 된다.

선택 정렬은 3가지의 과정을 반복하며 정렬을 수행한다.

 1. 선택한 곳의 데이터보다 더 작은 데이터가 있는지 순환하며 찾는다.

 2. 구한 가장 작은 최솟값을 맨 앞에 위치한 값과 교체한다.

 3. 맨 앞의 위치를 하나씩 앞으로 옮겨가며 반복한다.

#include<iostream>
using namespace std;

int main()
{
	int Array[] = { 10,9,8,7,6,5,4,2,3,1 };
	int MinIndex;
	int Number;

	for (int i = 0; i < 9; i++)
	{
        // 맨 앞 위치 선택
		MinIndex = i;

		for (int j = i + 1; j < 10; j++)
		{
            // 선택한 위치 값과 다른 위치 값들비교
            // 더 작은 값이 있으면 위치값 갱신
			if (Array[MinIndex] > Array[j])
			{				
				MinIndex = j;
			}
		}
        
        // 한번 반복하고 나면 스왑
		swap(Array[i], Array[MinIndex]);
	}

	return 0;
}

시간복잡도

데이터의 개수가 n개라고 할 경우,

• 첫 번째 회전에서의 비교횟수 : 1 ~ ( n - 1 ) => n - 1
• 두 번째 회전에서의 비교횟수 : 2 ~ ( n - 1 ) => n - 2
• ...
• (n-1) + (n-2) + ... + 2 + 1 => n(n-1) / 2

비교하는 것이 상수 시간에 이루어진다는 가정 아래에서 n개의 주어진 배열을 정렬하는데

O( n^2 ) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O( n^2 )로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

버블 정렬이란, 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면

자리를 바꾸는 정렬 알고리즘을 말한다.

이름의 유래는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

버블 정렬 알고리즘의 구체적인 방법

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두번째 자료와 세 번째 자료를 .. 이런 식으로 ( 마지막 - 1 )번째 자료와 마지막 자료를 비교해 교환하면서 자료를 정렬한다.

void BubbleSort(int list[], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			// 현재 위치와 앞 위치 데이터 비교
			// 현재 위치 데이터가 더 크면 스왑
			if (list[j] > list[j + 1])
			{
				swap(list[j], list[j + 1]);
			}
		}
	}
}

시간복잡도

시간복잡도를 계산하면, ( n - 1 ) + ( n - 2 ) + ( n -3 ) + .... + 2 + 1 => n(n-1)/2 이므로, O(n^2)다.

또한, Bubble Sort는 정렬이 되어있던 안되어있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두

시간 복잡도가 O(n^2)로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

장점

• 구현이 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. ( 제자리 정렬 )
• 안정 정렬(Stable Sort)이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 되어있지 않은 원소가 정렬 되었을때의 자리로 가기 위해, 교환 연산(swap)이 많이 일어나게 된다.