[멋쟁이사자차럼 부트캠프] 유니티 게임 개발 5기 - 40일차 : 다익스트라 / 정렬 알고리즘

1. 다익스트라 알고리즘

---

정의

• 그래프에서 하나의 시작 노드로부터 모든 노드까지의 최단 거리를 구하는 알고리즘.
• 양의 가중치를 가진 그래프에서 사용하며, 대표적인 최단 경로 탐색 알고리즘

---

핵심 로직

1. 시작 노드에서 거리 0, 나머지는 무한대로 초기화
2. 방문하지 않은 노드 중 가장 짧은 거리 선택
3. 해당 노드를 거쳐 갈 때 더 짧은 경로가 있다면 업데이트
4. 모든 노드를 방문할 때까지 반복

---

전체 코드 (DijkstraSearch.cs)

using UnityEngine;

public class DijkstraSearch : MonoBehaviour
{
    private int[,] nodes = new int[6, 6]
    {
        { 0, 1, 2, 0, 4, 0 },
        { 1, 0, 0, 0, 0, 8 },
        { 2, 0, 0, 3, 0, 0 },
        { 0, 0, 3, 0, 0, 0 },
        { 4, 0, 0, 0, 0, 2 },
        { 0, 8, 0, 0, 2, 0 },
    };

    void Start()
    {
        int start = 0;
        int[] dist;
        int[] prev;

        Dijkstra(start, out dist, out prev);

        for (int i = 0; i < nodes.GetLength(0); i++)
            Debug.Log($"{start}에서 {i}까지 최단 거리 : {dist[i]}, 경로 : {GetPath(i, prev)}");
    }

    private void Dijkstra(int start, out int[] dist, out int[] prev)
    {
        int n = nodes.GetLength(0);
        dist = new int[n];
        prev = new int[n];
        bool[] visited = new bool[n];

        for (int i = 0; i < n; i++)
        {
            dist[i] = int.MaxValue;
            prev[i] = -1;
            visited[i] = false;
        }

        dist[start] = 0;

        for (int cnt = 0; cnt < n; cnt++)
        {
            int u = -1;
            int min = int.MaxValue;

            for (int j = 0; j < n; j++)
            {
                if (!visited[j] && dist[j] < min)
                {
                    min = dist[j];
                    u = j;
                }
            }

            if (u == -1)
                break;

            visited[u] = true;

            for (int k = 0; k < n; k++)
            {
                if (nodes[u, k] > 0 && !visited[k])
                {
                    int newDist = dist[u] + nodes[u, k];
                    if (newDist < dist[k])
                    {
                        dist[k] = newDist;
                        prev[k] = u;
                    }
                }
            }
        }
    }

    private string GetPath(int end, int[] prev)
    {
        if (prev[end] == -1)
            return end.ToString();

        return $"{GetPath(prev[end], prev)} -> {end}";
    }
}

---

핵심 코드 설명

1) 그래프 인접 행렬 정의

private int[,] nodes = new int[6, 6]

• 2차원 배열로 그래프의 간선과 가중치를 표현
• 0이면 연결되지 않음, 나머지는 거리

---

2) 거리 및 방문 상태 초기화

for (int i = 0; i < n; i++)
{
    dist[i] = int.MaxValue;
    prev[i] = -1;
    visited[i] = false;
}
dist[start] = 0;

• 모든 노드의 최단 거리를 무한대로 설정
• 출발 노드는 거리 0
• prev[]는 경로를 추적하기 위한 배열

---

3) 방문하지 않은 노드 중 가장 가까운 노드 선택

for (int j = 0; j < n; j++)
{
    if (!visited[j] && dist[j] < min)
    {
        min = dist[j];
        u = j;
    }
}

• 현재까지 거리 중 가장 작은 노드 u를 선택

---

4) 인접 노드 거리 갱신

if (nodes[u, k] > 0 && !visited[k])
{
    int newDist = dist[u] + nodes[u, k];
    if (newDist < dist[k])
    {
        dist[k] = newDist;
        prev[k] = u;
    }
}

• 아직 방문하지 않은 인접 노드에 대해 더 짧은 거리라면 갱신
• prev[k] = u를 통해 경로 저장

---

알고리즘 요약

• 시간 복잡도: O(n²) (우선순위 큐를 사용하면 O(E log V))
• 조건: 양의 가중치 그래프
• 특징: BFS보다 느리지만 정확한 거리 계산 가능

 

2. 선택 정렬 (Selection Sort)

---

개념

• 배열에서 가장 작은 값을 찾아 맨 앞에 위치시키는 작업을 반복하는 정렬 알고리즘
• 마치 정렬되지 않은 데이터에서 최솟값을 하나씩 골라 맨 앞으로 옮기는 방식

---

동작 원리

1. 첫 번째 인덱스를 기준으로 삼고, 이후 요소들 중에서 가장 작은 값을 탐색
2. 가장 작은 값이 현재 기준보다 앞쪽에 있다면 교환
3. 기준 인덱스를 하나씩 오른쪽으로 이동하며 위 작업을 반복
4. 전체 배열이 정렬될 때까지 계속

---

정렬 예시

초기 배열: [5, 3, 8, 1, 2]

• i = 0 → 가장 작은 값 1 → 0번 인덱스와 교환 → [1, 3, 8, 5, 2]
• i = 1 → 가장 작은 값 2 → 1번 인덱스와 교환 → [1, 2, 8, 5, 3]
• i = 2 → 가장 작은 값 3 → 2번 인덱스와 교환 → [1, 2, 3, 5, 8]
• i = 3 → 가장 작은 값 5 → 이미 제자리 → 정렬 완료

---

특징

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)
• 정렬 방식: 비교 기반, 제자리 정렬
• 장점: 구현이 간단하고 교환 횟수가 적음
• 단점: 효율이 낮고, 안정 정렬이 아님 (같은 값의 순서가 보장되지 않음)

---

전체 코드 (SelectionSort.cs)

using UnityEngine;

public class SelectionSort : MonoBehaviour
{
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };

    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Selection(array);

        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Selection(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n - 1; i++)
        {
            int minIdx = i;

            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[minIdx])
                    minIdx = j;
            }

            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

---

핵심 코드

1) 배열 순회 및 최소값 인덱스 선택

for (int i = 0; i < n - 1; i++)
{
    int minIdx = i;

• 현재 위치 i를 기준으로 최소값을 찾기 시작

---

2) 현재 위치 이후 요소 중 최소값 탐색

for (int j = i + 1; j < n; j++)
{
    if (arr[j] < arr[minIdx])
        minIdx = j;
}

• i 이후의 인덱스 중 가장 작은 값을 찾고 minIdx에 저장

---

3) 현재 위치와 최소값 위치를 교환

int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;

• i와 minIdx를 교환해 정렬 순서를 맞춤

---

알고리즘 설명

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1) (추가 메모리 없음)
• 정렬 방식: 최소값을 선택해 앞쪽으로 정렬
• 특징: 교환 횟수는 적지만, 비교는 많음 / 불안정 정렬

 

3. 삽입 정렬 (Insertion Sort)

---

개념

• 이미 정렬된 부분에 새로운 값을 적절한 위치에 삽입하여 정렬 상태를 유지하는 알고리즘
• 사람이 카드 손에 쥐고 정렬하는 방식과 유사함

---

동작 원리

1. 배열의 두 번째 요소부터 시작하여 정렬 대상(key)으로 선택
2. key 앞에 있는 요소들과 비교하며 자신보다 큰 값은 오른쪽으로 한 칸 이동
3. 적절한 자리에 key를 삽입
4. 다음 요소로 넘어가면서 위 과정을 반복

---

정렬 예시

초기 배열: [5, 3, 8, 1, 2]

• i = 1, key = 3 → 5보다 작음 → [3, 5, 8, 1, 2]
• i = 2, key = 8 → 5보다 크다 → 그대로 유지
• i = 3, key = 1 → 8 > 5 > 3 → [1, 3, 5, 8, 2]
• i = 4, key = 2 → 8 > 5 > 3 → [1, 2, 3, 5, 8]

---

특징

• 시간 복잡도: O(n²), 단 거의 정렬된 상태에서는 O(n)
• 공간 복잡도: O(1)
• 정렬 방식: 비교 기반, 제자리 정렬
• 장점: 구현이 간단하며, 거의 정렬된 데이터에 매우 효율적
• 단점: 데이터가 역순일 경우 비효율적, 평균 성능 낮음
• 안정 정렬: 동일한 값의 순서가 유지됨

---

전체 코드 (InsertionSort.cs)

using UnityEngine;

public class InsertionSort : MonoBehaviour
{
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };

    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Insertion(array);

        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Insertion(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }
}

---

핵심 코드

1) 정렬 대상 원소 선택

int key = arr[i];
int j = i - 1;

• 현재 정렬할 대상은 key, 그 앞쪽 요소부터 비교 시작

---

2) 정렬된 구간에서 적절한 위치 찾기

while (j >= 0 && arr[j] > key)
{
    arr[j + 1] = arr[j];
    j--;
}

• key보다 큰 값은 한 칸 뒤로 이동하며 빈칸을 만든다

---

3) key 삽입

arr[j + 1] = key;

• 적절한 위치에 key 삽입하여 정렬된 상태 유지

---

알고리즘 설명

• 시간 복잡도: O(n²), 단 정렬된 데이터일수록 빠름 (최선 O(n))
• 공간 복잡도: O(1)
• 정렬 방식: 앞쪽 정렬된 배열에 끼워 넣는 방식
• 특징: 안정 정렬, 구현 쉬움

 

4. 버블 정렬 (Bubble Sort)

---

개념

• 버블 정렬은 배열을 순회하면서 인접한 두 요소를 비교하여 큰 값을 오른쪽으로 계속 밀어내는 방식의 정렬 알고리즘
• 각 회차마다 가장 큰 값이 마지막으로 "떠오르듯" 옮겨가기 때문에 ‘버블’ 이라는 이름이 붙여짐

---

동작 원리

1. 배열의 처음부터 끝까지 인접한 두 값을 비교
2. 왼쪽 값이 오른쪽 값보다 크면 둘을 교환
3. 한 번의 전체 순회가 끝나면 가장 큰 값이 가장 뒤에 위치
4. 정렬되지 않은 구간의 크기를 줄이며 위 과정을 반복

---

정렬 예시

초기 배열: [5, 3, 8, 1, 2]

• 1회전: [3, 5, 1, 2, 8]
• 2회전: [3, 1, 2, 5, 8]
• 3회전: [1, 2, 3, 5, 8]
• 4회전: 정렬 완료

---

특징

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)
• 정렬 방식: 비교 기반, 제자리 정렬
• 장점: 구현이 매우 간단함
• 단점: 성능이 가장 느린 편, 데이터가 많을수록 비효율적
• 안정 정렬: 동일한 값의 순서를 보존함

---

전체 코드 (BubbleSort.cs)

using UnityEngine;

public class BubbleSort : MonoBehaviour
{
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };

    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Bubble(array);

        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Bubble(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

---

핵심 코드

1) 바깥 루프 - 회전 수 제어

for (int i = 0; i < n - 1; i++)

• 총 n-1회 반복, 정렬이 완료될 때까지 진행

---

2) 안쪽 루프 - 인접한 요소 비교 및 교환

if (arr[j] > arr[j + 1])
{
    int temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
}

• 왼쪽 값이 크면 오른쪽 값과 교환하여 큰 값을 뒤로 보냄

---

알고리즘 설명

• 시간 복잡도: O(n²), 최선 O(n) (이미 정렬 시)
• 공간 복잡도: O(1)
• 정렬 방식: 큰 값을 오른쪽으로 밀어냄
• 특징: 매우 직관적, 비효율적이지만 학습용으로 많이 사용

 

5. 퀵 정렬 (Quick Sort)

---

개념

• 퀵 정렬은 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘.
• 배열에서 하나의 값을 기준(pivot)으로 정하고, 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 다음 각각을 재귀적으로 정렬함.

---

동작 원리

1. 기준 값(pivot)을 하나 선택 (보통 가장 오른쪽 값)
2. 배열을 순회하며 pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 배치
3. pivot을 정확한 위치로 옮김
4. pivot을 기준으로 나뉜 좌/우 서브 배열에 대해 재귀 호출
5. 서브 배열이 더 이상 나뉠 수 없을 때 정렬 완료

---

정렬 예시

초기 배열: [5, 3, 8, 1, 2]

• pivot = 2 → 왼쪽 [1], 오른쪽 [5, 3, 8]
• 왼쪽 [1]은 정렬 완료
• 오른쪽 [5, 3, 8] → pivot = 8 → 왼쪽 [5, 3], 오른쪽 []
• [5, 3] → pivot = 3 → 왼쪽 [], 오른쪽 [5]
• 정렬 결과: [1, 2, 3, 5, 8]

---

특징

• 평균 시간 복잡도: O(n log n)
• 최악 시간 복잡도: O(n²) (pivot이 계속 한쪽 끝이면)
• 공간 복잡도: O(log n) (재귀 스택)
• 정렬 방식: 분할 정복, 재귀 기반
• 장점: 대부분의 경우 매우 빠름, 실무에서 널리 사용됨
• 단점: 최악의 경우 O(n²), pivot 선택이 중요
• 불안정 정렬: 동일한 값의 순서를 보장하지 않음

---

전체 코드 (QuickSort.cs)

using UnityEngine;

public class QuickSort : MonoBehaviour
{
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };

    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Quick(array, 0, array.Length - 1);

        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Quick(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            Quick(arr, left, pivot - 1);
            Quick(arr, pivot + 1, right);
        }
    }

    private int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];
        int index = left - 1;

        for (int i = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                index++;
                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
            }
        }

        int temp2 = arr[index + 1];
        arr[index + 1] = arr[right];
        arr[right] = temp2;

        return index + 1;
    }
}

---

핵심 코드

1) 분할 정복 재귀

Quick(arr, left, pivot - 1);
Quick(arr, pivot + 1, right);

 

• pivot을 기준으로 좌/우를 나누어 재귀 정렬

---

2) 분할 함수 (Partition)

int pivot = arr[right];
int index = left - 1;

• 기준 값 pivot을 배열 끝에서 선택
• pivot보다 작은 값들을 앞쪽으로 모음

---

3) pivot 정렬 위치에 배치

arr[index + 1] = arr[right];
arr[right] = temp2;

• pivot을 올바른 위치에 배치하고 그 인덱스를 반환

---

알고리즘 설명

• 시간 복잡도: 평균 O(n log n), 최악 O(n²)
• 공간 복잡도: O(log n) (재귀 스택)
• 정렬 방식: 기준점(pivot)을 정해 분할 정복 방식으로 정렬
• 특징: 매우 빠른 정렬 알고리즘, 실무에서도 자주 사용

 

6. 정리 요약표

---

알고리즘	시간 복잡도	핵심 특징
다익스트라	O(n²) / O(E log V)	최단 거리 탐색, 양의 가중치 그래프
선택 정렬	O(n²)	전체 탐색 후 최소값 선택
삽입 정렬	O(n²)	정렬된 부분에 삽입하는 방식
버블 정렬	O(n²)	인접한 값들을 swap하며 정렬
퀵 정렬	O(n log n)	pivot 기준 분할 정복 방식