1. 병합정렬
시간 복잡도 : nlogn
public static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
private static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
Array.Copy(arr, left, leftArr, 0, n1);
Array.Copy(arr, mid + 1, rightArr, 0, n2);
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2)
{
if (leftArr[i] <= rightArr[j])
{
arr[k] = leftArr[i];
i++;
}
else
{
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = rightArr[j];
j++;
k++;
}
}
단점
- 추가 메모리 공간이 필요하다.
- 내부 정렬이 아니다.
장점
- 최악의 경우에도 일정한 성능을 보장한다.
- 안정적인 정렬
2. 퀵정렬
시간 복잡도 : nlogn
public static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivotIndex = Partition(arr, low, high);
QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}
private static int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp2 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp2;
return i + 1;
}
단점
- 시간복잡도가 최악의 경우 n^2까지 증가할 수 있음.
- 불안정 정렬
장점
- 평균적으로 빠르다.
- 내부 정렬을 한다.
3. 힙정렬
시간 복잡도 : nlogn
public static void HeapSort(int[] arr)
{
int n = arr.Length;
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
for (int i = n - 1; i > 0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
Heapify(arr, i, 0);
}
}
private static void Heapify(int[] arr, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
Heapify(arr, n, largest);
}
}
4. BigO 표기법 (Big O Notation)
빅오 표기법은 알고리즘의 성능을 수학적으로 표현하는 방법.
입력값의 크기(n)이 커질수록 알고리즘의 실행시간이나 메모리 사용량이 얼마나 증가하는지를 나타냄.
이는 알고리즘의 최악의 경우 성능을 나타내며, 하드웨어 구현 방식 같은 세부 사항을 무시하고 오직 알고리즘의 효율성 자체를 평가하는데 사용 됨.
주요 빅오 표기법과 특징
표기법 명칭 설명
| O(1) | 상수 시간 | 입력값의 크기에 관계없이 실행 시간이 항상 일정합니다. (예: 배열의 특정 인덱스에 접근) |
| O(logn) | 로그 시간 | 입력값의 크기가 커질수록 실행 시간은 매우 느리게 증가합니다. (예: 이진 탐색) |
| O(n) | 선형 시간 | 입력값의 크기에 비례하여 실행 시간이 증가합니다. (예: 배열의 모든 요소를 순회) |
| O(nlogn) | 선형 로그 시간 | 퀵 정렬, 병합 정렬 등 효율적인 정렬 알고리즘의 평균적인 시간 복잡도입니다. |
| O(n2) | 2차 시간 | 입력값의 제곱에 비례하여 실행 시간이 증가합니다. 비효율적인 알고리즘으로 여겨집니다. (예: 이중 루프를 사용하는 버블 정렬) |
| O(2n) | 지수 시간 | 입력값이 조금만 커져도 실행 시간이 기하급수적으로 증가합니다. 매우 비효율적입니다. (예: 재귀를 사용하는 피보나치 수열) |
5. 디자인 패턴
디자인 패턴은 소프트웨어 설계 과정에서 자주 발생하는 문제를 해결하기 위한 정형화된 접근 방법
1. 싱글톤 패턴 (Singleton Pattern)
목적: 클래스의 인스턴스를 오직 하나만 생성하고, 어디서든지 그 인스턴스에 접근할 수 있도록 함. 사용 예시: 게임의 설정 관리자, 데이터베이스 연결 풀, 로거(Logger) 등과 같이 프로그램 전체에서 공유되어야 하는 유일한 객체를 만들 때 사용
코드 보기
// GameManager.cs
// 게임의 전체 상태를 관리하는 싱글톤 클래스
public sealed class GameManager
{
// 클래스의 유일한 인스턴스
private static GameManager instance = null;
private static readonly object padlock = new object();
public string CurrentGameState { get; private set; }
// 외부에서 직접 생성하지 못하도록 private 생성자로 선언
private GameManager()
{
CurrentGameState = "초기화 중";
}
// 전역적으로 접근 가능한 인스턴스 속성
public static GameManager Instance
{
get
{
// 스레드 안정성을 위한 lock
lock (padlock)
{
if (instance == null)
{
instance = new GameManager();
}
return instance;
}
}
}
// 게임 상태를 변경하는 메서드
public void SetState(string state)
{
this.CurrentGameState = state;
Console.WriteLine($"게임 상태가 '{this.CurrentGameState}'로 변경되었습니다.");
}
// 사용 예시
public void StartGame()
{
// 싱글톤 인스턴스에 접근
GameManager.Instance.SetState("게임 시작");
}
}
2. 옵저버 패턴 (Observer Pattern)
목적: 한 객체(주체)의 상태 변화에 따라 다른 객체들(관찰자)에게 자동으로 알림을 보내고, 그에 따른 작업을 수행하게 함. 사용 예시: 게시판에서 새로운 글이 등록되면 알림을 보내거나, 주식 가격이 변동할 때 사용자에게 알림을 주는 시스템에 사용.
코드 보기
// IObserver.cs - 관찰자 인터페이스
public interface IObserver
{
void OnNotify(string message);
}
// Player.cs - 주체 (Subject)
public class Player
{
private List<IObserver> observers = new List<IObserver>();
private int level = 1;
public void Attach(IObserver observer)
{
observers.Add(observer);
}
public void LevelUp()
{
level++;
string message = $"플레이어가 레벨 {level}로 올랐습니다!";
Notify(message);
}
private void Notify(string message)
{
foreach (var observer in observers)
{
observer.OnNotify(message);
}
}
}
// UIManager.cs - 관찰자 (Observer)
public class UIManager : IObserver
{
public void OnNotify(string message)
{
Console.WriteLine($"[UI 알림] {message}");
}
}
// AchievementSystem.cs - 관찰자 (Observer)
public class AchievementSystem : IObserver
{
public void OnNotify(string message)
{
if (message.Contains("레벨 10"))
{
Console.WriteLine("[도전 과제] '베테랑' 도전 과제를 달성했습니다!");
}
}
}
// 사용 예시
// var player = new Player();
// var uiManager = new UIManager();
// var achievementSystem = new AchievementSystem();
// player.Attach(uiManager);
// player.Attach(achievementSystem);
// player.LevelUp(); // UI와 도전 과제 시스템에 알림
3. 팩토리 패턴 (Factory Pattern)
목적: 객체 생성 로직을 캡슐화하여, 어떤 객체를 생성할지 결정하는 책임을 서브클래스에 위임함. 사용 예시: 게임에서 캐릭터 클래스(기사, 마법사 등)를 생성할 때, 팩토리 클래스에 '기사'를 요청하면 해당 객체를 만들어 반환하는 방식에 사용.
코드 보기
// IEnemy.cs - 공통 인터페이스
public interface IEnemy
{
void Attack();
}
// Orc.cs - 구체적인 객체
public class Orc : IEnemy
{
public void Attack()
{
Console.WriteLine("오크가 도끼로 공격합니다!");
}
}
// Goblin.cs - 구체적인 객체
public class Goblin : IEnemy
{
public void Attack()
{
Console.WriteLine("고블린이 단검으로 공격합니다!");
}
}
// EnemyFactory.cs - 팩토리 클래스
public class EnemyFactory
{
public static IEnemy CreateEnemy(string type)
{
switch (type.ToLower())
{
case "orc":
return new Orc();
case "goblin":
return new Goblin();
default:
throw new ArgumentException("알 수 없는 적 타입입니다.");
}
}
}
// 사용 예시
// var orc = EnemyFactory.CreateEnemy("orc");
// orc.Attack();
4. 상태 패턴 (State Pattern)
목적: 객체의 내부 상태가 변할 때 객체의 동작을 변경합니다. 마치 객체 자신이 클래스를 변경하는 것처럼 보임. 사용 예시: 게임 캐릭터가 '걷기' 상태일 때와 '점프' 상태일 때의 행동이 달라지는 경우에 사용됩니다. 각 상태를 클래스로 만들어 관리하면 코드가 깔끔해짐.
코드 보기
// ICharacterState.cs
// 캐릭터 상태를 정의하는 인터페이스
public interface ICharacterState
{
void EnterState(Character character); // 상태 진입 시 호출
void UpdateState(Character character); // 상태 업데이트 (매 프레임)
void ExitState(Character character); // 상태 종료 시 호출
}
// IdleState.cs
// 대기 상태
public class IdleState : ICharacterState
{
public void EnterState(Character character)
{
Console.WriteLine("캐릭터가 대기 상태에 진입했습니다.");
// 캐릭터의 애니메이션을 Idle로 설정
}
public void UpdateState(Character character)
{
// 플레이어 입력에 따라 상태를 변경
if (character.HasMoveInput)
{
character.ChangeState(new MovingState());
}
}
public void ExitState(Character character)
{
Console.WriteLine("캐릭터가 대기 상태에서 벗어납니다.");
}
}
// MovingState.cs
// 이동 상태
public class MovingState : ICharacterState
{
public void EnterState(Character character)
{
Console.WriteLine("캐릭터가 이동 상태에 진입했습니다.");
// 캐릭터의 애니메이션을 Move로 설정
}
public void UpdateState(Character character)
{
// 캐릭터를 이동시킵니다
Console.WriteLine("캐릭터가 이동 중입니다.");
// 입력이 없으면 대기 상태로 변경
if (!character.HasMoveInput)
{
character.ChangeState(new IdleState());
}
}
public void ExitState(Character character)
{
Console.WriteLine("캐릭터가 이동 상태를 종료합니다.");
}
}
// Character.cs
// 상태를 관리하는 캐릭터 클래스
public class Character
{
private ICharacterState currentState;
public bool HasMoveInput { get; set; } // 예시용 입력값
public Character()
{
// 초기 상태 설정
currentState = new IdleState();
currentState.EnterState(this);
}
public void ChangeState(ICharacterState newState)
{
currentState.ExitState(this);
currentState = newState;
currentState.EnterState(this);
}
public void Update()
{
currentState.UpdateState(this);
}
}
// main 함수에서 사용 예시
/*
var player = new Character();
player.Update(); // 출력: "캐릭터가 대기 중입니다."
player.HasMoveInput = true;
player.Update(); // 출력: "캐릭터가 대기 상태에서 벗어납니다.", "캐릭터가 이동 상태에 진입했습니다.", "캐릭터가 이동 중입니다."
*/
5. 컴포넌트 패턴 (Composite Pattern)
목적: 객체들을 트리 구조로 구성하여, '부분'과 '전체'를 동일한 방식으로 다룰 수 있게 함. 사용 예시: UI 툴킷에서 버튼(부분)과 패널(전체)을 동일한 인터페이스로 다루어, 패널에 속한 모든 버튼을 한 번에 숨기는 것과 같은 작업을 할 때 유용.
코드 보기
// IGameObject.cs - 공통 인터페이스
public interface IGameObject
{
void Render();
}
// Player.cs - 개별 오브젝트 (Leaf)
public class Player : IGameObject
{
public void Render()
{
Console.WriteLine("플레이어 캐릭터를 그립니다.");
}
}
// Weapon.cs - 개별 오브젝트 (Leaf)
public class Weapon : IGameObject
{
public void Render()
{
Console.WriteLine("무기를 그립니다.");
}
}
// CompositeGameObject.cs - 복합 오브젝트 (Composite)
public class CompositeGameObject : IGameObject
{
private List<IGameObject> children = new List<IGameObject>();
public void Add(IGameObject gameObject)
{
children.Add(gameObject);
}
public void Render()
{
Console.WriteLine("복합 오브젝트를 그립니다.");
foreach (var child in children)
{
child.Render();
}
}
}
// 사용 예시
// var player = new Player();
// var weapon = new Weapon();
// var playerWithWeapon = new CompositeGameObject();
// playerWithWeapon.Add(player);
// playerWithWeapon.Add(weapon);
// playerWithWeapon.Render(); // 플레이어와 무기를 함께 렌더링
'XR 기술을 활용한 게임 개발자 부트 캠프 > TIL' 카테고리의 다른 글
| 유니티 입문 (1) 251013 (0) | 2025.10.14 |
|---|---|
| 메모리 구조 250930 (0) | 2025.10.14 |
| 알고리즘 디자인과 디자인 패턴 기초 (1) 250926 (0) | 2025.10.14 |
| 자료구조를 활용한 데이터 관리 (3) 250925 (0) | 2025.10.14 |
| 자료구조를 활용한 데이터 관리 (2) 250924 (0) | 2025.10.14 |