일단 모바일 코참 패스로 필기시험을 접수하고 공부를 시작하기로 했다. (비용 : 18,200원)

저번 겨울방학 때, YBM 인강을 끊어놓은게 있었는데 올해까진데다 마침 자격증 인강도 있길래 돈도 아낄겸 이걸 통해 공부했다.

근데 이렇게 써놓으면 뭔가 열심히 공부한거 같지만 사실 어영부영 대충 동영상 듣다가, 전날 되어서야 뭔가 큰일난거 같아서 호다닥 이론 공부를 마무리했다.

그리고 문제은행식이니 이제 문제풀이를 해야해서, 저기서 준 강의자료의 족보도 풀어보고 강사님이 알려주신 사이트에서 여러 번 풀어보았다.

여기 다른 자격증 족보도 많던데 나중에 다른거 딸 때 쓰면 좋을 것 같았다.

그리고 기출 3개년 풀고, 혹시 몰라 1년치 정도만 더 풀고 시험을 치러갔다. 처음 대기실에 갔을 때, 정말 조용하고 다들 정리노트 열심히 보고 있어서 쫄았다. 다들 좋은 결과가 있었으면 좋겠다.

시험장 들어가니 진짜 OMR 카드 같은것도 아니고 only 컴퓨터로만 시험을 쳤다. 그리고 혹시 몰라 수험증 출력해서 갔는데 그냥 신분증만 들고 가면 됐다.

합격 기준 : (각 과목당 40점 이상) and (전체 평균 점수 60점 이상)

결과는 다행히 합격했다. 문제 풀면서 1,3번만 연속으로 10개는 나온 것 같아서 뭔가 망했나 싶었는데 다행히 잘 찍었나보다. 다들 2과목이 어렵다는데 진짜 어렵더라...

사족이지만 필기가 바로 다음 날 결과가 나와서 좋다. 실기는 결과 나오기까지 2주 걸리는거 같은데.

마지막으로 시험장이 깨끗하고 좋아서 실기도 거기서 보고 싶었는데 찾아보니 거기 시험장이 지원을 안하는건지 아니면 이미 지원이 마감 됐는지 그 지역은 실기가 없더라...

이제 실기만 치면 되는데 어서 빨리 기말 끝나는 날짜에 신청을 해야겠다.

1. JSON 파일 역직렬화 (Deserialization)

앞선 글에서 우리는 게임 데이터 객체를 JSON 형식으로 변환해봤다. 근데 이제 저장한 JSON 파일을 어떻게 불러오고, 그 파일의 내용을 어떻게 처리해야할까?

객체를 JSON 파일로 변환시켰던 것처럼, JSON 파일을 활용하기 위해선 이 데이터를 다시 객체로 변환시켜야한다. 이를 역직렬화(Deserialization)라 한다.

다행히 우리가 썼던 JsonUtility에서 JsonUtility.ToJson메서드를 통해 간단히 객체를 직렬화 했던 것처럼 라이브러리 내부에서 JsonUtility.FromJson 메서드를 사용해서 역직렬화 기능을 사용할 수 있다.

그럼 이제 JSON 파일을 역직렬화하는 코드를 살펴보자.

2. 저장된 파일 읽기

string path = Path.Combine(Application.persistentDataPath, "playerData.json");
if (File.Exists(path))
{
    string jsonData = File.ReadAllText(path);
}

당연히 데이터를 불러오러면 파일을 먼저 읽어야 한다. 위 코드를 분석해보면

• Path.Combine을 통해서 path 변수에 경로값을 할당해준다.
• File.Exists를 통해서 path 경로에 파일이 존재하는지 확인한다.
• 만약 존재한다면 File.ReadAllText로 파일 내의 모든 텍스트을 가져와서 jsonData 변수에 할당한다.

자, 이러면 jsonData변수에 파일 내에 있던 모든 값이 저장이 됐다. 그럼 이제 이 텍스트를 어떻게 처리해야 데이터 객체로 변환시킬 수 있을까?

3. 데이터 객체로 변환하기

PlayerData playerData = JsonUtility.FromJson<PlayerData>(jsonData);

이건 JSON 객체로 변환할 때 JsonUtility.ToJson을 사용한 것과 유사하게, JsonUtility.FromJson 메서드를 사용하면 된다.

• JsonUtility.FromJson를 통해서 jsonData에 저장된 텍스트 데이터를 PlayerData 타입의 객체로 변환한 후, playerData 변수에 값을 저장해준다.

이러면 데이터를 불러오는 기본 로직이 끝났다!

이제 위의 로직을 합쳐서 한 코드로 만들면 아래처럼 쓸 수 있다.

using System.IO;
using UnityEngine;

[System.Serializable]
public class PlayerData // 저장할 데이터가 명시된 클래스
{
    public string name;
    public int level;
    public string[] items;
}

// 데이터 로드와 관련된 메서드가 정의된 매니저 클래스
public class LoadManager : MonoBehaviour
{
    // JSON 파일에서 PlayerData를 불러와, 반환해주는 메서드
    public PlayerData LoadData()
    {
        string path = Path.Combine(Application.persistentDataPath, "playerData.json");
        if (File.Exists(path))
        {
            string jsonData = File.ReadAllText(path);
            PlayerData data = JsonUtility.FromJson<PlayerData>(jsonData);
            Debug.Log("데이터 로딩 성공! // 플레이어 이름 : " + data.name);
            return data;
        }
        else
        {
            Debug.LogWarning("세이브 파일을 찾을 수 없음!");
            return null;
        }
    }
}

이제 아래의 예제를 통해서playerData.json 파일을 저장 후, 불러와보자.

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

public class TestJson : MonoBehaviour
{
    void Start()
    {
        PlayerData player = new PlayerData // 데이터 객체 생성
        {
            name = "Player1",
            level = 5,
            items = new string[] { "sword", "shield" }
        };

        SaveManager saveManager = new SaveManager(); // SaveManager 객체 생성
        saveManager.SaveData(player); // 데이터 저장

        LoadManager loadManager = new LoadManager(); // LoadManager 객체 생성
        PlayerData playerData = loadManager.LoadData(); // 데이터 불러오기
        printData(playerData); // 불러온 데이터 출력
    }

    void printData(PlayerData playerData)
    {
        Debug.Log("name : " + playerData.name);
        Debug.Log("level : " + playerData.level);
        foreach(string item in playerData.items)
            Debug.Log("item : " + item);
    }
}

• 예제 코드

• 데이터가 성공적으로 불러와진 모습

• 불러온 데이터 객체에 저장되어 있는 값

이걸로 게임 저장 파일을 JSON 형식으로 저장하는 것에 이어서 불러오는 기능까지 구현해봤다.

위의 예시 코드를 좀 더 다듬은 코드를 첨부하고 글을 마치겠다.

• try-catch 문을 사용해 예상치 못한 오류 예외처리
• if문 구문 약간 수정 (로직은 동일함)

using System.IO;
using UnityEngine;

public class LoadManager : MonoBehaviour
{
    public PlayerData LoadData()
    {
        string path = Path.Combine(Application.persistentDataPath, "playerData.json");
        if (!File.Exists(path))
        {
            Debug.LogWarning("세이브 파일을 찾을 수 없습니다. 디폴트 파일을 불러옵니다.");
            return new PlayerData { name = "DefaultPlayer", level = 1, items = new string[] { } };
        }

        try
        {
            string jsonData = File.ReadAllText(path);
            PlayerData playerData = JsonUtility.FromJson<PlayerData>(jsonData);

            Debug.Log("데이터 로드 성공!");
            return playerData;
        }
        catch (System.Exception e)
        {
            Debug.LogError("JSON 파일을 불러오는데 오류 발생: " + e.Message);
            return new PlayerData { name = "DefaultPlayer", level = 1, items = new string[] { } };
        }

    }
}

1. JSON으로 저장할 데이터는?

일단 저장기능을 구현하기 전에, 우리는 무슨 데이터를 JSON으로 저장해야할까? 데이터야 여러가지가 있지만 보통 다음과 같은 예시가 있을 것이다.

플레이어의 정보, 게임 설정, 현재까지의 진행 상황...

이제 우린 이런 데이터들을 JSON 형식으로 저장해야한다. 앞선 글에서 나왔던 것처럼, JSON 파일은 키와 값 쌍의 형태로 이뤄져 있다는걸 기억하자. 위의 예시에서 언급된 데이터를 JSON으로 나타낸다면 다음과 같이 나타낼 수 있다.

{
  "player": {
    "name": "Player1",
    "level": 5,
    "items": ["sword", "shield"],
    "currentStage": {
      "id": 3,
      "name": "Forest of Shadows",
      "progress": 45
    },
    "clearedStages": [
      {
        "id": 1,
        "name": "Plains of Beginning",
        "time": "00:12:34"
      },
      {
        "id": 2,
        "name": "Cave of Echoes",
        "time": "00:24:56"
      }
    ]
  },
  "settings": {
    "volume": 70,
    "difficulty": "normal"
  }
}

이외에도 다양한 데이터들이 포함될 수도 있다.

2. JSON으로 데이터 저장하기

자, 어떻게 데이터를 JSON 형식으로 저장할지도 고민해봤으니 이제 JSON으로 데이터를 저장해보자.

먼저 우리는 파일을 저장할 위치를 정해야한다. 파일을 아무런 위치에다 저장해놓으면 나중에 찾기도 힘들고 관리하기도 버겁다.

이럴 때를 위해 유니티에서 제공하는 경로인 Application.persistentDataPath 가 있다.

이 프로퍼티는 각 플랫폼 별로 적절한 디렉터리를 제공하기에 번거롭게 경로를 일일히 정해줄 필요가 없다.

• Windows: C:\Users\<사용자이름>\AppData\LocalLow\<회사이름>\<프로젝트이름>
• macOS: ~/Library/Application Support/<회사이름>/<프로젝트이름>
• Android: /data/data/<패키지이름>/files
• iOS: <앱 샌드박스 디렉토리>/Documents

만약 실제 경로가 맞는지 확인하려면 아래의 코드를 실행시켜보면 된다.

Debug.Log("Save Path: " + Application.persistentDataPath);

그리고 사용자가 앱을 삭제하지 않는 한 데이터는 영구적으로 유지되기에 사용자의 데이터를 저장하기에 적합하다.

다만 파일 변조가 가능하기에, 중요하거나 개인적인 정보를 암호화하지 않은 상태로 Application.persistentDataPath 에 저장하는 것은 추천되지 않는다.

🤔 dataPath? // streamingAssetsPath?

Application 클래스의 프로퍼티를 살펴보면, 경로에 대한 여러 프로퍼티를 찾을 수 있다.

이중에서 몇 가지만 살펴보면

• Application.dataPath
  • 에디터 상에선 유니티 프로젝트의 Assets 폴더 경로를, 빌드된 앱에선 앱의 Data 폴더 경로를 반환.
  • 읽기 전용
  • 이 프로퍼티를 통해 게임 데이터를 저장하면 안됨.

Asset 폴더 안의 내용은 빌드 시, 특정 형식으로 패키징 되기에 경로 기반 접근이 불가능하다. 다만 Resources 폴더에 접근할 때는 아래 예시처럼 경로 기반이 아닌 Resources.Load 를 사용해 접근할 수 있다. 그리고 밑에서 얘기할 StreamingAssets 폴더의 경우에만 예외적으로 경로 기반 접근이 가능하다.

// Resources/myFile.txt 파일을 읽기
TextAsset textAsset = Resources.Load<TextAsset>("myFile"); // 확장자 제외

• Application.streamingAssetsPath
  • StreamingAssets 폴더의 경로 반환
  • StreamingAssets 폴더는 해당 내용 그대로 패키징 되기에 빌드 후에도 경로 기반 접근이 가능
  • 읽기 전용

이 외에도 임시적인 캐시 파일을 저장하는 경로인, Application.temporaryCachePath

콘솔 로그에 대한 경로를 반환하는, Application.consoleLogPath 가 있다.

3. JSON 직렬화(Serialization)

자 이제 게임 데이터를 JSON으로 변환해보자. UNITY는 이런 직렬화 과정을 위해 JsonUtility를 기본적으로 제공하며, 이 외의 다양한 기능이 필요할 경우 Newtonsoft의 JSON 라이브러리를 사용할 수도 있다.

우리는 유니티에서 기본적으로 제공하는 JsonUtility를 통해서 직렬화를 해보자.

먼저 게임 데이터를 저장해주는 클래스를 만들자.

[System.Serializable] // 직렬화를 하겠다는 어트리뷰트(Attribute)
public class PlayerData
{
    public string name;
    public int level;
    public string[] items;
}

이제 SaveManager 스크립트를 만들어주고 다음과 같이 적어주자.

using System.IO;
using UnityEngine;

public class SaveManager : MonoBehaviour
{
    public void SaveData(PlayerData data)
    {
        // 경로 설정
        string path = Path.Combine(Application.persistentDataPath, "playerData.json");

        // JSON으로 직렬화
        string jsonData = JsonUtility.ToJson(data, true); // true는 읽기 쉽게 포맷팅
        Debug.Log("JSON Data : \n" + jsonData);

        // 파일로 저장
        File.WriteAllText(path, jsonData);

        Debug.Log("Data saved to " + path);
    }
}

• Path.Combine : 두 개 이상의 문자열을 매개변수로 받고 올바른 디렉터리 경로를 반환.
• JsonUtility.ToJson : 매개변수로 직렬화할 객체를 받고, 만약 두 번째 매개변수에 true 넣는다면 읽기 쉽게 변환.
• File.WriteAllText : 해당 경로에 텍스트 파일을 저장.

이제 아래의 예제를 실행시켜보고 방금 얘기한 디렉터리를 살펴보면 파일이 생성된걸 확인할 수 있다.

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

public class TestJson : MonoBehaviour
{
    void Start()
    {
        PlayerData player = new PlayerData // 데이터 객체 생성
        {
            name = "Player1",
            level = 5,
            items = new string[] { "sword", "shield" }
        };

        SaveManager saveManager = new SaveManager(); // SaveManager 객체 생성
        saveManager.SaveData(player); // 세이브 시작
    }
}

JSON 파일로 직렬화 된 모습

파일이 저장된 위치

저장된 파일과 내용

4. 오류 케이스 처리하기

이걸로 저장 기능을 구현했다! 하지만 이 코드는 파일 저장 과정에서 생길 수 있는 오류를 처리하지 못한다. 마지막으로 예외 처리 로직까지 짜보자.

1. 파일 경로 체크
   • 만약 저장할 경로가 존재하지 않을 때 문제가 발생할 수 있다.
   • 다음의 코드를 통해, 파일의 경로가 존재하는지 체크하고 만약 존재하지 않는다면 디렉터리를 생성하게 할 수 있다.

     if (!Directory.Exists(Application.persistentDataPath))
     {
     Directory.CreateDirectory(Application.persistentDataPath);
     }

• Directory.CreateDirectory : 매개변수로 넣은 경로를 생성

2. 예외 처리
   • try-catch 문으로 저장 과정 중에 예상치 못하게 생기는 오류를 확인할 수 있다.

try
{
    File.WriteAllText(path, jsonData);
    Debug.Log("Data saved successfully.");
}
catch (Exception e)
{
    Debug.LogError("Failed to save data: " + e.Message);
}

이 예외 처리를 포함한 전체적인 저장 코드는 다음과 같다.

public class SaveManager : MonoBehaviour
{
    public void SaveData(PlayerData data)
    {
        // 저장 경로 설정
        string path = Path.Combine(Application.persistentDataPath, "playerData.json");

        try
        {
            // JSON 직렬화
            string jsonData = JsonUtility.ToJson(data, true);
            Debug.Log("JSON Data : \n" + jsonData);

            // 경로 확인 및 생성
            if (!Directory.Exists(Application.persistentDataPath))
            {
                Directory.CreateDirectory(Application.persistentDataPath);
            }

            // JSON 데이터 저장
            File.WriteAllText(path, jsonData);
            Debug.Log("Data saved to " + path);
        }
        catch (Exception e)
        {
            Debug.LogError("Failed to save data: " + e.Message);
        }
    }
}

이렇게 해서 저장 기능을 구현해봤다. 다음 글에선 이 저장한 파일을 어떻게 불러와야 하는지 알아보자.

JSON이란?

저장 기능을 구현하기 전에 먼저 JSON에 대해 알아보자. JSON으로 저장한다는데 JSON이 뭔지 모르면 뭔가 이상하지 않은가.

JSON은 JavaScript Object Notation의 약자로 데이터 저장과 교환을 수월하게 하기 위해 만들어진 양식이다. 기존에 쓰이던 XML에 비해 구조가 단순하고 가벼워 자주 사용된다.

1. JSON의 구조

JSON은 객체(Object)로 이루어져 있을 수도 있고, 배열(Array)로 이루어져 있을 수도 있다. 설명하기에 앞서 간단히 비교해보면,

객체

• 중괄호 {} 로 감싸며, 키(key) - 값(value) 쌍으로 데이터를 저장한다.
• 다양한 속성의 데이터를 저장할 때 유용하다. ex) 플레이어 레벨, 진행 상황, 설정 정보 등

기본적인 구조

{ key : value }

예시

{
  "도시": "서울",
  "인구": 10000000,
  "지역": ["은평구", "영등포구", "마포구"]
}

배열

• 대괄호 []로 감싸며, 값(value)들의 목록을 저장한다.
• 순서가 존재하거나 비슷한 종류의 데이터를 저장할 때 유용하다. ex) 아이템 리스트, 배열에 기반한 데이터 등

기본적인 구조

[value1, value2, value3]

예시

[
  {"상품": "노트북", "가격": 1500000},
  {"상품": "스마트폰", "가격": 800000},
  {"상품": "태블릿", "가격": 600000}
]

다음 예시로 좀 더 자세히 알아보자.

{
  "이름": "홍길동",
  "나이": 30,
  "주소": {
    "도시": "서울",
    "구": "강남구"
  },
  "취미": ["독서", "등산", "음악 감상"]
}

• 위의 예시는 JSON 객체로 이름, 나이, 주소, 취미의 키(key)와 이에 해당하는 값들이 포함되어 있다. 각 데이터는 쉼표,로 구분된다.
• 여기서 주소는 값으로 또 다른 객체를 가지며, 그 객체는 도시, 구의 키와 이에 해당하는 값이 저장되어 있다.
• 그리고 취미의 값으로는 배열이 할당되어 있다.

주소 키에 할당된 값(객체)

{
    "도시": "서울",
    "구": "강남구"
}

취미 키에 할당된 값(배열)

["독서", "등산", "음악 감상"]

갑자기 뭔가 복잡해 보이는 코드의 구조를 뜯어보니 뭔가 헷갈릴 수도 있다. 그래서 JSON에서 사용 가능한 데이터 타입에 대해 알아보면서 복습해보자.

2. JSON에서 사용 가능한 데이터 타입

JSON 내에서 표현할 수 있는 데이터 타입은 다음 6개가 있다.

• 문자열 (String): "텍스트"
• 숫자 (Number): 정수ex) -1, 0, 1, 등...나 실수ex) 3.141592, 등...
• 객체 (Object): { "키": "값" }
• 배열 (Array): [값1, 값2, ...]
• 불리언 (Boolean): true 또는 false
• 널 (Null): null

이를 보고 다음 예시와 함께 다시 자세히 이해해보자.

{
  "name": "홍길동",                
  "age": 28,                      
  "height": 175.5,                
  "isMember": true,               
  "address": {                    
    "city": "서울",
    "district": "강남구",
    "zipcode": null               
  },
  "hobbies": ["독서", "등산", "영화 감상"]
}

1. 문자열 (String)
   • 예시 필드: "name": "홍길동", "city": "서울", "district": "강남구"
   • 텍스트 데이터를 저장하는 데 사용된다. 문자열은 항상 큰따옴표(" ")로 감싸서 써야한다.
2. 숫자 (Number)
   • 예시 필드: "age": 28, "height": 175.5
   • 정수와 실수, 모두를 지칭한다. JSON에서는 별도의 정수 타입과 실수 타입으로 구분하지 않는다.
3. 객체 (Object)
   • 예시 필드: "address": { ... }
   • 중괄호{}로 감싸여 있으며, 키-값 쌍으로 구성된다. 복잡한 데이터를 구조화하는 데 사용된다.
4. 배열 (Array)
   • 예시 필드: "hobbies": ["독서", "등산", "영화 감상"]
   • 대괄호[]로 감싸여 있으며, 값들의 순서가 있는 목록으로 구성된다. 동일한 타입의 데이터나 다양한 타입의 데이터를 포함할 수 있다.
5. 불리언 (Boolean)
   • 예시 필드: "isMember": true
   • 참(true) 또는 거짓(false) 값을 가진다.
6. 널 (Null)
   • 예시 필드: "zipcode": null
   • 값이 없음을 나타낸다. 데이터가 없거나 값이 아직 할당되지 않은 경우에 사용한다.

데이터 타입을 활용하면 아래와 같이 복잡한 구조도 표현 가능하다.

{
  "player": {
    "name": "김철수",
    "stats": {
      "level": 15,
      "experience": 2450.75,
      "isPremium": false
    },
    "inventory": [
      {
        "item": "검",
        "quantity": 1,
        "durability": 80.5
      },
      {
        "item": "방패",
        "quantity": 1,
        "durability": 60.0
      },
      {
        "item": "포션",
        "quantity": 10,
        "durability": null
      }
    ],
    "achievements": null
  }
}

• player : 객체 타입, 플레이어에 대한 모든 정보를 포함.
• name : 문자열 타입, 플레이어의 이름.
• stats : 객체 타입, 플레이어의 레벨, 경험치, 프리미엄 회원 여부에 대한 정보를 포함.
  • level: 숫자 타입, 플레이어의 레벨.
  • experience: 숫자 타입, 플레이어의 경험치.
• isPremium: 불리언 타입, 프리미엄 회원 여부.
• inventory: 배열 타입, 플레이어의 인벤토리 아이템 목록.
  • 각 아이템은 객체 타입으로, item(문자열), quantity(숫자), durability(숫자 또는 널) 필드를 가짐.
• achievements: 널 타입, 현재 플레이어가 달성한 업적이 없음을 의미.

3. JSON을 쓰면서 주의해야 할 것

• 키와 문자열 값은 작은따옴표''가 아닌 큰따옴표""로 감싸야 한다.

  (X)    { 'name': '홍길동' }
  (O)       { "name": "홍길동" }

• 각 요소의 구분은 쉼표,로 구분하며, 마지막 요소 뒤엔 쉼표를 사용하지 않는다.

  (X)
  {
  "name": "홍길동",
  "age": 30,
  }
  

(O) { "name": "홍길동", "age": 30 }

- **JSON 표준은 주석을 지원하지 않는다.**

(X) { "name": "홍길동" // 사용자 이름 } 또는 { "name": "홍길동" # 사용자 이름 }

(O) { "name": "홍길동" }

```

이렇게 해서 JSON에 대해 알아보았다. 쓰다보니 분량이 길어져서 유니티에서 JSON을 활용해 저장 기능을 만들어 보는 것은 다음 글에서 알아보자.

동적 계획법(Dynamic Programming)은

• 문제의 최적해가 하위 문제(sub-problem)의 최적해로 정의되며,
• 하위 문제가 중첩(overlapping)될 때

사용할 수 있는 알고리즘 기법이다.

예시로, 피보나치 수열을 재귀와 DP로 구하는 방식을 비교해보자.

1. 재귀

 import time

 #재귀 함수
 def Fibonacci(n):
     if n == 1 or n == 2:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

 n = 40

 startTime = time.time()
 result = Fibonacci(n)
 endTime = time.time()
 timeRecursive = endTime - startTime

 print(f"Fibonacci({n}) 계산 결과")
 print(f"값 : {result} / 실행 시간 {timeRecursive}초")

• 실행결과

  Fibonacci(40) 계산 결과
  값 : 102334155 / 실행 시간 29.934786319732666초

• 시간 복잡도 : O(2^n)

이 재귀함수가 실행되는 과정을 살펴보면, 동일한 과정을 반복한다는 것을 알 수 있다. 이로 인해 실행과정이 오래 걸리게 된다.

그런데 이 과정을 잘 살펴보니

• 같은 하위 문제(sub-problem)가 중첩되고 ex) Fibo(n-k)가 반복됨
• 최종적인 해가 하위 문제의 해로 정의된다는 것을 알 수 있다. ex) Fibo(n) = Fibo(n-1) + Fibo(n-2)

즉 이 문제는 DP로 해결할 수 있다. 이제 피보나치 수열을 DP로 해결해보자.

2. 동적 계획법

import time

# 동적 계획법
def Fibonacci_DP(n):
    if n == 1 or n == 2:
        return 1

    fibo = [0 for _ in range(n+1)]

    fibo[1], fibo[2] = 1, 1

    for i in range(3, n+1):
        fibo[i] = fibo[i-1] + fibo[i-2]

    return fibo[n]


n = 10000

startTime = time.time()
result = Fibonacci_DP(n)
endTime = time.time()
timeDP = endTime - startTime

print(f"Fibonacci({n}) 계산 결과")
print(f"값 : {result} / 실행 시간 {timeDP}초")

• 실행결과

  Fibonacci(10000) 계산 결과
  값 : 33644764876...(생략) / 실행 시간 0.00937342643737793초

• 시간 복잡도 : O(n)

재귀와 DP의 실행 시간을 비교해보면, DP방식이 재귀방식보다 매우 빠른 것을 알 수 있다.

탑다운(Top-Down)과 바텀업(Bottom-Up)

방금 전 문제의 경우, 바텀업(Bottom-Up) 접근 방식을 통해 문제를 풀었다. DP는 주로 탑다운(Top-Down)과 바텀업(Bottom-Up) 접근방식을 통해서 문제를 해결한다.

1. 탑다운

탑다운은 위에서부터 아래로, 즉 큰 문제에서 시작해서 필요한 하위문제의 해를 구해가는 방식이다.

탑다운 방식의 경우, 재귀와 메모제이션(Memoization)을 활용한다.

메모제이션(Memoization) : 문제를 해결하는 과정에서 이미 계산한 결과를 저장해서 중복 계산을 방지하는 기법 중 하나

• 탑다운적 접근 방식
• 재귀 함수를 통해 구현된다.
• 문제를 해결하며 필요한 부분 문제만 계산되어 저장된다.

앞서 풀어본 피보나치 수열을 탑다운 방식으로 구현하면 다음과 같이 구현할 수 있다.

# 동적 계획법 (탑다운)
def Fibonacci_DP(n, memo = {}):
    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = Fibonacci_DP(n-1, memo) + Fibonacci_DP(n-2, memo)

    return memo[n]

print(Fibonacci_DP(20)) # 출력 6765

Fibonacci_DP 함수를 통해서 위에서부터 재귀적으로 수열을 계산하면서, 계산된 결과는 memo 딕셔너리에 저장하며 중복 계산을 피하고 있다.

2. 바텀업

바텀업은 아래에서부터 위로, 즉 작은 하위문제에서 시작해 더 큰 문제의 해를 구성하는 방식이다.

바텀업 방식의 경우, 반복문과 타뷸레이션(Tabulation)을 활용한다.

타뷸레이션(Tabulation) : 문제를 해결하는 과정에서 이미 계산한 결과를 저장해서 중복 계산을 방지하는 기법 중 하나

• 바텀업적 접근 방식
• 반복문을 통해 구현된다.
• 모든 부분 문제를 계산해서 작은 것부터 순차적으로 저장한다.

앞서 구현한 코드를 다시 살펴보자.

# 동적 계획법 (바텀업)
def Fibonacci_DP(n):
    if n == 1 or n == 2:
        return 1

    fibo = [0 for _ in range(n+1)]

    fibo[1], fibo[2] = 1, 1

    for i in range(3, n+1):
        fibo[i] = fibo[i-1] + fibo[i-2]

    return fibo[n]

print(Fibonacci_DP(20)) # 출력 6765

Fibonacci_DP 함수 내에서 fibo리스트의 인덱스가 1과 2일 때 값을 1로 초기화한다. (기저 조건(Base Case)) 그리고 반복문을 통해 3에서 n까지 순차적으로 수열을 계산하고 fibo리스트에 저장한다.

정리

테이블(table) : 데이터를 구조화하여 저장하고, 효율적으로 검색하거나 참조할 수 있도록 만든 데이터 구조로, 여기선 문제를 해결하기 위해 부분 문제의 해답을 저장하는 배열 또는 리스트를 의미한다.

캐시(cache) : 데이터나 계산 결과를 임시로 저장해 두었다가 필요할 때 빠르게 꺼내 쓰는 저장소를 의미한다.

분할 정복(Divide and Conquer)과 동적 계획법(Dynamic Programming)

문제를 하위문제로 쪼개고, 그 하위문제의 부분해를 통해서 전체 문제의 해를 구한다는 측면에서 분할 정복(Divide and Conquer)과 동적 계획법(Dynamic Programming)은 동일하게 보이기도 한다.

하지만 접근 방식과 적용되는 문제의 특성에서 둘은 몇 가지 중요한 차이점이 있다.

divede 오타났다.

• 분할 정복(Divide and Conquer)

  • 하위 문제가 서로 독립적이며, 중복되지 않음
  • 문제를 여러 하위 문제로 분할한 후, 부분해를 결합해서 전체해를 구한다.

    예시 : 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search)

• 동적 계획법(Dynamic Programming)

  • 하위 문제가 중첩되며 여러 번 계산됨
  • 하위 문제의 부분해를 저장해놨다가 재사용하며 전체해를 구한다.

    예시 : 피보나치 수열, LCS(최장 공통 부분 수열), 막대 자르기 문제

여담

동적 계획법의 이름을 보면 동적(dynamic)이라는 말이 붙어있는데, 앞서 살펴본 것처럼, 사실 이 기법은 동적과는 거리가 멀다. 그런데도 이름이 이런 이유는, 동적 계획법의 고안자가 dynamic이란 이름이 멋져보여서 붙였기에 이런 이름으로 정해지게 되었다.

보통 None이 아무것도 없음을 나타내는 것처럼, None은 함수가 값을 반환하지 않을 때, 또는 변수에 초기값을 지정하지 않을 때 사용됩니다.

특징

1. None은 싱글톤 객체입니다.

즉, 프로그램 내에서 하나의 None객체만 존재합니다. 이는 다음과 같은 코드로 확인해 볼 수 있습니다.

• 코드

  a = None
  b = None
  print(f"a is b : {a is b}")
  print()
  #다른 큰 수여도 상관 없음
  c = 200000000000000000000000 * 9999999999999999999999999999999999999999999999999
  d = 200000000000000000000000 * 9999999999999999999999999999999999999999999999999
  print(f"c is d : {c is d}")
  print(f"c == d : {c == d}")
  print()
  e = [1]
  f = [1]
  print(f"e is f : {e is f}")
  print(f"e == f : {e == f}")

• 결과

  a is b : True
  

c is d : False c == d : True

e is f : False e == f : True

앞서 얘기한거처럼 `Python`은 `None`을 하나의 **싱글톤 객체**로만 생성합니다.

같은 객체를 참조할 때 `True`를 반환하는 `is`연산자를 통해서 모**든 `None` 참조가 하나의 객체**를 가리킨다는 것을 알 수 있습니다.


### 🤔 왜 두 번째 케이스에 큰 수를 쓰나요?
- 파이썬은 `자주 사용되거나 크기가 작은 객체`, `불변 객체(immutable objects)`(`None`, `True`, `False` 등)를 **미리 저장해놨다가 필요할 때 재사용하는 캐싱 기법**을 사용하고 있습니다. 

- 예를 들어, 값이 작은 정수 같은 값은 프로그램에서 여러 번 사용될 가능성이 높습니다. 그래서 이 값이 다시 사용될 때마다 메모리를 새로 할당하는 것이 아닌 기존에 저장한 값을 재사용하는 것입니다.

- 하지만 `너무 큰 값`이거나, `가변 객체(mutable objects)`(`리스트`, `딕셔너리`, `집합` 등) 경우에는 **캐싱**해놓지 않습니다. 따라서 만약 두 번째 경우에서 값을 작은 값으로 하면 결과가 **`True`**로 바뀌게 됩니다.

- 코드
```python
c = 1000
d = 1000
print(f"c is d : {c is d}")
print(f"c == d : {c == d}\n")

• 결과

  c is d : True
  c == d : True

2. None은 NoneType이라는 고유한 타입을 가지고 있습니다.

• 코드

  print(type(None))

• 결과

  <class 'NoneType'>

3. None은 불리언 판별을 할 때, False로 평가됩니다.

• 코드

  if not None:
    print("None은 False 입니다.")

• 결과

  None은 False 입니다.

None의 사용 예제

1. 반환값이 없는 함수의 반환값

   def my_function():
    pass
   

result = my_function() print(result) # 출력: None

2. 매개변수의 기본값 설정
```python
def greet(name=None):
    if name is None:
        print("Hello, Stranger!")
    else:
        print(f"Hello, {name}!")

greet()          # 출력: Hello, Stranger!
greet("Alice")   # 출력: Hello, Alice!

3. 변수 초기화

   data = None
   if data is None: # 만약 data에 값이 없다면 값을 초기화
    print("데이터가 없습니다.")
    data = "Initial_Value"

None과 is

None을 비교 목적으로 사용할 때는 == 또는 != 대신 is 또는 is not을 사용하는 것이 권장됩니다.

if var is None:
    print("변수가 None입니다.")

이는 None이 싱글톤 객체이기 때문으로, 한 프로그램 내에서 하나의 객체만 존재하는 싱글톤 객체의 특성상 값을 비교하는 == 연산자 보단 객체의 동일성을 검사하는 is 연산자를 쓰는게 권장됩니다.

파이썬의 None과 다른 언어의 null

다른 프로그래밍 언어에도 None과 비슷한 null이라는 개념이 있습니다. 이 둘은 값이 없음을 의미하기도 하고, 실제로 둘은 비슷한 기능을 담당하고 있습니다. 다만 세부적으로 들어가면서 차이가 생깁니다.

주요 차이점

1. 타입 시스템 및 표현 방식:

   • 파이썬: None은 NoneType의 유일한 객체으로, 모든 상황에서 동일하게 사용됩니다.
   • 자바, C#: null은 참조형에만 사용되며, 값형에서는 nullable 타입을 통해 사용됩니다.
   • C++: nullptr은 C++11부터 도입된 명확한 포인터 리터럴이며, 이전에는 NULL이나 0을 사용했습니다.
   • C: NULL은 전통적으로 ((void*)0)으로 정의되며, 포인터와 관련된 상황에서 사용됩니다.

2. 비교 방법:

   • 파이썬: is 연산자를 사용하여 None과 비교합니다.

     if 변수 is None:
         print("변수는 아무 값도 가지고 있지 않습니다.")

   • 자바, C#, C++: == 연산자를 사용하여 null 또는 nullptr과 비교합니다.

     if (변수 == null) {
         System.out.println("변수는 null입니다.");
     }

     if (포인터 == nullptr) {
         std::cout << "포인터는 nullptr입니다." << std::endl;
     }

   • C: == 연산자를 사용하여 NULL과 비교합니다.

     if (포인터 == NULL) {
         printf("포인터는 NULL입니다.\n");
     }

3. 기본값 처리:

   • C++ 및 C: 포인터 초기화 시 NULL이나 nullptr을 명시적으로 할당하지 않으면, 포인터는 쓰레기 값을 가질 수 있습니다.

4. 객체 지향 특성:

   • 파이썬: None은 객체이므로, 모든 객체와 마찬가지로 메서드를 호출하거나 속성을 가질 수 없지만, 타입 체킹이 명확하게 가능합니다.
   • 자바, C#: null은 객체 참조가 없음을 나타내며, null 참조에 접근하면 NullPointerException(자바)이나 NullReferenceException(C#)이 발생합니다.
   • C++ 및 C: nullptr이나 NULL은 단순히 메모리 주소 0을 나타내며, 이를 역참조하면 정의되지 않은 동작이 발생할 수 있습니다.

입력 처리하기

파이썬에서는 보통 input() 함수를 이용해서 입력을 처리한다. 이 함수는 사용자가 입력한 값을 항상 문자열(str)로 반환한다.

예시

name = input("이름을 입력하세요: ")
print(f"안녕하세요, {name}님!")

매개변수로 받은 문자열을 화면 상에 출력한 후, 사용자가 입력한 값을 name 변수에 저장한다. 그 다음 print 함수를 통해 이름을 출력한다.

숫자로 입력받기

input 함수는 항상 문자열을 반환한다. 만약 숫자를 입력받아서 활용하고자 한다면 형 변환이 요구된다.

예시1 (정수 입력)

age = int(input("나이를 입력하세요: "))
print(f"제 나이는 {age}살 입니다.")

int() 함수를 통해 입력값을 정수로 변환시킬 수 있다.

예시2 (실수 입력)

height = float(input("키를 입력하세요 (cm): "))
print(f"당신의 키는 {height}cm입니다.")

비슷하게 float() 함수를 통해 입력값을 실수로 변환시킬 수 있다.

여러 개의 값 입력받기

만약 사용자가 여러 개의 값을 입력한다면 어떻게 해야할까? 그럴 땐 split() 함수를 활용하면 된다.

예시1 (여러 개의 문자열 입력받기)

nameList = input("참여하는 사람들을 입력하세요 (공백으로 구분): ").split()
print(f"참여하는 사람: {nameList}")

결과

참여하는 사람들을 입력하세요 (공백으로 구분): 신희 난형 시우
참여하는 사람: ['신희', '난형', '시우']

split() 함수는 입력된 문자열을 공백을 기준으로 나눠서 문자열 리스트를 반환한다.

그럼 여러 개의 데이터를 입력받은 다음 형 변환을 해야할 때는 어떻게 해야할까?

이럴 때를 위해 map() 함수가 있다.

map() 함수는 map(함수, 반복 가능한 객체) 이런 구조를 가지고 있으며, 각 요소마다 함수를 적용하고 그 값이 포함된 map객체를 반환한다.

map객체에 데이터가 저장되지만 사용자가 이 값을 직접 볼 수 없다. 따라서 출력할 땐list() 등을 써서 출력해줘야 한다.

예시2 (여러 개의 정수 입력받기)

numList = map(int ,input("값들을 입력하세요 (공백으로 구분): ").split())
print(f"입력한 값: {list(numList)}")  # 데이터를 읽기 위해선 list()로 감싸줘야 함.

결과

값들을 입력하세요 (공백으로 구분): 1 5 3
입력한 값: [1, 5, 3]

예시3 (두 개의 정수 입력 받기)

a, b = map(int, input("두 수를 입력하세요 (공백으로 구분): ").split())
print(f"두 수의 합: {a + b}")

결과

두 수를 입력하세요 (공백으로 구분): 3 5
두 수의 합: 8

보다 빠르게 입력받기

대부분의 상황에선 편리적인 input() 함수를 사용해도 큰 문제는 없으나, 코딩 테스트처럼 처리 시간이 중요한 상황에서 input() 함수는 문제가 생길 수도 있다. (예시 : 백준 BOJ 15552번)

이럴 때는 sys 모듈을 import한 후에 sys.stdin.readline() 함수를 사용하는 것으로 해결할 수 있다.

input()함수 내부적으로 sys.stdin.readline()을 호출하기에 둘은 기능적으로 유사하지만 input()은 sys.stdin.readline()와 다르게

1. 개행 문자(\n)를 자동으로 제거한다.
2. 프롬프트 문자열을 출력한다. (예시: input("값을 입력해주세요"))
3. 예외 처리 같은 부가적인 로직이 포함한다.

이로 인해 input()함수가 sys.stdin.readline()보다 느리다. 그렇기에 코딩 테스트 같이 많은 양의 데이터를 반복적으로 처리해야하는 케이스에선 input()보단 sys.stdin.readline()을 사용하는 것이 좋다.

sys.stdin.readline()

sys.stdin.readline()는 반환값에 개행 문자를 제거하지 않는다. 따라서 입력값을 활용할 땐 이를 고려해야 한다.

예시

import sys
name = sys.stdin.readline().strip()     # 개행 문자 제거
print(f"제 이름은 {name}입니다.")

결과

시우
제 이름은 시우입니다.

예시2

import sys    
phoneList = sys.stdin.readline().split()
print(phoneList)

결과

S99 IPHONE99 G5
['S99', 'IPHONE99', 'G5']         #split()을 통해 개행 문자도 같이 제거

2차원 배열 입력받기

이제 코딩 테스트에서 자주 볼 수 있는 2차원 배열 입력 데이터를 파이썬으로 어떻게 처리해야 할지 알아보자

입력값

3 5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2

예시1

import sys
rows, cols = map(int, sys.stdin.readline().split())
matrix = []
for r in range(rows):
    matrix.append(list(map(int, sys.stdin.readline().split())))
print(matrix)

결과

[[6, 8, 2, 6, 2], [3, 2, 3, 4, 6], [6, 7, 3, 3, 2]]

리스트 컴프리헨션을 사용하면 반복문을 대체할 수 있다.

예시2

import sys
n, m = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
print(matrix)

결과

[[6, 8, 2, 6, 2], [3, 2, 3, 4, 6], [6, 7, 3, 3, 2]]

만약 입력 케이스가 공백이나 쉼표,로 구분되어 있지 않다면 어떻게 받아야할까? 그럴 땐 split() 메서드 대신 strip() 메서드를 사용해주면 된다.

입력

4 5
00100
01110
11111
10011

예시

import sys
rows, cols = map(int, sys.stdin.readline().split())
matrix = []
for r in range(rows):
    matrix.append(list(map(int, sys.stdin.readline().strip())))
print(matrix)

결과

[[0, 0, 1, 0, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 0, 0, 1, 1]]

이 경우에도 동일하게 리스트 컴프리헨션을 사용 가능하다.

확률적 분석과 랜덤화 알고리즘의 차이에 대해 설명하기 인디케이터 랜덤 변수 테크닉 소개하기 랜덤화 알고리즘 분석의 다른 예시 소개하기 (추가 배열 없이 배열 섞기)

채용 문제 (The Hiring Problem)

지배인은 에이전시를 통해서 직원을 고용하고자 합니다. 에이전시는 매일 한 명의 후보자를 보냅니다. 지배인은 각 후보자를 인터뷰하고 그 자리에서 고용 여부를 결정해야 합니다. 만약 새로운 사람이 고용되면, 현재 고용된 사람은 해고됩니다. 인터뷰 비용은 후보자 당 c_i / 고용 비용은 후보자 당 c_h 입니다. 고용 비용 c_h는 인터뷰 비용 c_i보다 크다고 가정합니다.

이 문제의 목표는 항상 현재까지 면접 본 후보자 중 가장 뛰어난 사람을 고용하는 할 때 발생하는 비용을 계산하는 것 입니다.

발생 비용 분석

만약 n명의 후보자 중에서 m명을 고용한다 가정하면, 총 비용은 입니다. (c_i = 인터뷰 비용, c_h = 고용 비용)

최악의 케이스(WorstCase)에서 지배인은 n명을 모두 한번씩 고용하게 됩니다. (1명 인터뷰 하고 기존의 직원 해고 후 1명 고용) 이 때의 비용은 입니다.

확률적 분석

보통, 후보자들이 나타나는 순서는 제어할 수 없기에 우리는 후보자들이 무작위 순서로 등장한다고 가정합니다. 각 후보자마다 순위(rank)를 부여합니다. rank(i) 는 1부터 n까지 범위에 대한 고유한 정수입니다. 이 순위들로 이루어진 리스트 는 후보자들 에 대한 순열로 볼 수 있습니다. 이 순위 리스트는 n!개가 존재할 수 있으며, 모든 순열은 동일한 확률입니다, 즉 이 순열은 균일한 무작위 순열(uniform random permutation)입니다.

인디케이터 랜덤 변수

인디케이터 랜덤 변수는 특정 사건(A)이 발생했는지의 여부를 나타내는 변수입니다.

인티케이터 랜덤 변수는 다음과 같이 정의됩니다. 즉, 사건 A가 발생하면 1을, 발생하지 않으면 0을 반환하는 이진 변수입니다.

인티케이터 랜덤 변수는 확률을 기댓값으로 변환하는데 유용합니다. 어떤 사건이 발생할 확률을 구해야 될 때 인디케이터 변수를 사용해 사건의 기댓값을 계산할 수 있습니다.

Lemma

주어진 사건 A에 대해, 인디케이터 랜덤 변수 I{A}의 기대값은 다음과 같습니다. 즉, 인디케이터 랜덤 변수의 기대값은 사건 A가 발생할 확률과 같습니다. 이를 증명하기 위한 과정은 다음과 같습니다:

사건 A의 보수(complement)인 /A 를 정의합니다. 기대값의 정의를 적용하면: 즉, 인디케이터 랜덤 변수의 기대값은 사건 A가 발생할 확률과 정확히 일치하게 됩니다.

Example

문제 - n번의 동전 던지기에서 앞면이 나오는 횟수의 기대값을 계산하기

먼저, X를 n번의 동전 던지기에서 앞면이 나온 횟수를 나타내는 확률 변수로 정의합니다. 그럼 X의 대한 기댓값은 다음과 같이 계산할 수 있습니다. 이 식은 이는 각 k(앞면의 개수)별로 해당 값이 나올 확률을 곱한 뒤 더하는 것을 의미합니다.

이 식은 인디케이터 랜덤 변수를 활용해 더 간단하게 만들 수 있습니다. X_i를 정의하여, i번째 동전 던지기가 앞면이 나오는 사건을 나타내는 인디케이터 랜덤 변수로 설정합니다. 즉, i-번째 동전 던지기에서 앞면이 나오면 X_i=1, 나오지 않으면 X_i=0입니다.

동전 던지기에서 앞면이 나오는 총 횟수 X는 각 동전 던지기에서 앞면이 나왔는지 여부를 나타내는 인디케이터 랜덤 변수들의 합으로 표현될 수 있습니다. 즉, 모든 n번의 동전 던지기에 대해 앞면이 나온 횟수는 각 인디케이터 변수 X_i들의 합입니다.

각 X_i의 기대값은 앞면이 나올 확률 Pr{H}와 같습니다. 즉, 균등한 동전을 가정할 때

그리고 앞면이 나오는 총 횟수 X의 기대값은 모든 X_i의 기대값의 합으로 계산됩니다. 그러므로 n번의 동전 던지기에서 앞면이 나오는 기대값은 n/2로 계산됩니다.

참고로 이게 가능한 이유는 기댓값의 선형성(Linearity of Expectation) 때문입니다.

기댓값의 선형성

기대값의 선형성은 기대값을 구할 때, 랜덤 변수들의 합의 기대값이 랜덤 변수들의 기대값의 합과 같다는 원리입니다. 중요한 점은 각 랜덤 변수들 간의 독립 여부와 상관없이 이 법칙이 적용된다는 점입니다.

즉, 기댓값을 구할 때 이렇게 바꿔서 구할 수 있습니다.

채용 문제 분석

이제 X_i를 다음과 같이 후보자가 고용되는 사건에 대한 인디케이터 랜덤 변수도 정의합니다.

이제 다음의 특성을 활용해 채용 문제를 분석할 수 있습니다.

Pr{candidate i is hired} 즉, i번째 후보자가 고용될 확률은 i번째 후보자가 가장 뛰어날 확률로 볼 수 있습니다. 후보자들이 누가 가장 뛰어난 사람인지는 동일한 확률이기에 이는 1/i입니다. 이제 Lemma를 통해서 인디케이터 랜덤 변수 X_i의 기댓값이 1/i임을 알 수 있습니다.

이제 고용 비용의 기대값, E{X}를 다음과 같이 계산할 수 있습니다. (조화급수의 합은 ln(n)으로 근사 가능) (O(1)은 상수 항으로 n에 비례하지 않는 작은 값임)

따라서 기대 고용 비용은 다음과 같이 계산됩니다.

이 O(c_h * ln(n)) 은 최악의 케이스에서 봤던 O(c_h * n)보다 낮은데, 이를 통해 무작위 순서로 후보자를 면접할 때 기대되는 비용을 낮출 수 있다는 것을 알 수 있습니다.

랜덤화 알고리즘이란?

랜덤화 알고리즘은 동작이 난수 생성기(random-number generator)에 의해 결정되는 알고리즘입니다. 즉, 실행될 때마다 다른 결과를 내놓을 수 있습니다.

보통 RANDOM(a,b)으로 표시하며 RANDOM(a,b)는 a부터 b까지의 범위에서 동일한 확률로 난수를 선택해 반환합니다.

현실에선 완전히 무작위한 난수를 생성할 수 없습니다. 따라서 결정론적 방법으로 난수가 생성되지만 통계적으로 무작위처럼 보이는 의사 난수 생성기(pseudorandom-number generator)를 사용합니다.

랜덤화 알고리즘은 알고리즘이 실행될 때마다 다른 경로를 따를 수 있기에, 입력이 최적화되지 않았거나 예측 불가능한 경우에 최악의 성능을 유발하지 않도록 도와줍니다.

채용 문제에서 결정적 알고리즘과 랜덤화 알고리즘의 차이

• 결정적 알고리즘은 입력된 순서에 의존하여 고용 횟수가 결정되며, 이는 주어진 입력에서 항상 같은 결과를 산출합니다.

• 랜덤화 알고리즘은 입력 분포를 가정하지 않고, 입력에 무작위성을 부여함으로써, 후보자의 순서가 알고리즘의 성능에 미치는 영향을 줄일 수 있습니다.

배열을 무작위로 섞기

목표 : 균등한 무작위 순열(uniform random permutation)을 생성하기. 단, 배열의 모든 n!개의 가능한 순열 중 하나가 동일한 확률로 선택되야 함.

(여기선 각 요소 A[i]가 특정 위치로 이동할 확률이 1/n 임을 증명하는 것이 목표가 아님) (대신에 전체 순열이 균등하게 분포되는지에 초점을 맞춤)

의사코드 (psedocode)

각 반복에서, 현재 처리 중인 A[i] 요소를 배열의 남은 부분에서 무작위로 선택된 요소와 교환합니다. 교환 후 A[i]는 다시 바뀌지 않으며, 그 자리에 고정됩니다.

시간 복잡도(Time Complexity)

각 반복(iteration)은 상수 시간(O(1))에 수행됩니다. n번의 반복이 있으므로, 전체 알고리즘의 시간 복잡도는 O(n)입니다.

Lemma

무작위 배열 순열(Randomly Permuting an Array)은 균등한 무작위 순열을 생성한다.

Proof

1. 루프 불변식 : i-번째 반복 직전까지의 부분 배열 A[1:i−1]에는 (i−1)-순열이 포함되어 있으며, 이 순열은 (n−i+1)!/n!의 확률로 발생합니다.

2. i=1 일 때, 0-순열(즉, 빈 순열)이 부분 배열 A[1:0]에 포함됩니다. n!/n!=1이므로, 이 빈 배열은 100% 확률로 0-순열을 포함합니다. 즉, 배열이 비어 있고, 이 빈 배열은 확률 1로 0-순열을 포함하게 됩니다.

3. i-번째 반복 직전까지, 부분 배열 A[1:i−1]에 (i−1)-순열이 포함되어 있다고 가정합니다. 이 부분 배열은 (n−i+1)!/n!의 확률로 해당 순열을 포함합니다. 알고리즘의 i-번째 반복에서, 배열 A[i]와 무작위로 선택된 요소가 교환됩니다. 이로 인해 배열의 무작위성이 유지됩니다.

4. 알고리즘이 n번 반복을 완료하고 종료될 때, 종료 시점에서는 배열 A[1:n]이 완전한 n-순열을 포함하며, 이 순열은 1/n!의 확률로 발생합니다. 따라서 모든 가능한 n-순열이 동일한 확률로 발생한다는 것을 보장합니다.

팩토리 패턴은 객체 생성 매커니즘을 별도의 클래스나 메서드로 분리하여, 객체생성을 담당하는 코드와 클라이언트 코드(객체를 사용하는 코드)를 분리하는 디자인 패턴입니다. 이 패턴을 통해 객체 생성 과정을 캡슐화 할 수 있으며 클라이언트 코드가 객체의 생성 방식에 의존하지 않게 되어 코드의 확장성과 유지보수성이 향상됩니다.

팩토리 패턴의 사용 이유

1. 객체 생성의 캡슐화

객체 생성 매커니즘이 별도 클래스나 메서드로 분리되기에 코드 구조가 깔끔해집니다.

2. 확장성

새로운 객체가 추가할 때 클라이언트 코드를 수정하지 않고, 객체 생성을 담당하는 팩토리 클래스나 메서드를 확장하거나 수정하기만 하면 됩니다.

3. 의존성 감소

클라이언트 코드가 구체적인 클래스에 의존하는 것이 아닌 추상 클래스나 인터페이스에 의존하기에 코드를 수정할 때 보다 용이해집니다.

팩토리 패턴의 종류

팩토리 패턴은 주로 심플 팩토리 패턴, 팩토리 메서드 패턴, 추상 팩토리 패턴이 있습니다.

심플 팩토리 패턴

심플 팩토리 패턴은 객체 생성을 담당하는 클래스나 메서드를 따로 두는 것을 의미합니다.

예시 코드 :

// Animal 인터페이스 정의
public interface Animal
{
    void Speak();
}

// Cat 클래스 정의
public class Cat : Animal
{
    public void Speak()
    {
        Console.WriteLine("Meow");
    }
}

// Dog 클래스 정의
public class Dog : Animal
{
    public void Speak()
    {
        Console.WriteLine("Woof");
    }
}

// AnimalFactory 클래스 정의 (팩토리 패턴)
public class AnimalFactory
{
    // 동물을 생성하는 메서드
    public static Animal CreateAnimal(string animalType)
    {
        if (animalType == "Cat")
        {
            return new Cat();
        }
        else if (animalType == "Dog")
        {
            return new Dog();
        }
        else
        {
            throw new ArgumentException("Unknown animal type");
        }
    }
}

// 사용 예시 (클라이언트 코드)
class Program
{
    static void Main(string[] args)
    {
        // 팩토리 패턴을 이용한 객체 생성
        Animal cat = AnimalFactory.CreateAnimal("Cat");
        Animal dog = AnimalFactory.CreateAnimal("Dog");

        cat.Speak(); // 출력: Meow
        dog.Speak(); // 출력: Woof
    }
}

위 코드를 살펴보면 AnimalFactory 클래스에서 if-else 문을 통해 클라이언트에서 사용할 동물 객체를 CreateAnimal() 메서드를 활용해 객체를 생성하고 있습니다. 이처럼 심플 팩토리는 생성 로직을 팩토리 클래스에 모아두는 것을 의미합니다.

다만 심플 팩토리 패턴은 만약 다른 클래스가 추가되었을 때 기존 코드를 수정해야합니다. 이는 확장에는 열려있으나 변경에는 닫혀있어야 하는 OCP 원칙(Open Close Principle)에 위배된다는 문제가 있습니다.

예를 들어, 또 다른 객체로 Horse나 Monkey가 추가 된다면 AnimalFactory 클래스를 수정해야만 합니다.

이는 프로젝트가 작을 때는 문제가 되지 않으나 프로젝트의 규모가 커지면서 문제가 발생할 수도 있습니다.

팩토리 메서드 패턴

팩토리 메서드 패턴은 객체 생성 방식을 하위 클래스에서 결정하는 패턴입니다. 즉 객체를 생성하는 매커니즘은 부모 클래스에서 정의하되, 실제로 생성되는 객체의 종류는 자식 클래스에서 결정됩니다.

• 부모 클래스 (또는 인터페이스) : 객체 생성 메서드를 정의
• 자식 클래스 : 실제 객체를 생성하는 로직을 구현

예시 코드 :

코드 복사
// Product 인터페이스 정의
public interface Product
{
    void Use();
}

// ConcreteProductA 클래스 정의
public class ConcreteProductA : Product
{
    public void Use()
    {
        Console.WriteLine("Using Product A");
    }
}

// ConcreteProductB 클래스 정의
public class ConcreteProductB : Product
{
    public void Use()
    {
        Console.WriteLine("Using Product B");
    }
}

// Creator 추상 클래스 (팩토리 메서드 패턴)
public abstract class Creator
{
    // 팩토리 메서드
    public abstract Product CreateProduct();

    // 생성된 제품을 사용하는 메서드
    public void UseProduct()
    {
        Product product = CreateProduct();
        product.Use();
    }
}

// ConcreteCreatorA 클래스 정의
public class ConcreteCreatorA : Creator
{
    public override Product CreateProduct()
    {
        return new ConcreteProductA();
    }
}

// ConcreteCreatorB 클래스 정의
public class ConcreteCreatorB : Creator
{
    public override Product CreateProduct()
    {
        return new ConcreteProductB();
    }
}

// 사용 예시
class Program
{
    static void Main(string[] args)
    {
        Creator creatorA = new ConcreteCreatorA();
        Creator creatorB = new ConcreteCreatorB();

        creatorA.UseProduct();  // 출력: Using Product A
        creatorB.UseProduct();  // 출력: Using Product B
    }
}

위 코드를 살펴보면, Use() 메서드를 정의하는 Product 인터페이스를 상속받는 ConcreteProductA와 ConcreteProductB 클래스에서 Product 인터페이스가 구현되어 있습니다. Creator 추상 클래스는 CreateProduct()라는 팩토리 메서드를 추상 메서드로 정의하고, 하위 클래스 CreateCreatorA 그리고 CreateCreatorB에서 추상 메서드를 오버라이드 해줍니다. 그리고 실제로 Product객체를 생성할 때는 CreateCreatorA 또는 CreateCreatorB 클래스를 사용합니다.

이렇게 패턴을 작성함으로서, 다른 Product객체가 추가된다 해도 Creator 추상 클래스의 수정없이 새로운 Product객체에 해당하는 Creator 클래스를 새로 작성하는 것으로 확장이 가능해집니다. (ex: ProductC 추가 -> CreateCreatorC 클래스 작성)

추상 팩토리 패턴

추상 팩토리 패턴은 연관된 객체들의 집합을 생성하는 인터페이스를 제공하는 패턴입니다. 팩토리 메서드 패턴에서 단일 객체를 생성하는 것과 달리, 여러 객체을 생성합니다. 여러 객체를 생성하는 메서드를 인터페이스를 통해 제공하고, 이를 상속받는 팩토리 클래스에서 그 메서드를 구현합니다.

• 추상 팩토리 (인터페이스) : 서로 관련된 객체들을 생성하는 메서드를 정의
• 실질 팩토리 : 추상 팩토리를 구현해서 각 제품군의 객체들을 생성
• 추상 객체 (인터페이스) : 여러 객체들의 공통 인터페이스를 정의
• 객체 : 추상 객체에서 정의한 인터페이스를 구현한 클래스로, 팩토리에서 생성

예시 코드 :

// Abstract ProductA
public interface AbstractProductA
{
    void UseA();
}

// Abstract ProductB
public interface AbstractProductB
{
    void UseB();
}

// Concrete ProductA1
public class ConcreteProductA1 : AbstractProductA
{
    public void UseA()
    {
        Console.WriteLine("Using Product A1");
    }
}

// Concrete ProductA2
public class ConcreteProductA2 : AbstractProductA
{
    public void UseA()
    {
        Console.WriteLine("Using Product A2");
    }
}

// Concrete ProductB1
public class ConcreteProductB1 : AbstractProductB
{
    public void UseB()
    {
        Console.WriteLine("Using Product B1");
    }
}

// Concrete ProductB2
public class ConcreteProductB2 : AbstractProductB
{
    public void UseB()
    {
        Console.WriteLine("Using Product B2");
    }
}

// Abstract Factory (객체 집합 생성 인터페이스)
public interface AbstractFactory
{
    AbstractProductA CreateProductA();
    AbstractProductB CreateProductB();
}

// Concrete Factory 1
public class ConcreteFactory1 : AbstractFactory
{
    public AbstractProductA CreateProductA()
    {
        return new ConcreteProductA1();
    }

    public AbstractProductB CreateProductB()
    {
        return new ConcreteProductB1();
    }
}

// Concrete Factory 2
public class ConcreteFactory2 : AbstractFactory
{
    public AbstractProductA CreateProductA()
    {
        return new ConcreteProductA2();
    }

    public AbstractProductB CreateProductB()
    {
        return new ConcreteProductB2();
    }
}

// 사용 예시
class Program
{
    static void Main(string[] args)
    {
        AbstractFactory factory1 = new ConcreteFactory1();
        AbstractFactory factory2 = new ConcreteFactory2();

        AbstractProductA productA1 = factory1.CreateProductA();
        AbstractProductB productB1 = factory1.CreateProductB();

        AbstractProductA productA2 = factory2.CreateProductA();
        AbstractProductB productB2 = factory2.CreateProductB();

        productA1.UseA(); // 출력: Using Product A1
        productB1.UseB(); // 출력: Using Product B1

        productA2.UseA(); // 출력: Using Product A2
        productB2.UseB(); // 출력: Using Product B2
    }
}

위 코드를 살펴보면, 관련있는 객체를 묶어주는 AbstractProductA와 AbstractProductB 인터페이스가 있으며, ConcreteProductA1, ConcreteProductA2 클래스는 AbstractProductA 인터페이스를, ConcreteProductB1, ConcreteProductB2 클래스는 AbstractProductB 인터페이스를 상속받아서 인터페이스를 구현하고 있습니다. 그리고 AbstractFactory 인터페이스는 연관있는 객체들의 집합을 생성하는 메서드를 정의하고 있으며, 이 인터페이스를 상속받는 ConcreteFactory1과 ConcreteFactory2 클래스에서 각각 메서드를 정의하고 서로 다른 객체 집합을 생성합니다.

이렇게 패턴을 작성함으로서, 객체 집합을 생성할 때, 한 팩토리에서 담당하게 설계할 수 있으며, 팩토리 메서드 패턴과 동일하게 OCP 원칙을 지키면서 코드를 작성할 수 있습니다.

ex:

• 몬스터를 소환한다 가정할 때, OrcFactory 팩토리 클래스에서 Orc, BattleAxe, Leather Armor 객체를 같이 생성. (각각 AbstractFactory, Monster, Weapon, Armor 인터페이스를 상속받음)
• 나중에 몬스터로 Ghost가 추가되어도, 새롭게 GhostFactory 클래스를 작성하고, 그 안에서 메서드를 오버라이드해서 Ghost, GhostHand, WhiteCloth 객체들을 생성

마지막으로 제가 사용했었던 심플 팩토리 코드입니다. 그리 효율적이진 못하니 참고만 해주세요.

public class CharacterStatsInitFactory
{
    public static ArisuStats InitArisuStats()
    {
        return new ArisuStats
        {
            skillDamage = 50,
            skillSpeed = 30,
            manaCost = 50,
            skillCoolDown = 2f,
            playerSpeed = 5,
            playerDamage = 1,
            maxHealth = 10,
            maxMana = 100,
            manaRegenPerSecond = 20f
        };
    }

    public static MidoriStats InitMidoriStats()
    {
        return new MidoriStats
        {
            skillDamage = 10,
            skillSpeed = 30,
            manaCost = 30,
            skillCoolDown = 3f,
            detectionAngle = 120f,
            playerSpeed = 5,
            playerDamage = 1,
            maxHealth = 10,
            maxMana = 100,
            manaRegenPerSecond = 20f
        };
    }

    public static MomoiStats InitMomoiStats()
    {
        return new MomoiStats
        {
            skillDamage = 5,
            skillSpeed = 30,
            manaCost = 20,
            skillCoolDown = 3f,
            bulletCount = 10,
            spreadAngle = 90f,
            playerSpeed = 5,
            playerDamage = 1,
            maxHealth = 10,
            maxMana = 100,
            manaRegenPerSecond = 20f
        };
    }

    public static UZStats InitUZStats()
    {
        return new UZStats
        {
            skillDamage = 10,
            skillSpeed = 15,
            skillDuration = 4f,
            manaCost = 80,
            skillCoolDown = 10f,
            playerSpeed = 5,
            playerDamage = 1,
            maxHealth = 10,
            maxMana = 100,
            manaRegenPerSecond = 20f
        };
    }
}

객체 지향 프로그래밍 개발을 하면서 자주 발생하는 문제들을 해결하기 위해 사용되는 검증된 해결책의 모음입니다. 각 문제에 대한 정형화된 해결 방식을 제시하는 디자인 패턴을 사용하면 코드를 보다 유연하고 견고하게 작성할 수 있습니다.

디자인 패턴의 목적

-개발자 간 의사소통의 편의성

예를 들어, 서로 디자인 패턴을 알고 있는 상태에서 '여기선 객체를 만들어 반환하는 함수를 통해 초기화 과정을 외부로부터 숨겨놓고 반환타입을 제어하는게 좋겠네요.' 보단 '여기선 팩토리 패턴을 사용하는게 좋겠네요.' 가 서로 이해하는데 더 편리할 것이다.

-코드 간 유연성 향상

디자인 패턴은 객체 간의 관계를 유연하게 관리할 수 있는 구조를 제공해줍니다. 따라서 객체 지향 프로그래밍 구조를 구현하는데 유용합니다.

디자인 패턴의 유형

디자인 패턴은 크게 생성 패턴, 구조 패턴, 행위 패턴으로 구분됩니다.

-생성 패턴

객체 생성과 관련된 패턴으로, 객체 생성 과정을 추상화하거나 캡슐화시켜주는 매커니즘을 제공합니다.

-구조 패턴

객체나 클래스를 조합하여 더 큰 구조를 만들어 내는 패턴으로, 객체의 확장성을 높여줍니다.

-행동 패턴

객체나 클래스 간의 상호작용을 도와주는 패턴으로, 객체들 간 소통 방법이나 역할 할당을 도와줍니다.

디자인 패턴의 주의점

디자인 패턴이 필요가 없는 상황에도 디자인 패턴을 적용해 코드가 더 복잡해질 수도 있다. 오히려 디자인 패턴을 사용하려고 하다가 빙 돌아가는 상황이 생길 수도 있으니 필요한 상황에 적재적소에 쓰는 것이 좋을 것이다.

오브젝트 풀링의 동작 방식

1. 오브젝트 풀 생성(Create) 게임을 시작하면서 사용될 오브젝트들의 인스턴스를 필요한 만큼 미리 생성하고 풀에 저장한다.

2. 오브젝트 요청(Call) 게임 중 오브젝트가 필요할 때마다 Instantiate를 사용하는 것이 아닌, 풀에서 오브젝트를 가져온다.

3. 오브젝트 반환(Return) 다 사용한 오브젝트는 Destroy를 호출해 삭제시키는 것이 아니라, 풀로 반환하여 다음 요청 때 재사용할 준비를 한다.

그러면 이런 오브젝트 풀링은 왜 사용하는 걸까?

오브젝트 풀링의 사용 이유

*1. 성능 최적화 * 오브젝트를 매번 새로 생성하고 삭제할 때마다 메모리 할당과 해제 비용이 발생한다. 오브젝트 수가 많아질수록 이 비용이 커져서 게임 성능에 영향을 미칠 수 있다. 오브젝트 풀링을 사용하면 오브젝트를 미리 생성해 두고 재사용하기 때문에 이러한 성능 저하를 막을 수 있다.

2. 가비지 컬렉터(GC) 호출 감소
Destroy 메서드를 호출하면 사용하지 않는 메모리를 해제하는 과정에서 가비지 컬렉터가 작동하게 된다. 이 가비지 컬렉션이 빈번하게 발생하면 게임이 일시적으로 멈추거나 렉이 걸릴 수 있다. 오브젝트 풀링을 사용하면 Destroy 호출을 줄여 가비지 컬렉션의 빈도를 낮출 수 있다.

아래는 내가 사용했던 오브젝트 풀링 코드이다.

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


public class PoolManager : MonoBehaviour
{
    public static PoolManager Inst { get; private set; }

    // 프리펩을 보관할 변수
    public GameObject[] prefabs;

    // 풀 담당을 하는 리스트들
    List<GameObject>[] pools;

    private void Awake()
    {
        if (Inst == null)
        {
            Inst = this;
            DontDestroyOnLoad(gameObject); // 씬 전환 시에도 유지
        }
        else if (Inst != this)
        {
            Destroy(gameObject); // 기존 인스턴스가 있다면 새로운 것을 파괴
        }

        // pools의 길이를 프리펩의 길이 만큼 선언
        pools = new List<GameObject>[prefabs.Length];


        // 각 인덱스마다 프리펩을 담을 리스트 선언
        for (int index = 0; index < pools.Length; index++)
            pools[index] = new List<GameObject>();
    }

    public GameObject GetObject(PoolObjectType poolObjectType)
    {
        GameObject select = null;
        int index = (int)poolObjectType;

        // 해당 인덱스의 게임 오브젝트 리스트 중 비활성화된 게임 오브젝트 선택 후 select에 할당
        foreach (GameObject prefab in pools[index]) 
        {
            if(!prefab.activeSelf)
            {
                select = prefab;
                select.SetActive(true);
                break;
            }
        }

        // 만약 다 사용 중이면 새롭게 생성 후 select에 할당
        if(!select)
        {
            select = Instantiate(prefabs[index], transform);
            pools[index].Add(select);
        }

        // 선택된 게임 오브젝트 반환
        return select;
    }

    public void ReturnObject(GameObject obj)
    {
        // 반환할 오브젝트를 비활성화하여 풀에 다시 넣음
        obj.SetActive(false);
    }
}

코드 분석

코드를 하나씩 살펴보면,

    private void Awake()
    {
        //... 싱글톤 패턴 ...

        // pools의 길이를 프리펩의 길이 만큼 선언
        pools = new List<GameObject>[prefabs.Length];


        // 각 인덱스마다 프리펩을 담을 리스트 선언
        for (int index = 0; index < pools.Length; index++)
            pools[index] = new List<GameObject>();
    }

Awake 메서드에서는 pools(GameObject List)를 prefabs(GameObject Array)의 길이만큼 선언해 준다. 예를 들어 prefabs에 BulletPrefab, EnemyPrefab, ItemPrefab이 있다면, pools는 3개의 크기로 선언된다. 그리고 각 index마다 프리팹을 담을 리스트를 선언해 준다.

방금 예시로 든 BulletPrefab, EnemyPrefab, ItemPrefab에 대한 리스트가 각각 생성되며, 이는 일종의 2차원 리스트 구조라고 볼 수 있다.

    public GameObject GetObject(PoolObjectType poolObjectType)
    {
        GameObject select = null;
        int index = (int)poolObjectType;

        // 해당 인덱스의 게임 오브젝트 리스트 중 비활성화된 게임 오브젝트 선택 후 select에 할당
        foreach (GameObject prefab in pools[index]) 
        {
            if(!prefab.activeSelf)
            {
                select = prefab;
                select.SetActive(true);
                break;
            }
        }

        // 만약 다 사용 중이면 새롭게 생성 후 select에 할당
        if(!select)
        {
            select = Instantiate(prefabs[index], transform);
            pools[index].Add(select);
        }

        // 선택된 게임 오브젝트 반환
        return select;
    }

그 다음에 GetObject 메서드가 poolObjectType을 매개변수로 받으면서 호출된다. 여기서 poolObjectType은 enum으로 인덱스 역할을 하며 다음과 같이 선언되어 있다.

public enum PoolObjectType
{
    Bullet,
    Enemy,
    Item
}

그리고 GameObject 타입 변수, select를 선언해주고 매개변수로 받은 poolObjectType으로 pools에서 원하는 리스트가 있는 인덱스를 참조한다. 그리고 그 리스트에서 활성화되지 않은 오브젝트가 있다면, select는 그 오브젝트를 참조하고, 오브젝트를 활성화한다.

만약 리스트를 다 돌았는데도 활성화되지 않은 오브젝트가 없다면 (즉 모든 오브젝트가 사용 중이거나 아예 없다면) Instantiate를 호출하고 생성된 오브젝트를 pools의 리스트에 추가한다.

예를 들어, 만약 매개변수로 Bullet이 들어오면 pools[0]에 위치한 리스트를 순회하고 만약 사용 중이지 않은 오브젝트가 있다면 걔를 반환하고, 없다면 생성 후 pools[0]에 위치한 리스트에 추가한다.

그리고 select(선택한 오브젝트)를 반환한다.

    public void ReturnObject(GameObject obj)
    {
        // 반환할 오브젝트를 비활성화하여 풀에 다시 넣음
        obj.SetActive(false);
    }

ReturnObject 메서드에선 반환할 오브젝트를 매개변수로 받고 obj.SetActive(false);로 사용이 다 끝난 오브젝트를 비활성화 시켜준다.

int형 index 대신 enum을 사용했다. 그리고 오브젝트를 반환하기 위한 목적으로ReturnObject 메서드를 정의했는데 내가 만든 게임에선 obj.SetActive(false);로 사용해도 별 문제가 없었다.

하지만 아래처럼 추가적인 로직이 필요할 경우, ReturnObject 메서드를 사용하는 것이 더 나을 것이다.

    public void ReturnObject(GameObject obj)
    {
        // 반환할 오브젝트를 비활성화하여 풀에 다시 넣음
        obj.SetActive(false);
        // 오브젝트의 계층 관리
        bullet.transform.SetParent(Instance.transform);

        // 이 외의 다른 로직들...
    }

위의 PoolManager 클래스는 싱글톤 패턴도 적용되어 있는데 이는 다른 포스트에서 다뤄보도록 하겠다.

참고자료: 골드메탈 유튜브 강의 티스토리 포스트 베르의 프로그래밍 노트