🎮 Unity에서의 싱글톤(Singleton) 패턴

🔍 싱글톤이란?

싱글톤(Singleton)은 프로그램 전체에서 단 하나의 인스턴스만 존재하도록 보장하는 디자인 패턴이다. 게임에서는 주로 오디오 매니저, 게임 매니저, UI 매니저 등 전역적으로 접근해야 하는 매니저 클래스에 사용된다.

🧱 Unity에서의 싱글톤 구현 예시: SoundManager

public class SoundManager : MonoBehaviour
{
    public static SoundManager instance;

    private void Awake()
    {
        instance = this;
    }
}

위 코드에서 핵심은 public static SoundManager instance와 Awake()에서의 instance = this 할당이다. 이 방식으로 어디서든 SoundManager.instance를 통해 접근 가능하다.

🎯 GameManager에서도 적용된 예시

public class GameManager : MonoBehaviour
{
    public static GameManager instance;

    private void Awake()
    {
        instance = this;
    }
}

이렇게 작성하면, 다른 스크립트에서 다음처럼 쉽게 접근할 수 있다:

GameManager.instance.GameOver();

🧠 왜 사용하는가?

• 전역 접근이 필요한 매니저 클래스에 적합
• 중복 생성 방지로 안정성 향상
• 코드 간결화 (FindObjectOfType 등 비효율 제거)

⚠️ 주의할 점

• 씬에 오직 하나만 존재해야 한다 (중복 방지 필요)
• DontDestroyOnLoad(this)와 함께 사용할 수도 있음 (씬 이동 시 유지할 경우)

📘 300. Longest Increasing Subsequence

🔹 문제 설명

정수 배열 nums가 주어질 때,

배열에서 오름차순으로 증가하는 가장 긴 부분 수열의 길이를 구하라.

• 부분 수열(subsequence):(연속된 값일 필요는 없음)
• 원래 배열에서 순서를 유지하면서 일부 원소를 건너뛰어 선택할 수 있음

🔸 예시

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

설명: 가장 긴 오름차순 부분 수열은 [2, 3, 7, 101] 이므로 길이는 

🔹 조건

• 1 <= nums.length <= 2500
• 10⁴ <= nums[i] <= 10⁴

🎯 목표

👉 배열에서 가장 길게 오름차순으로 증가하는 부분 수열을 찾아서

그 길이를 반환하는 함수를 작성하는 것이 목표야.

✅ 예시 2

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
설명: [0, 1, 2, 3] 이 가장 길다

🧠 핵심 개념

이 문제는 전형적인 동적 계획법 (DP) 또는 이진 탐색을 이용한 최적화 문제야.

• 기본 DP 풀이: O(n²)
• 이진 탐색 최적화: O(n log n)

using System;

public class Program
{
    public static void Main()
    {
        int[] nums = new int[] { 10, 9, 2, 5, 3, 7, 101, 18 };

        Console.WriteLine("Input Array: " + string.Join(", ", nums));

        int result = FindLengthOfLIS(nums);

        Console.WriteLine("Longest Increasing Subsequence Length: " + result);
    }

    public static int FindLengthOfLIS(int[] nums)
    {
        int n = nums.Length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        for (int i = 0; i < n; i++)
            dp[i] = 1;  // 최소 자기 자신

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < n; i++)
            maxLength = Math.Max(maxLength, dp[i]);

        return maxLength;
    }
}

🖌️ 문제 733. Flood Fill

🔸 문제 설명

2차원 배열 image가 주어지고,

어떤 **시작 좌표 (sr, sc)**와 새로운 색상 newColor가 주어졌을 때,

시작 좌표에서 연결된 같은 색상의 픽셀들을 모두 찾아서,

해당 픽셀들을 newColor로 바꾸는 Flood Fill 알고리즘을 구현하라는 문제야.

🔹 입력

• image: 2차원 배열 (각 원소는 색상을 의미하는 정수)
• sr, sc: 시작 픽셀의 행(row), 열(column)
• newColor: 바꿀 색상 (정수)

🔹 조건

• 연결된 픽셀은 상하좌우로 인접하면서 같은 색을 가진 픽셀만 포함됨
• 대각선은 포함되지 않음 ❌

🧪 예시

Input:
image = [[1,1,1],
         [1,1,0],
         [1,0,1]],
sr = 1, sc = 1, newColor = 2

Output:
[[2,2,2],
 [2,2,0],
 [2,0,1]]

설명:

• 시작점 (1,1)의 색은 1
• 이 색과 연결된 상하좌우 방향의 픽셀을 찾아서 2로 바꿈
• image[2][2]은 색이 1이지만 연결되지 않았기 때문에 제외

🎯 목표

시작점과 연결된 모든 같은 색의 픽셀을 찾아서, 모두 newColor로 바꾼 2차원 배열을 리턴하는 함수 구현하기!

💡 핵심 개념

• Flood Fill은 대표적인 그래프 탐색 문제야.
• 방식은 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색) 중 하나를 사용해 구현할 수 있어.
• DFS가 간단하고 구현도 쉬워서 자주 사용돼.

public class Program
{
    public static void Main(string[] args)
    {
        // 이미지 배열 예시 선언 (2차원 배열)
        int[][] image = new int[][]
        {
            new int[] {1, 1, 1},
            new int[] {1, 1, 0},
            new int[] {1, 0, 1}
        };

        // 시작 위치와 새 색상 정의
        int sr = 1;
        int sc = 1;
        int newColor = 2;

        Console.WriteLine("Before Flood Fill:");
        PrintImage(image);

        FloodFill(image, sr, sc, newColor);

        Console.WriteLine("\\nAfter Flood Fill:");
        PrintImage(image);
    }

    public static void FloodFill(int[][] image, int sr, int sc, int newColor)
    {
        int originalColor = image[sr][sc];

        if (originalColor == newColor)
        {
            return;
        }

        void Fill(int row, int col)
        {
            if (row < 0 || row >= image.Length || col < 0 || col >= image[0].Length)
                return;

            if (image[row][col] != originalColor)
                return;

            image[row][col] = newColor;

            Fill(row - 1, col); // 위
            Fill(row + 1, col); // 아래
            Fill(row, col - 1); // 왼쪽
            Fill(row, col + 1); // 오른쪽
        }

        Fill(sr, sc);
    }

    public static void PrintImage(int[][] image)
    {
        for (int i = 0; i < image.Length; i++)
        {
            for (int j = 0; j < image[i].Length; j++)
            {
                Console.Write(image[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}

📘 문제 설명: Largest Rectangle in Histogram

🔸 문제 개요

너비가 1인 여러 개의 직사각형이 세로 방향으로 일렬로 나열되어 있는 히스토그램(histogram) 이 주어졌을 때,

이 중 가장 넓은 직사각형의 넓이를 구하는 문제야.

🔸 입력 예시

heights = [2, 1, 5, 6, 2, 3]

각 숫자는 해당 위치에 있는 직사각형의 높이를 의미해.

→ 이 경우, 너비 1인 직사각형이 총 6개 있고, 각각 높이는 2, 1, 5, 6, 2, 3이야.

🎯 목표

히스토그램에서 만들 수 있는 가장 넓은 직사각형의 넓이를 반환해야 해.

🔸 예시 결과

입력: [2,1,5,6,2,3]
출력: 10

→ 높이 5와 6 사이의 두 개 직사각형(5,6)을 선택하면,

가로 너비 2 × 세로 높이 5 = 10

💡 핵심 아이디어

이 문제는 스택(Stack) 을 활용해서 풀면 효율적으로 해결할 수 있어.

브루트포스 방식은 시간 복잡도가 O(n²)지만,

스택을 사용하면 O(n) 에 해결 가능

📌 주요 개념 요약

개념 설명

class Program
{
    public static int[] heights = [2, 1, 5, 6, 2, 3];

    public static void Main(string[] args)
    {
        // 넓이의 최댓값을 저장할 변수
        int maxArea = 0;

        // 인덱스를 저장할 스택 생성
        Stack<int> indexStack = new Stack<int>();

        // heights 배열을 List로 바꾸고 마지막에 높이 0짜리 막대 추가
        List<int> heightList = new List<int>();
        for (int i = 0; i < heights.Length; i++)
        {
            heightList.Add(heights[i]);
        }
        heightList.Add(0);  // 남은 스택 정리를 위한 트릭

        // 전체 막대를 하나씩 검사
        for (int i = 0; i < heightList.Count; i++)
        {
            int currentHeight = heightList[i];

            // 스택이 비어 있지 않고, 현재 막대 높이가
            // 스택 top에 해당하는 막대보다 작다면 넓이 계산
            while (indexStack.Count > 0 &&
                   currentHeight < heightList[indexStack.Peek()])
            {

                // 스택에서 pop된 인덱스를 기준으로 직사각형 만들기
                int poppedIndex = indexStack.Pop();
                int poppedHeight = heightList[poppedIndex];

                int width;

                // 스택이 비어 있다면 왼쪽 끝(0)부터 현재 인덱스 i 전까지 가능
                if (indexStack.Count == 0)
                {
                    width = i;  // 0부터 i-1까지 너비
                }
                else
                {
                    // 오른쪽은 현재 i, 왼쪽은 스택 top 다음부터 가능
                    int leftIndex = indexStack.Peek();
                    width = i - leftIndex - 1;
                }

                int area = poppedHeight * width;

                // 최대 넓이 갱신
                if (area > maxArea)
                {
                    maxArea = area;
                }
            }

            // 현재 인덱스를 스택에 저장
            indexStack.Push(i);
        }

    }
}

1. 🧠 동적 계획법 (Dynamic Programming, DP)

개념

• 복잡한 문제를 작은 하위 문제로 나누어 풀고, 결과를 저장해 재사용
• 조건: 최적 부분 구조, 중복 부분 문제

구현 방식

• Top-down: 재귀 + 메모이제이션
• Bottom-up: 반복문으로 작은 문제부터 해결

예시 (피보나치 Bottom-up)

int Fibonacci(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

대표 문제

피보나치 수열, 계단 오르기, 최소 동전, LCS, 배낭 문제

중복되는 하위 문제를 저장해 재활용하며 푸는 방법
→ 비효율적인 재귀 호출을 피하고 성능을 극대화함.

📌 대표 예시: 피보나치 수열, 계단 오르기, 최소 비용 문제

"같은 계산을 두 번 하지 않는다!"

2. 🪙 그리디 알고리즘 (Greedy)

개념

• 매 순간 최적의 선택을 하는 알고리즘
• 전체 최적을 보장하려면 특정 조건을 만족해야 함

예시 (동전 거스름돈)

int CoinChange(int[] coins, int target) {
    Array.Sort(coins); Array.Reverse(coins);
    int count = 0;
    foreach (int coin in coins) {
        count += target / coin;
        target %= coin;
    }
    return count;
}

대표 문제

동전 교환, 회의실 배정, 활동 선택, 최소 스패닝 트리

매 순간 가장 최적인 선택을 하는 방식
→ 전체 최적해가 보장되지는 않지만, 특정 조건에서는 매우 빠르고 정확함.

📌 대표 예시: 동전 거스름돈, 회의실 배정, 최소 회의 수

"지금 가장 좋은 걸 고르자!"

3. ⚔️ 분할 정복 (Divide and Conquer)

개념

• 문제를 작게 나누고, 각각 해결, 결과를 합쳐서 해결

예시 (이진 탐색)

int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

대표 문제

병합 정렬, 퀵 정렬, 이진 탐색, 거듭제곱, Karatsuba 곱셈

문제를 작게 나누고 → 각각 해결하고 → 다시 합쳐서 해결
→ 정렬, 탐색 등 대규모 데이터를 다룰 때 성능이 뛰어남.

📌 대표 예시: 퀵 정렬, 병합 정렬, 이진 탐색

"쪼개서 풀고, 다시 합쳐서 해결한다!"

4. 🔙 백트래킹 (Backtracking)

개념

• 모든 경우의 수 탐색 + 유망하지 않으면 가지치기
• DFS 기반 + 조건 검증

대표 문제

N-Queen, 스도쿠, 미로 찾기, 조합/순열 생성

모든 경우의 수를 탐색하지만, 유망하지 않으면 미리 포기(가지치기)
→ 순열/조합, 퍼즐, N-Queen 등에서 강력한 기법.

📌 대표 예시: N-Queen, 스도쿠, 조합 만들기

"정답이 아닐 것 같으면 일찍 그만두자!"

5. 🔗 유니온-파인드 (Disjoint Set / Union-Find)

개념

• 여러 노드가 같은 집합인지 판별하거나 병합
• 주로 그래프 사이클 탐지나 네트워크 연결에 사용

예시

int Find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = Find(parent, parent[x]);
    return parent[x];
}

void Union(int[] parent, int a, int b) {
    int rootA = Find(parent, a);
    int rootB = Find(parent, b);
    if (rootA != rootB) parent[rootB] = rootA;
}

여러 노드가 같은 그룹인지 빠르게 확인하고 병합하는 구조
→ 네트워크 연결, 사이클 여부 확인 등에 사용됨.

📌 대표 예시: 친구 네트워크, 그래프 사이클 판별

"넌 누구랑 같은 팀이니?"

6. 🌲 트리 탐색 (DFS / BFS)

DFS

void DFS(int node, bool[] visited, List<int>[] graph) {
    visited[node] = true;
    foreach (var next in graph[node])
        if (!visited[next]) DFS(next, visited, graph);
}

BFS

void BFS(int start, List<int>[] graph) {
    var visited = new bool[graph.Length];
    var q = new Queue<int>();
    visited[start] = true; q.Enqueue(start);
    while (q.Count > 0) {
        int node = q.Dequeue();
        foreach (var next in graph[node])
            if (!visited[next]) { visited[next] = true; q.Enqueue(next); }
    }
}

DFS: 깊이 우선 탐색 – 한 갈래로 끝까지 파고드는 방식
BFS: 너비 우선 탐색 – 가까운 노드부터 차례로 탐색

📌 대표 예시: 미로 탐색, 경로 유무 확인, 거리 계산

DFS: "끝까지 가보고 안 되면 돌아온다"
BFS: "가까운 것부터 차례로 살핀다"

7. 🚉 최단 경로 알고리즘

📍 다익스트라 (Dijkstra)

• 양수 가중치 그래프의 최단 경로
• 우선순위 큐 사용 시: O(E log V)

📍 벨만-포드 (Bellman-Ford)

• 음수 가중치 허용, 음수 사이클 탐지 가능
• 시간 복잡도: O(V × E)

📍 플로이드-워셜 (Floyd-Warshall)

• 모든 정점 쌍 간 최단 거리
• DP 기반, 시간 복잡도: O(V³)

✅ 마무리 표 (한눈에 보기)

🌉 플로이드-워셜 알고리즘 (Floyd-Warshall)

1. 개념

플로이드-워셜 알고리즘은 모든 노드 쌍 간의 최단 거리를 구하는 알고리즘이다.
음수 간선이 있어도 동작하지만, 음수 사이클이 있으면 사용 불가하다.

• 동적 계획법(DP)의 한 형태
• 인접 행렬 기반
• 3중 반복문으로 구현됨

2. 작동 원리 요약

1. dist[i][j] = i에서 j로 가는 최단 거리
2. 중간에 거쳐가는 노드 k를 하나씩 고려하면서
   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. 모든 노드 쌍에 대해 최단 거리 계산

3. C# 예제 코드

void FloydWarshall(int[,] dist, int n)
{
    for (int k = 0; k < n; k++)         // 경유지
    {
        for (int i = 0; i < n; i++)     // 출발지
        {
            for (int j = 0; j < n; j++) // 도착지
            {
                if (dist[i, k] == int.MaxValue || dist[k, j] == int.MaxValue)
                    continue;

                if (dist[i, j] > dist[i, k] + dist[k, j])
                    dist[i, j] = dist[i, k] + dist[k, j];
            }
        }
    }
}

🔹 int.MaxValue는 무한(INF)을 의미
🔹 dist[i, j]는 i에서 j로 가는 최소 거리

4. 시간/공간 복잡도

5. 특징

• 모든 쌍의 최단 거리를 구할 수 있음
• 음수 간선 허용, 단 음수 사이클은 불가
• 간단한 구현, 하지만 시간 복잡도는 높음
• 다익스트라로 V번 반복해도 되지만, 구현은 이쪽이 더 간단

6. 활용 예시

• 모든 도시 사이의 최소 이동 비용 계산
• 최단 거리 기반의 경로 분석, 그래프 분석
• 유사한 관계 그래프에서 최소 전이 분석

7. 예시

정점: 0, 1, 2  
간선:
0 → 1 (4)
0 → 2 (11)
1 → 2 (2)

→ 결과:
0 → 2 최단 경로 = 0→1→2 = 4 + 2 = 6

8. 마무리 요약

• 플로이드-워셜은 모든 정점 쌍 최단 거리가 필요할 때 사용
• DP 기반의 알고리즘이며, 구현이 간단한 편
• 음수 간선이 있어도 안전하지만 음수 사이클만은 조심

🛤️ 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

1. 개념

벨만-포드 알고리즘은 **음의 가중치(음수 간선)**가 있는 그래프에서도 단일 시작점으로부터 최단 거리를 구할 수 있는 알고리즘이다.
시간 복잡도는 크지만, 음수 간선 사이클 탐지까지 가능한 것이 특징이다.

2. 작동 원리 요약

1. 시작 노드의 거리는 0, 나머지는 무한대로 초기화
2. **(정점 수 - 1)**번 동안 모든 간선을 확인하며 거리 갱신 반복
3. 한 번 더 돌면서 거리 갱신이 일어난다면 → 음수 사이클 존재

3. C# 예제 코드

class Edge
{
    public int From, To, Cost;
    public Edge(int from, int to, int cost)
    {
        From = from;
        To = to;
        Cost = cost;
    }
}

bool BellmanFord(int vertexCount, List<Edge> edges, int start, int[] dist)
{
    for (int i = 0; i < vertexCount; i++)
        dist[i] = int.MaxValue;

    dist[start] = 0;

    for (int i = 0; i < vertexCount - 1; i++)
    {
        foreach (var edge in edges)
        {
            if (dist[edge.From] == int.MaxValue) continue;

            int newDist = dist[edge.From] + edge.Cost;
            if (newDist < dist[edge.To])
                dist[edge.To] = newDist;
        }
    }

    // 음수 사이클 확인
    foreach (var edge in edges)
    {
        if (dist[edge.From] == int.MaxValue) continue;
        if (dist[edge.From] + edge.Cost < dist[edge.To])
            return false; // 음수 사이클 존재
    }

    return true;
}

✅ dist[]: 최단 거리 배열
✅ 반환값: true면 정상, false면 음수 사이클 존재

4. 시간/공간 복잡도

• V: 정점 개수
• E: 간선 개수

5. 다익스트라 vs 벨만-포드

6. 활용 예시

• 금융 시스템 등에서 이익이 무한히 증가하는 루프 탐지
• 도로, 통신망에서 음수 간선 포함 최단 거리 문제
• 단일 시작점 기준 거리 탐색

7. 예시 그래프

정점: 0, 1, 2  
간선: (0 → 1, 1), (1 → 2, -1), (2 → 0, -1)

→ 음수 사이클 존재!

8. 마무리 요약

• 벨만-포드는 느리지만 범용적이다.
• 특히 음수 간선이나 음수 사이클 탐지가 필요한 경우 유일한 해법.
• 코딩 테스트에서도 간혹 그래프에 음수 가중치가 있을 때 등장한다.

🚀 다익스트라 알고리즘 (Dijkstra Algorithm)

1. 개념

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
음수 간선이 없을 때 사용 가능하며, **우선순위 큐(Heap)**를 이용하면 빠르게 계산할 수 있다.

2. 작동 방식 요약

1. 시작 노드에서 거리를 0으로 초기화, 나머지는 무한대로 설정
2. 아직 방문하지 않은 노드 중 가장 가까운 노드 선택
3. 선택한 노드를 기준으로 인접한 노드의 거리 업데이트
4. 모든 노드를 방문할 때까지 반복

3. C# 예제 코드 (우선순위 큐 사용)

using System;
using System.Collections.Generic;

class Edge
{
    public int To, Cost;
    public Edge(int to, int cost)
    {
        To = to;
        Cost = cost;
    }
}

class Node : IComparable<Node>
{
    public int Vertex, Distance;
    public Node(int v, int d)
    {
        Vertex = v;
        Distance = d;
    }

    public int CompareTo(Node other)
    {
        return Distance.CompareTo(other.Distance);
    }
}

void Dijkstra(int start, List<Edge>[] graph, int[] dist)
{
    int n = graph.Length;
    bool[] visited = new bool[n];
    for (int i = 0; i < n; i++) dist[i] = int.MaxValue;
    dist[start] = 0;

    var pq = new PriorityQueue<Node, int>();
    pq.Enqueue(new Node(start, 0), 0);

    while (pq.Count > 0)
    {
        pq.TryDequeue(out var current, out _);
        int now = current.Vertex;

        if (visited[now]) continue;
        visited[now] = true;

        foreach (var edge in graph[now])
        {
            int cost = dist[now] + edge.Cost;
            if (cost < dist[edge.To])
            {
                dist[edge.To] = cost;
                pq.Enqueue(new Node(edge.To, cost), cost);
            }
        }
    }
}

📌 C# 10 이상에서 PriorityQueue<TElement, TPriority> 사용 가능 (System.Collections.Generic)

4. 시간/공간 복잡도

• V: 정점 수
• E: 간선 수

5. 특징

• 음수 간선이 없는 경우에만 사용 가능
• 단일 시작점 기준 최단 거리
• BFS보다 복잡하지만 더 정확하고 빠름 (가중치 포함 가능)
• 코딩 테스트에서 그래프 문제에 자주 등장

6. 예시

정점: 0, 1, 2, 3  
간선: (0→1, 4), (0→2, 2), (2→1, 1), (1→3, 1), (2→3, 5)

출발: 0 → 도착: 모든 노드  
최단 거리: [0, 3, 2, 4]

7. 마무리 요약

• 다익스트라 알고리즘은 가장 널리 쓰이는 최단 경로 알고리즘
• 음수 가중치가 없다면 무조건 사용 가능
• 우선순위 큐를 활용하면 성능을 크게 향상시킬 수 있음
• 실전에서는 BFS vs 다익스트라의 선택이 중요함 (가중치 유무)