🧩 병합 정렬 (Merge Sort) – 항상 안정적인 분할 정복 정렬

1. 개념

병합 정렬은 분할 정복(Divide and Conquer) 알고리즘의 대표 예시이다.
배열을 반으로 나누고, 나눈 배열을 각각 정렬한 후, 두 정렬된 배열을 **병합(merge)**하여 최종 정렬된 배열을 만든다.

2. 작동 방식 요약

1. 배열을 반으로 분할
2. 각각을 재귀적으로 병합 정렬
3. 두 정렬된 배열을 정렬된 상태로 병합
4. 더 이상 나눌 수 없을 때까지 반복

3. C# 예제 코드 (새로운 예시)

void MergeSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    int mid = (left + right) / 2;

    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] temp = new int[right - left + 1];

    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= right)
        temp[k++] = arr[j++];

    // 원래 배열에 복사
    for (int t = 0; t < temp.Length; t++)
        arr[left + t] = temp[t];
}

✅ 사용 예:

int[] data = { 6, 2, 9, 1, 5 };
MergeSort(data, 0, data.Length - 1);

4. 시간/공간 복잡도

• 공간 복잡도: O(n)
  → 정렬을 위해 임시 배열이 필요함

5. 특징

• 항상 안정적인 시간 복잡도 O(n log n)
• 안정 정렬 (동일 값의 순서 보존)
• 추가 메모리 공간 필요 (In-place 아님)
• 큰 데이터, 안정성이 중요한 경우에 적합

6. 예시

[4, 1, 3, 2]
→ 나누기: [4, 1] / [3, 2]
→ 정렬: [1, 4] / [2, 3]
→ 병합: [1, 2, 3, 4]

7. 마무리 요약

• 병합 정렬은 시간 복잡도가 항상 O(n log n)으로 예측 가능하여 신뢰도가 높다.
• 퀵 정렬보다 느릴 수 있지만, 데이터가 정렬된 상태와 무관하게 안정적인 성능을 낸다는 점에서 강력한 선택이다.
• 추가 메모리가 필요하다는 점은 고려해야 한다.

⚡ 퀵 정렬 (Quick Sort) – 빠르고 강력한 분할 정복 정렬 알고리즘

1. 개념

퀵 정렬은 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다.
중간 기준값(피벗)을 선택하여 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤,
각 부분을 재귀적으로 정렬하는 방식으로 작동한다.

2. 작동 방식 요약

1. 피벗(Pivot)을 선택
2. 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할
3. 각 부분 배열에 대해 재귀적으로 퀵 정렬 수행
4. 병합 없이 정렬 완료

3. C# 예제 코드 (새로운 예시)

void QuickSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    int pivotIndex = Partition(arr, left, right);

    QuickSort(arr, left, pivotIndex - 1);
    QuickSort(arr, pivotIndex + 1, right);
}

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

    for (int j = left; j < right; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]); // C# 튜플 스왑
        }
    }

    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
    return i + 1;
}

✅ 사용 예:

int[] data = { 8, 4, 7, 3, 10, 2 };
QuickSort(data, 0, data.Length - 1);

4. 시간/공간 복잡도

• 공간 복잡도: O(log n) (재귀 호출 스택)

5. 특징

• 비교 기반 정렬 중 매우 빠름
• 불안정 정렬 (같은 값의 순서가 바뀔 수 있음)
• 제자리 정렬(In-place): 별도 배열이 필요하지 않음
• 피벗 선택 방식에 따라 성능이 달라짐 (랜덤 피벗, 중앙값 등 개선 가능)

6. 예시

[5, 2, 8, 1, 6]
→ 피벗: 6 → [5, 2, 1] [6] [8]
→ 왼쪽 정렬: [2, 1, 5] → [1, 2, 5]
→ 최종 정렬: [1, 2, 5, 6, 8]

7. 마무리 요약

• 퀵 정렬은 많은 데이터에 빠르게 정렬을 수행할 수 있는 알고리즘이다.
• 다만, 피벗 선택을 잘못하면 성능이 급격히 나빠질 수 있기 때문에, 개선된 버전(랜덤 피벗, 3-way 퀵 정렬 등)도 많이 활용된다.
• 실제 라이브러리 내부에서도 자주 사용됨.

📥 삽입 정렬 (Insertion Sort) – 직관적이고 효율적인 정렬 방법

1. 개념

삽입 정렬은 카드 정렬과 비슷한 방식으로 작동한다.
두 번째 원소부터 시작해서, 앞쪽 정렬된 구간에 자신이 들어갈 자리를 찾아 삽입하는 방식이다.

2. 알고리즘 동작 방식

1. 두 번째 원소부터 시작
2. 현재 원소를 앞쪽 정렬된 구간과 비교
3. 자기보다 큰 값들을 뒤로 한 칸씩 이동
4. 알맞은 자리에 삽입

3. C# 예제 코드 (새로운 예제)

void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; 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;
    }
}

4. 시간/공간 복잡도

• 공간 복잡도: O(1)

5. 특징

• 정렬이 거의 되어 있을수록 빠르다
• 안정 정렬 (같은 값의 순서가 유지됨)
• 코드 구조가 단순하고 직관적이어서 초보자에게 추천
• 데이터가 많을 경우에는 성능이 떨어진다

6. 예시

[4, 2, 5, 1]
→ 2 삽입 → [2, 4, 5, 1]
→ 5 삽입 → [2, 4, 5, 1]
→ 1 삽입 → [1, 2, 4, 5]

🔀 정렬 알고리즘 – 선택, 삽입, 퀵, 병합 정렬 비교

1. 정렬 알고리즘이란?

정렬 알고리즘은 **주어진 데이터를 일정한 순서(예: 오름차순, 내림차순)**로 재배열하는 알고리즘이다.
알고리즘의 기본 중의 기본이며, 많은 고급 알고리즘(탐색, 최적화 등)의 기반이 되기 때문에 중요하다.

2. 대표 정렬 알고리즘 비교표

3. 선택 정렬 (Selection Sort)

📌 개념

• 매번 가장 작은(또는 큰) 값을 찾아서 앞쪽과 교환
• 모든 원소를 한 번씩 비교하며 정렬

🧪 C# 예제 (새로운 배열)

void SelectionSort(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }

        // Swap
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

⏱️ 복잡도

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)

✅ 특징

• 구조는 단순하지만 효율은 낮음
• 교환 횟수는 적음 (최대 n회)
• 데이터 양이 많으면 부적합

1. 개념 정리

⏱️ 시간 복잡도 (Time Complexity)

• 알고리즘이 실행되는 데 걸리는 연산 횟수를 입력 크기 n에 따라 수학적으로 표현한 것
• O(n), O(n²), O(log n)처럼 Big-O 표기법으로 나타냄
• 실제 시간(초)이 아닌, 비례적인 연산량이 기준

💾 공간 복잡도 (Space Complexity)

• 알고리즘이 사용하는 메모리 공간의 양을 입력 크기에 따라 표현한 것
• 변수, 배열, 재귀 호출 스택 등이 포함됨
• O(1), O(n), O(n²) 등으로 표현

2. 차이점 요약

3. 실전 예제 비교

🧪 예제 1: 단순 합 구하기

int Sum(int[] arr)
{
    int total = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        total += arr[i];
    }
    return total;
}

• 시간 복잡도: O(n) — 한 번 순회함
• 공간 복잡도: O(1) — 변수 total만 사용

🧪 예제 2: 새로운 배열로 제곱값 저장

int[] SquareElements(int[] arr)
{
    int[] result = new int[arr.Length];
    for (int i = 0; i < arr.Length; i++)
    {
        result[i] = arr[i] * arr[i];
    }
    return result;
}

• 시간 복잡도: O(n) — 배열 한 번 순회
• 공간 복잡도: O(n) — 새로운 배열 result 사용

🧪 예제 3: 재귀로 팩토리얼

int Factorial(int n)
{
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

• 시간 복잡도: O(n) — n번 재귀 호출
• 공간 복잡도: O(n) — 재귀 호출 스택이 n층

4. 어느 쪽을 더 중요하게 봐야 할까?

• 대부분 시간 복잡도가 더 중요하지만,
  메모리 제약이 있는 환경(임베디드, 모바일 등)에선 공간 복잡도도 중요하다.
• 두 복잡도를 트레이드오프할 수 있음
  예: 메모리를 더 써서 시간을 줄이는 경우 (캐싱, DP)

5. 마무리 요약

• 시간 복잡도는 "얼마나 오래 걸리는가", 공간 복잡도는 "얼마나 많은 메모리를 쓰는가"
• 알고리즘 문제 풀이에선 둘 다 고려하되, 문제의 제한 조건을 보고 판단해야 한다
• 항상 시간 < 메모리 또는 메모리 < 시간 중 무엇이 더 중요한지 판단하며 설계하자

📊 Big-O 표기법 완벽 정리 – 알고리즘 성능의 기준

1. Big-O란 무엇인가?

Big-O 표기법은 **알고리즘의 효율성(시간 또는 공간 사용량)**을 수학적으로 표현하는 방식이다.
입력의 크기 n에 따라 알고리즘이 얼마나 느려질 수 있는지를 나타내며, 주로 최악의 경우를 기준으로 분석한다.

2. 왜 Big-O가 중요한가?

• 성능이 나쁜 알고리즘은 입력이 커질수록 실행 시간이 폭발적으로 증가한다.
• 코딩 테스트, 알고리즘 문제 해결, 실제 서비스 구현 모두에서 필수 요소이다.
• 성능을 비교할 때 단순한 실행 시간이 아니라 입력 크기에 따른 성능 증가율이 핵심이다.

3. Big-O의 주요 종류와 특징

🚀 효율성 순서 (가장 효율적 → 가장 비효율적)

흠.. 어떤게 제일 효율적인지 궁금해서 한번 찾아봤다!

4. Big-O 분석 요령

① 상수 제거

• O(2n) → O(n)
• O(5n²) → O(n²)

② 최고 차수만 남기기

• O(n² + n) → O(n²)
• O(n³ + n² + 1) → O(n³)

③ 중첩 반복문 분석

• 바깥/안쪽 각각 순회 → O(n²)
• 세 겹 중첩 for문 → O(n³)

5. 새로운 실전 예제와 해설

🧪 예제 1: O(1)

int GetFirst(int[] arr)
{
    return arr[0];
}

• 입력 배열의 첫 번째 값을 가져오는 코드.
• 입력 크기와 관계없이 항상 1번 동작 → O(1)

🧪 예제 2: O(n)

int SumAll(int[] arr)
{
    int sum = 0;
    foreach (int num in arr)
    {
        sum += num;
    }
    return sum;
}

• 배열의 모든 값을 한 번씩 순회 → O(n)

🧪 예제 3: O(n²)

void PrintAllPairs(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        for (int j = 0; j < arr.Length; j++)
        {
            Console.WriteLine($"{arr[i]}, {arr[j]}");
        }
    }
}

• 이중 반복문으로 모든 쌍 출력 → O(n²)

6. 마무리 요약

• Big-O는 성능을 수치화한 언어다.
• “빠르다”는 말 대신 “O(n)”처럼 수학적으로 표현하자.
• 알고리즘을 설계할 때는 항상 "이 코드의 시간/공간 복잡도는?"을 습관처럼 따져보자.

🧙‍♂️ 텍스트 기반 RPG 게임 (Text RPG)

간단한 콘솔 기반의 텍스트 RPG 게임입니다.

2일간 집중 개발하여 기본적인 전투, 아이템, 레벨업, 저장/불러오기 등의 기능을 구현했습니다.

✨ 주요 기능

• 던전 탐험 및 전투 시스템
• 경험치 획득과 레벨업
• 상점에서 아이템 구매 및 장착
• 인벤토리 시스템
• 게임 저장 및 불러오기 기능
• 부활 기능

🛠️ 사용 기술

• C# Console Application – 기본 구조 및 흐름 제어
• 객체지향 프로그래밍 (OOP) – Player, Item, Inventory, Shop, BattleSystem 등 클래스를 나눠서 설계
• 파일 입출력 (File I/O) – 게임 저장 및 불러오기 구현
• 컬렉션 활용 – List, Dictionary<TKey, TValue> 등을 이용한 아이템 관리 및 인벤토리 구현
• LINQ – 아이템 검색, 조건 필터링 등에 활용
• 구조체(Struct) – 값 형식 데이터 관리
• 열거형(Enum) – 직업, 아이템 종류 등 의미 있는 상수 그룹 정의
• 예외 처리 (Exception Handling) – 잘못된 입력에 대한 방어 코드 작성
• 캡슐화 및 접근 제한자 활용 – 클래스 내부 데이터 보호 및 인터페이스 명확화
• 상속과 다형성 – 향후 몬스터나 아이템 클래스 확장 고려한 구조 설계 (일부 구현)

🕹️ 실행 방법

1. https://github.com/NextTheWAT/C-_TextRPGGame

   2. TextRPG 파일 - TextRPG.exe 프로그램 실행!

📁 저장 방식

• 플레이어 정보는 파일로 저장되며, 여러 슬롯 중 하나를 선택해 저장/불러오기 가능합니다.

📌 개발자 메모

• 개발 기간: 약 2일
• 구현하고 싶은 기능은 많았지만, 제한된 시간 안에 최대한 깔끔하게 구조화하고자 노력했습니다.

👤 개발자

• 이재은

맨날 유니티 개발만 하다가 C# 으로 콘솔 게임을 만들게 될 줄은 몰랐다 솔직히 텍스트로만 보이고 개발하다보니 좀 어려운 것도 있었지만 나의 기초를 다듬고 보완하는 시간이였다. 머리가 아팠지만 그럴수록 너무 재밌었고 어떻게 해야할지 감이왔었다. 하나하나 차근차근히 해보니 실행이 잘 될때의 쾌감이란.. 이래서 개발자 한다 ㅎㅎ..

🗓️ 오늘 하루 일정

✅ 오전

• 09:00 ~ 11:30 : 텍스트 RPG 기능 개발 (던전 기능 설계 및 레벨업 시스템 구상)
• 11:30 ~ 13:00 : C# 체크리스트 강의 Day 3 수강
  • 주제: 메서드
  • 주요 내용: 메서드 선언과 호출, 매개변수/반환값, 연산자 실습

🍽️ 점심시간

• 13:00 ~ 14:00 : 점심시간

✅ 오후

• 14:00 ~ 18:00 : 텍스트 RPG 기능 구현
  • 던전 시스템 완성 (난이도/보상/실패 확률 등)
  • 클리어 횟수 기반 레벨업 구현
  • 장착 아이템 능력치 반영 문제 해결
  • 저장/불러오기 시 능력치 정상 반영

🍽️ 저녁시간

• 18:00 ~ 19:00 : 저녁시간

✅ 저녁

• 19:00 ~ 20:30 : 오늘 작성한 코드 복습 및 구조 점검
• 20:30 ~ 21:00 : TIL 내용 정리 및 작성

✅ 오늘 학습 키워드

• 텍스트 RPG 던전 시스템 구현
• 레벨업 시스템 설계 및 구현
• 난이도에 따른 전투 결과 처리
• 경험치 계산 및 능력치 반영
• 아이템 능력치 저장/불러오기 버그 수정
• C# 메서드 선언과 호출
• 매개변수와 반환값
• 산술/관계/논리 연산자 실습
• 코드 구조 복습 및 정리

✅ 오늘 학습 한 내용을 나만의 언어로 정리하기

오늘은 텍스트 RPG의 핵심 기능인 던전 시스템과 레벨업 로직을 본격적으로 구현했다. 난이도에 따라 전투 결과가 달라지고, 클리어 여부에 따라 경험치와 보상을 획득할 수 있도록 설계했다.

레벨업 시스템을 만들었고, 능력치도 구현했다.

저장/불러오기 기능에서도 중요한 이슈가 하나 있었는데, 장착한 아이템의 능력치가 불러오기 후 반영되지 않는 문제였다. 꽤 골치 아픈 버그였지만, 결국 장비 장착 로직과 플레이어 능력치 반영 구조를 다시 살펴보며 해결할 수 있었다. 버그가 사라지는 순간, 굉장히 굉장히.. 뿌듯했다.

오전 강의에서는 메서드의 기본 구조와 개념을 다시 짚었고, 실습 문제를 통해 다양한 연산자를 복습했다. 실제 게임 시스템 안에서 메서드를 설계하고 나니 얼마나 중요한 기초인지 느낄 수 있었다.

저녁 시간에는 오늘 만든 코드를 차분히 복습하면서 구조적으로 더 깔끔하게 만들 수 있는 방법도 고민했다. 하루가 끝날 땐, 나의 실력이 1레벨 올라간 기분이었다. 😊

🧩 학습하며 겪었던 문제점 & 에러

1. 저장 후 불러올 때 장착 아이템 능력치가 반영되지 않음

• 문제정의
• 아이템을 장착한 상태로 저장하고 나서 불러오면, 장비는 잘 표시되는데 능력치(공격력/방어력)에 반영되지 않는 문제가 발생함.
• 시도한 방법
  • LoadPlayer()에서 장착 상태만 복원하고, 능력치 재계산을 따로 하지 않은 상태였음.
  • 처음엔 장비가 잘 불러와졌기에 기능상 문제 없다고 착각했음.
• 해결 방법 (코드 포함)
• 장착 아이템의 능력치를 적용하는 메서드를 새로 만들어, 불러온 후 적용하도록 수정함.

public void LoadPlayer()
{
    // 저장된 값 로드
    player.Level = data.Level;
    player.Exp = data.Exp;
    // ...

    // 장비 복원
    foreach (var item in data.EquippedItems)
    {
        player.EquipItem(item); // 착용만 했고 능력치 반영이 안 됐었음
    }

    // ✅ 능력치 반영 추가
    player.ApplyEquippedStats();
}

// 새로 만든 메서드
public void ApplyEquippedStats()
{
    BaseAttack = originalBaseAttack;
    BaseDefense = originalBaseDefense;

    foreach (var item in EquippedItems)
    {
        BaseAttack += item.Attack;
        BaseDefense += item.Defense;
    }
}

• 새롭게 알게 된 점
• "장착"이라는 상태만 저장하는 것이 아니라, 그 상태가 게임 시스템에 어떤 영향을 주는지까지 고려한 로직이 필요하다는 걸 알게됨.
• 다시 만나게 된다면
• 불러온 데이터가 정상 동작하는지 확인할 때 단순히 UI만 보지 말고 값이 정확히 적용되는지 출력해보는 습관을 들이자.

2. 장비 장착 상태에서는 정상인데 +능력치만 사라진 현상

• 문제정의
• 저장된 캐릭터를 불러오면 장비창과 인벤토리엔 아이템이 정상적으로 표시되지만, 플레이어 능력치에 +Attack, +Defense 보정치가 반영되지 않음.
• 시도한 방법
• 장비가 눈에 보이는 걸로 착용 완료라고 생각했지만, 능력치 수치가 기본값으로만 출력되었고, 로그 찍어보며 확인.
• 해결 방법 (코드 포함)
• EquipItem()과 LoadPlayer() 호출 흐름을 점검하여, 장착 상태를 적용한 직후 능력치를 반영하도록 수정함.

public void EquipItem(Item item)
{
    if (!EquippedItems.Contains(item))
        EquippedItems.Add(item);

    // 능력치 반영
    BaseAttack += item.Attack;
    BaseDefense += item.Defense;
}

또는 LoadPlayer()에서 일괄 계산하는 방식으로 ApplyEquippedStats()처럼 구성함.

• 새롭게 알게 된 점
• 장비 시스템은 UI와 데이터, 기능(능력치 반영)이 완전히 분리되어 있으면 버그가 생기기 쉽다는 걸 느낌.
• 다시 만나게 된다면
• 장비 착용 → 능력치 반영 → 화면 출력까지의 흐름을 항상 하나의 덩어리로 인식하자.

📝 메모

오늘은 하루 종일 텍스트 RPG의 구조를 다지고 기능을 쌓아가는 데 집중했다. 특히 던전과 레벨업 시스템을 직접 설계하고 구현하면서, 내가 지금 배우고 있는 C#과 게임 개발 지식들이 하나로 연결되는 느낌이 들었다.

하나하나 해결해나가면서 느낀 점은 처음엔 복잡해 보이던 문제들도 디버깅하고 출력해보며 하나씩 분석하니 결국 실마리가 풀렸다. 그럴때의 쾌감은 이루 말할 수 없다..ㅎㅎ 이래서 개발자 한다고 생각한다!

무엇보다 오늘은 "장비 능력치가 반영되지 않는 문제"를 해결하면서 꽤 큰 성취감을 느꼈다. 단순히 코드가 돌아가는 걸 넘어서, 게임 시스템 전체의 흐름을 고민하게 되었고, 그게 바로 개발자다운 성장이라는 생각이 들었다.

코드를 복습하며 내가 만든 로직을 스스로 설명할 수 있게 되니까 조금은 더 자신감도 생겼다.

하루를 마무리하며, 오늘도 잘 해냈다 하루하루 화이팅!!!