전체 글 (114)

10
29

 

안녕하세요.

유니티 싱글톤에 대해서 모르시는 분은 없을거라고 생각합니다.

다만 매번 클래스에서 싱글톤을 구현하실 때 코드가 많이 더러워지는데요.

이런분들을 위해 싱글톤을 구현한 클래스를 상속하면 바로 쓸 수 있게 템플릿을 준비했습니다.

 

아래 템플릿 코드를 그냥 복사 붙여넣기하시거나 파일 다운하시면 됩니다.

바로 코드를 봅시다.

 

MMSingleton.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// Singleton pattern.
/// </summary>
public class MMSingleton<T> : MonoBehaviour where T : Component
{
    protected static T _instance;
    public static bool HasInstance => _instance != null;
    public static T TryGetInstance() => HasInstance ? _instance : null;
    public static T Current => _instance;

    /// <summary>
    /// Singleton design pattern
    /// </summary>
    /// <value>The instance.</value>
    public static T Instance
    {
        get
        {
            if (_instance == null)
            {
                _instance = FindObjectOfType<T>();
                Create(true);
            }
            return _instance;
        }
    }
    public static void Create()
    {
        if (_instance == null)
        {
            GameObject obj = new GameObject(typeof(T).Name);
            obj.name = typeof(T).Name + "_AutoCreated";
            _instance = obj.AddComponent<T>();
        }
    }
    public static void Create(bool dontDestroy)
    {
        if (_instance == null)
        {
            GameObject obj = new GameObject(typeof(T).Name);
            obj.name = typeof(T).Name + "_AutoCreated";
            _instance = obj.AddComponent<T>();
            if(dontDestroy) DontDestroyOnLoad(obj);
        }
    }

    /// <summary>
    /// On awake, we initialize our instance. Make sure to call base.Awake() in override if you need awake.
    /// </summary>
    protected virtual void Awake()
    {
        InitializeSingleton();
    }

    /// <summary>
    /// Initializes the singleton.
    /// </summary>
    protected virtual void InitializeSingleton()
    {
        if (!Application.isPlaying)
        {
            return;
        }

        _instance = this as T;
    }
}

MMSingleton.cs
0.00MB

 

 

코드를 간단히 보자면 Instance를 호출했을 때 없다면 새로 생성하고 씬 전환시 Don't Destroy하도록 되어있습니다.

그리고 Awake() 함수에서 초기화가 되는걸 볼 수 있습니다.


사용법

 

사용하실 땐 싱글톤으로 만들 클래스에서 MMSingleton<클래스이름> 이런식으로 상속하면됩니다.

public class Global : MMSingleton<Global>
{
	
}

네 이게 답니다.

 

상속에 대해서 잘 모르겠다면 아래글을 참고하시기바랍니다.

https://kimyir.tistory.com/18

 

유니티 C#의 필수 개념! 상속(inheritance)에 대해 알아보자

이전에 올린 글들에서 계속 상속이 나왔다. 그만큼 상속은 객체지향적인 C#에게 필수적이다. 오늘은 상속을 알아보도록 하자 늘 그렇듯 공식 메뉴얼은 훨씬 디테일하다. 마이크로소프트 C# 상속

kimyir.tistory.com

 

장점 ①

 

외부 클래스에서 Global.cs 싱글톤으로 접근한다면 어떻게 해야할까요?

평소 여러분이 생각한대로면 Global.instance.메서드() 이런식으로 instance 키워드 붙여야해서 복잡했을겁니다.

 

그런데 MMSingleton에선 그냥 Global.메서드() 이렇게 호출해도 됩니다.

Global의 인스턴스가 생성안됐다면 호출한 순간에 생성되니 문제 없습니다.

예시코드)

using System.Numerics;
public class CashManager
{
    public BigInteger Cash;

    public void AddCash(BigInteger amt)
    {
        Cash += amt;
        Global.UserDataManager.SetCashData(Cash);
    }
}

 

장점 ②

 

그리고 싱글톤으로 선언된 Global.cs의 내부에 그냥 다른 싱글톤으로 만들 클래스들을 몰아넣어서 굳이 개별적으로 싱글톤을 작성할 필요가 없습니다. 그냥 하나의 싱글톤으로 선언된 클래스에 모아놔도 다 접근이 되는겁니다.

예를 들어 Global.클래스이름.메서드() 이런식으로 접근이 가능합니다.

 

예시코드)

public class Global : MMSingleton<Global>
{
    public static SceneBase CurrentScene { get; set; }
    public static UIManager UIManager { get; private set; }
    public static UserDataManager UserDataManager { get; set; }
}

 

 


주의점

사실 하나의 싱글톤 Global.cs에 다 몰아 넣는 이유는 순서 보장하는 이유가 가장큽니다.

만일 서로 다른 싱글톤 인스턴스를 호출했을 때 뒤늦게 인스턴스 생성하게 되면 Null 에러가 자주 뜹니다.

그렇기에 하나에 몰아넣어서 Global.cs는 게임 시작시 바로 호출되게 하는 방식으로 관리하면 좋습니다.

씬에서 생성해야하는 인스턴스는 따로 또 씬에 싱글톤 객체를 미리 만들어두면 됩니다.

 

또한 인스턴스 생성시 MMSingleton.cs를 보시면 알겠지만 유니티의 Awake() 함수를 사용합니다.

때문에 상속한 뒤 Awake()에서 처리하실게 있다면 override 키워드로 하위 클래스에서 Awake를 오버라이드해주시면 됩니다.

그리고 오버라이드된 Awake() 내부는 base.Awake();로 싱글톤 처리를 먼저해주셔야합니다. 

 

여하튼 이렇게 오늘 한번 상속으로 사용하는 싱글톤 템플릿을 소개해드려봤습니다.

클래스:MMSingleton<클래스> 이것만 익숙해지면 굉장히 편한 것 같습니다.

즐거운 개발되시길 바랍니다.

COMMENT
 
10
20

 

Punch Card

Radix Sort 을 다루기 전에 Punch Card를 알아봅시다.
punch card는 한국어로 천공 카드인데요.

이게 바로 punch card입니다. 이게 프로그래밍의 시초인데요.
보다시피 숫자가 3자리씩 나열된걸 볼 수 있습니다.
이중 만약 백의 자리수는 2, 십의 자리수는 4, 일의 자리수는 1이  뚫려있다면 241이라는 숫자를 알게되는겁니다.
 
구멍을 뚫어서 숫자를 지정한 뒤 이걸 정렬하는 방식이 Radix Sort, 기수 정렬이었던겁니다.

각각 3자리 수를 구멍 뚫어서 만든 카드를 우린 0번부터 9번까지 정렬해야합니다.
이때 가장 큰 수는 맨 아래에, 가장 작은 수는 맨 위에 오도록 정렬해야합니다.
이때 이용하는 방식이 바로 기수 정렬입니다.
 


 

기수 정렬 (Radix Sort)

 

 
말로 설명하는것보다 눈으로 보는게 가장 편합니다.
보다시피 일의 자리수를 기준으로 먼저 가장 작은 수 부터 큰수까지 정렬해주고,
그다음 십의 자리수, 백의 자리수 까지 정렬해주면 됩니다.
그러면 우리는 3자리 수의 작은 수 부터 큰 수까지 정렬을 끝낸것과 같습니다.
 
 

패스 수에 대한 유도(의사 코드에서는 i)


숫자 1, 2, . . . , i − 1이 정렬됩니다.
숫자 i에 대한 안정적인 정렬이 정렬된 결과를 제공한다는 것을 입증해봅시다.
i 위치의 2자리 숫자가 다를 경우 i 위치순으로 정렬하는 것이 맞으며, 1, . . . , i − 1은 관련이 없습니다.
i 위치의 두 숫자가 같다면 숫자는 이미 올바른 순서로 되어 있는 것입니다(귀납적 가설에 따르면). 
따라서 숫자 i의 안정적인 정렬은 올바른 순서로 유지됩니다.

계산 정렬을 중간 정렬로 사용한다고 가정합니다.
패스당 Θ(n + k)(0, . . . , k 범위의 숫자)
d 패스
Θ(d(n + k)) 합계
k = O(n)이면 시간 = Θ(dn)입니다.
 
결론.  Θ(n) 시간 복잡도를 가집니다.
 


 
각 키를 숫자로 나누는 방법은 뭘까요?
 
1. n개의 단어(words)를 정렬합니다.
2. 각 단어는 b 비트로 구성됩니다.
3. 이를 r-비트 자릿수로 나눕니다. 이때 d = ⌈b/r⌉ (b를 r로 나눈 후 올림)입니다.
4. 계수 정렬을 사용하며, k = 2^r - 1 입니다. (r-비트로 표현할 수 있는 최대값)
5. 예시: 32-비트 단어를 8-비트 자릿수로 나누는 경우
   - b = 32, r = 8
   - d = 32/8 = 4 (4개의 자릿수로 나눔)
   - k = 2^8 - 1 = 255 (0부터 255까지의 값 가능)
6. 시간 복잡도: Θ((b/r)(n + 2^r))
   - b/r은 패스 횟수
   - n + 2^r은 각 패스에서의 계수 정렬 시간
 
Buckets Counts  = k = 2^r 부분이고
 
큰 키 값을 작은 자릿수로 나누어 효율적으로 정렬하는 기수 정렬의 원리였습니다.
 

COMMENT
 
10
20

 

Counting Sort는 말 그대로 각 숫자가 몇 번 등장했는지를 세는 정렬입니다.

 

(a) 상황 - 배열 A에서 나온 각 값의 등장 횟수를 배열 C에 담아줍니다.

(b) 상황 - 배열 C에 들어있던 횟수들을 누적합으로 새로 C 배열을 구성합니다.

C = [2, 2, 4, 7, 7, 8] 보면 0이 두 번 2가 두 번 3이 세 번 5가 한 번 등장해서

2+2+3+1 = 8 해서 새로 구성한 누적합 마지막 요소가 8인것입니다. 

(c) 상황 - 이제 배열 A의 마지막 인덱스부터 하나하나 정렬해봅시다.

배열 A의 마지막 인덱스 8의 숫자 3을 누적합 배열 C를 통해 새로 B 배열에 배치하면 3이 들어갈 곳은 7번이네요. 

배치한 뒤에는 배열 C에 있는 3의 누적합을 1 감소합니다.

(d) 상황 - 배열 A의 7번째 숫자는 0이므로 배열 C에서 0의 위치가 2라는걸 확인 후 배열 B의 2번에 0을 배치합니다.

배치한 뒤에는 배열 C에 있는 0의 누적합을 1 감소합니다.

(e) 상황 - 배열 A의 6번째 숫자는 3이므로 배열 C에서 3의 위치가 6라는걸 확인 후 배열 B의 6번에 3을 배치합니다.

배치한 뒤에는 배열 C에 있는 3의 누적합을 1 감소합니다.

이렇게 배치한 결과 (f) 배열 B에는 잘 정렬된 결과를 볼 수 있습니다.

 


 

특징

 

계수 정렬은 동일한 값을 가진 요소들의 상대적 순서를 유지합니다.

 

k ≤ n

k는 정렬할 수 있는 최대 키 값, n은 입력 배열의 크기입니다.

만약에 100명의 학생 (배열의 크기)가 있다면 0~100점 사이에서 5개의 키값이 [25,45, 75, 29, 100] 점 이렇게 있다면

k = 5가 되기 때문에 이 조건에 부합합니다.

이 때 k의 값이 항상 n보다 작거나 같다면 계수 정렬은 안정적 정렬(stable sort)입니다.

 

시간 복잡도 분석:
Step 1: Θ(k) - 계수 배열 초기화
Step 2: Θ(n) - 입력 배열 순회하며 계수
Step 3: Θ(k) - 계수 배열의 누적 합 계산
Step 4: Θ(n) - 정렬된 배열 생성
총 시간 복잡도: Θ(n+k)
모든 단계를 합하면 Θ(n+k)가 됩니다.

그렇기 때문에 만약에 이 때 k가 n을 뛰어넘게 된다면 k > n이라면 O(n) 시간 복잡도가 아닙니다.

k가 더 영향이 크기 때문에 O(k)가 됩니다.

 

COMMENT
 
10
20

 

우선 상황을 가정해봅시다.

3개 요소 1, 2 ,3으로 나열 될 수 있는 경우의 수는 다음과 같습니다.


<1,2,3>, <1,3,2>, <2,1,3>, <2,3,1>, <3,1,2>, <3,2,1>

 

3개 요소들을 각각 a1, a2, a3라고 인덱스를 지정하도록하겠습니다.

 

다시한번 상기시키자면 지금 우린 삽입정렬을 하고 있습니다. 그런데 이제 요소 3개씩 조합들을 곁들인.

그래서 첫번째 조합을 보자면 <1,2,3>으로 되어있습니다.

삽입정렬 기억 나시죠? 첫 번째 인덱스 요소부터 정렬을 시작합니다.

그러면 a1인 1과 a2인 2가 서로 비교 대상이 됩니다.

이걸 먼저 루트 노드로 그려보자면

(a1, a2)가 되겠습니다. 이때 key 값은 a2가 됩니다.

그 다음은 a2와 a3 값이 서로 비교대상이 됩니다.

이 때는 key 값이 a3가 됩니다.

 

a1(1)이 a2(2)보다 작거나 같으면 a2(2)랑 a3(3)이랑 비교하면 되기 때문에

왼쪽 하위노드로 두었습니다.

이제 a2(2)가 a3(3)보다 작거나 같은지 체크해보면됩니다. 

이경우 더이상 비교할 필요가 없으니 유일한 <1,2,3> 경우가 될겁니다.

 

<1,2,3>, <1,3,2>, <2,1,3>, <2,3,1>, <3,1,2>, <3,2,1>

 

이번에는 맨 뒤의 숫자 <3,2,1> 조합을 생각해봅시다.

이 경우 a1(3)이 a2(2)보다 크기 때문에 오른쪽 하위 노드에 들어갑니다.

이 때 key 값은 a2가 입니다.

 

그리고 이제 a1(3)이 a3(1)보다도 크기 때문에 성립하네요

 

 

이제 a1이 a2와 a3보다 크다는걸 알았으니 a2가 a3보다 작은지만 비교하면 되겠네요.

역시나 이번에도 <3,2,1>은 성립하는걸 보았으니 오른쪽 루트의 리프노드는 <3,2,1>이 되겠네요.

 

이 때 a1와 a2비교한 후 스왑을 해줍니다. 이 때 배열은 <2,3,1> 이고 key값은 a3입니다.

 

이런식으로 나머지 배열들도 다 정리를 해보면 아래 사진과 같습니다.

 

 

그리고 여기에 최선의 케이스 오메가와 최악의 케이스 빅 오를 그려보면

이렇게 되겠습니다.

우리가 지금까지 한건 세 개의 요소로 삽정렬의 결정 트리를 구성한겁니다.



결정 트리에는 두 가지 중요한 점이 있습니다


1. 결정 트리의 잎(leaves) 개수:
   - 결정 트리에는 최소한 n! (n 팩토리얼) 개의 잎이 있습니다.
   - 이유: 모든 가능한 순열(permutation)이 최소 한 번씩 나타나야 하기 때문입니다.
   - 예: 3개 요소의 경우, 3! = 6개의 순열이 있으므로 최소 6개의 잎이 있어야 합니다.

2. 루트에서 잎까지의 가장 긴 경로 길이:
   - 이는 사용하는 정렬 알고리즘에 따라 다릅니다.
   - 예시:
     a) 삽입 정렬(Insertion sort): Θ(n²)
        - 최악의 경우, n²에 비례하는 비교 횟수가 필요합니다.
     b) 병합 정렬(Merge sort): Θ(n lg n)
        - 항상 n log n에 비례하는 비교 횟수가 필요합니다.

이걸 통해 각 정렬 알고리즘의 시간 복잡도를 이해하는 데 도움이 됩니다. 

결정 트리의 구조가 알고리즘의 성능을 직접적으로 반영한다는 것을 보여줍니다.

 


 

결정 트리 증명


정렬 알고리즘의 결정 트리에 대한 중요한 정리와 그 증명을 보겠습니다.

1. 정리: n개 요소를 정렬하는 모든 결정 트리의 높이는 Ω(n lg n)입니다.

2. 증명 과정:
   - 트리의 높이 h는 최소한 lg(n!)보다 크거나 같아야 합니다.


 - 스털링 근사(Stirling's approximation)를 사용하여 n!을 근사합니다



 

   - 로그를 취하고 계산을 진행하면 h ≥ n lg(n/e)가 됩니다.
   - 이를 전개하면 h ≥ n lg n - n lg e가 됩니다.

   - 결과적으로 h = Ω(n lg n)임을 보입니다.

 



h ≥ n lg n - n lg e 에서 Ω(n lg n)이 되는 과정은 다음과 같습니다:

1. n lg e는 상수항입니다:
   - lg e는 고정된 값(약 1.44)이므로, n lg e는 n에 비례하는 선형 항입니다.

2. 점근적 표기법에서는 상수항과 낮은 차수의 항을 무시합니다:
   - n lg n은 n lg e보다 더 빠르게 증가합니다.
   - 따라서 n이 충분히 큰 경우, n lg n이 n lg e를 지배합니다.

3. 결과적으로:
   h ≥ n lg n - n lg e
   ≥ n lg n - O(n)
   = Ω(n lg n)

즉, h의 하한(lower bound)은 n lg n에서 선형 항을 뺀 것이지만, 점근적으로는 이 선형 항이 무시되어 결국 Ω(n lg n)이 됩니다.

이는 "h는 최소한 n lg n의 order로 증가한다"는 의미로, 모든 비교 기반 정렬 알고리즘의 시간 복잡도 하한을 나타냅니다.

 

결론은 어떤 비교 기반 정렬 알고리즘도 Ω(n lg n)보다 빠를 수 없다는 것을 수학적으로 보여줍니다.

 

 

'그냥 개발글 > 알고리즘' 카테고리의 다른 글

Radix Sort 기수 정렬  (0) 2024.10.20
Counting Sort 계수 정렬  (0) 2024.10.20
퀵 정렬 Quick Sort  (1) 2024.10.19
우선순위 큐 Priority Queues  (0) 2024.10.19
COMMENT