📅 지난 일주일 동안 가장 인상 깊었던 배움은?

이번 주 가장 인상 깊었던 배움은 텍스트 기반 RPG 프로젝트를 직접 설계하고 구현한 경험이었다.

단순히 기능을 만들기보다, 상호작용하는 시스템을 어떻게 구조화할 것인지에 대한 고민이 깊었던 한 주였다.
예를 들어, Item 클래스를 중심으로 상점, 인벤토리, 장착 시스템, 저장/불러오기 기능까지 유기적으로 연결하며, 자연스럽게 클래스 간의 책임 분리와 데이터 공유 방식에 대해 고민하게 되었다.

또한, Item.Items라는 정적 리스트를 활용하여 아이템 정보를 한곳에서 관리하고, 아이템의 구매 상태(가격 0원 처리), 능력치 반영 방식, 저장 시의 데이터 유지 등 실제 게임 시스템을 구현하며 생기는 수많은 예외 상황들을 마주했다. 이 과정에서 값 형식/참조 형식, 깊은 복사와 얕은 복사, 메모리 흐름 등 이론적으로 배웠던 개념들이 실전에서 어떻게 작동하는지를 몸으로 익힐 수 있었다.

특히, 던전 시스템과 레벨업 구조 설계는 알고리즘적 사고까지 동반되어 더욱 인상 깊었다. 클리어 횟수에 따라 레벨이 오르고, 난이도에 따른 실패 확률과 보상 계산을 직접 수식으로 구현하면서, 단순한 조건문이 아닌 논리적인 흐름을 갖는 시스템을 어떻게 설계해야 하는지 큰 통찰을 얻었다.

이번 주는 말 그대로 "하나의 게임 시스템을 내가 직접 완성해보았다"는 확신을 얻은 시간이었다.
그 과정에서 기능을 나열하는 개발자에서, 구조를 고민하는 개발자로 조금씩 변해가는 나를 느낄 수 있었던 것이 가장 큰 배움이었다.

❗배움까지 다가가는데 어떤 어려움이 있었지?

이번 주는 정말 배움이 많았던 만큼, 그 배움에 도달하기까지의 어려움도 적지 않았다.
가장 큰 어려움은 복잡한 시스템을 어떻게 나누고 연결할지를 감 잡는 것이었다.

예를 들어, Item 클래스 하나로 상점과 인벤토리, 플레이어 장비를 동시에 관리하고 싶었는데, 정작 기능을 만들다 보니 어디서 무엇을 참조하고 수정해야 하는지가 자꾸 꼬였다.
처음에는 Item 리스트를 각각 따로 두었고, 구매한 아이템과 장착한 아이템을 서로 연동하지 못해 데이터 일관성이 무너지는 문제가 발생했다.

또한, 저장과 불러오기 기능을 구현할 때는 장착한 장비의 능력치가 적용되지 않거나 사라지는 현상이 발생해서 한참을 디버깅해야 했다.
장비가 저장은 되었지만, 다시 불러오면 플레이어 능력치에 반영이 되지 않는 이유를 찾느라 LoadPlayer() 함수의 구조를 여러 번 뜯어고치기도 했다.

무엇보다 어려웠던 건, 문제의 원인이 단순히 “코드가 틀렸다”가 아니라 설계 구조가 잘못되어 생기는 문제라는 사실이었다.
기존의 습관대로 빠르게 기능을 붙이기만 하면 오히려 나중에 수정이 불가능한 코드가 된다는 걸 뼈저리게 느꼈다.

하지만 그런 어려움 덕분에, "애초에 어떻게 설계할지를 더 먼저 고민해야 한다"는 교훈을 얻게 되었고, 클래스 간의 역할 분리와 데이터 흐름에 대한 감각을 조금씩 익힐 수 있었다.

💡과정에서 나는 무엇을 깨달았고, 어떤 감정/생각이 들었었지?

이번 주 과정을 통해 내가 가장 크게 깨달은 건, ‘몰랐던 게 아니라, 모르는 줄도 몰랐던 것들이 많았구나’ 하는 사실이었다.
처음엔 구조체와 클래스의 차이를 안다고 생각했고, 저장과 불러오기 기능도 단순히 파일만 다루면 될 줄 알았다. 하지만 실제로 하나하나 구현해보니, 값이 어디 저장되고, 어떻게 참조되며, 어떤 흐름으로 게임 내 시스템에 영향을 주는지 전혀 감이 없었다는 걸 깨달았다.

한참 동안 디버깅하면서 "왜 저장은 됐는데 장착 효과는 안 살아나지?"라는 단순한 문제에 몇 시간씩 매달리기도 했고, Item.Items 리스트의 정적 구조가 시스템 전반에 어떤 영향을 주는지 몸으로 부딪히며 익혀야 했다.

그 과정은 답답하고 벽에 부딪히는 느낌이 들기도 했지만, 동시에 하나씩 해결해나가면서
‘내가 진짜 조금씩 개발자에 가까워지고 있구나’ 하는 벅찬 감정도 함께였다!!

특히 저장한 데이터를 불러오면서 플레이어 능력치에 장비 효과까지 정확히 반영되었을 때, 스스로에게 “와, 내가 이걸 해냈네”라는 말을 하게 됐다.
그 순간이 이번 주 가장 뿌듯했던 기억으로 남았다.

나는 여전히 부족하지만, 부딪히고 고치고, 다시 해보는 과정 속에서 진짜 실력이 쌓이는 거구나 하는 걸 이 한 주 동안 온몸으로 느꼈다.

✍️ 메모

• 기능 하나를 만들기 전에 데이터가 어떻게 흐르고, 어디에 저장되며, 어떤 객체가 책임을 가져야 하는지 먼저 생각하자.
• 저장/불러오기 기능은 단순한 파일 저장이 아니라, 객체의 상태를 어떻게 재구성할 것인가에 대한 문제임을 알게 되었다.
• 정적 리스트나 참조 형식을 사용할 땐, 공유되는 데이터의 생명 주기와 영향 범위를 명확히 파악해야 한다.
• Item.Items, Player, Inventory, Shop 간의 관계를 설계하면서 실제 게임 시스템의 기반 구조에 대한 감각이 생기기 시작했다.
• 설계를 수정하는 데 시간이 걸리더라도, 올바른 방향을 잡고 나면 유지보수나 디버깅 시간이 훨씬 줄어든다는 걸 체감했다.
• 내가 모르는 걸 부끄러워하지 않고, 차분히 파고드는 습관을 계속 이어가자.

🌿 WIL - 시스템을 이해하는 힘, 그리고 성장

이번 주는 단순히 기능을 구현하는 한 주가 아니었다.
텍스트 기반 RPG 프로젝트를 만들며 처음으로 내가 직접 전체 구조를 설계하고 연결해나가는 경험을 했다.
상점, 인벤토리, 장착 시스템, 저장과 불러오기까지… 모든 요소가 Item 클래스를 중심으로 엮여 있었고, 그만큼 설계 하나가 시스템 전체에 미치는 영향도 컸다.

하지만 이 모든 걸 이해하게 되기까지는 쉽지 않은 시간들이 있었다.
저장은 되지만 장비 효과가 반영되지 않는 문제, 같은 데이터를 서로 다른 객체에서 참조할 때 발생하는 혼란, 능력치가 사라지는 원인을 찾기 위한 수많은 디버깅...
그 과정에서 나는 단순히 문법을 아는 것과 시스템을 이해하는 것의 차이를 뼈저리게 느꼈다.

그럼에도 불구하고 하나하나 부딪히며 고쳐나갔고, 마침내 내가 만든 시스템이 제대로 작동하는 걸 눈으로 확인했을 때
"아, 나 진짜 해냈다"는 생각이 들며 뿌듯함과 자부심이 함께 밀려왔다.
'모르는 걸 부끄러워하지 않고 끝까지 파고들면 반드시 얻을 수 있다'는 믿음이 생겼다.

이제 나는 기능을 나열하는 개발자가 아니라, 구조를 고민하고 흐름을 설계할 줄 아는 개발자가 되고 싶다.
그리고 그 출발점에 이번 주가 있다는 사실이 참 고맙고 소중하게 느껴진다.

🌱 앞으로도 하나씩 차분하게, 천천히, 그러나 확실하게 나아가자!!!!!!

📅 이번 주 TIL 목록

📅 이번 주 Study 목록

🗓️ 2025년 7월 11일 (금) 오늘 하루 일정

✅ 오전

• 09:00 ~ 11:30
  • 알고리즘 기초 개념 학습
    • 시간 복잡도 vs 공간 복잡도
    • 정렬 알고리즘 개요 및 종류
    • 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬, 병합 정렬 정리
    • 탐색 알고리즘 개요 및 DFS, BFS, 이진 탐색 정리
    • 최단 경로 알고리즘: 다익스트라, 벨만-포드
• 11:30 ~ 13:00
  • C# 체크리스트 강의 Day.4 수강 (반복문 주제)

🍽️ 점심시간

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

✅ 오후

• 14:00 ~ 18:00
  • 오전에 학습한 알고리즘 전체 복습
  • 문제 풀이: Histogram에서 최대 직사각형 (LeetCode 84)
    • ToList(), Stack 사용 방식, while 조건 이해
  • 문제 풀이: Flood Fill (LeetCode 733)
    • DFS를 이용한 그림 색칠 방식 이해
  • 문제 풀이: Longest Increasing Subsequence (LeetCode 300)

🍽️ 저녁시간

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

✅ 저녁

• 19:00 ~ 20:30
  • 정렬 알고리즘 & 탐색 알고리즘 복습
    • 삽입 정렬 while문의 역할
    • List와 배열, 제네릭 타입 관련 개념 정리

✅ 오늘 학습 키워드

• 시간 복잡도 / 공간 복잡도
• 기초 정렬 알고리즘
  • 선택 정렬
  • 삽입 정렬
  • 버블 정렬
• 고급 정렬 알고리즘
  • 퀵 정렬
  • 병합 정렬
• 탐색 알고리즘
  • 선형 탐색
  • 이진 탐색
  • DFS / BFS
• 최단 경로 알고리즘
  • 다익스트라
  • 벨만-포드
• C# 리스트 구조 이해
  • List<int> vs List<int>[]
  • List<(int, int)> 구조
• 문제 풀이 실습
  • 84번: Histogram에서 가장 큰 직사각형
  • 733번: Flood Fill
  • 300번: 최장 증가 부분 수열 (LIS)

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

오늘은 알고리즘 공부에 집중했다.

우선 시간 복잡도와 공간 복잡도의 개념부터 다시 정리했는데,

코드가 얼마나 오래 걸릴지, 얼마나 많은 메모리를 차지하는지를

Big-O 표기로 표현한다는 점을 다시 되짚었다.

그다음은 정렬 알고리즘들을 살펴봤다.

• 선택 정렬은 제일 작은 값을 찾아서 앞으로 보내는 방식이었고,
• 삽입 정렬은 앞에서부터 정렬된 상태를 유지하면서 새 값을 알맞은 위치에 "삽입"하는 구조였다.한 칸씩 왼쪽으로 이동하며 비교하기 위해서였다.
• 삽입 정렬의 while문 안에서 j-- 하는 이유도 알 수 있었다.

버블 정렬은 인접한 요소끼리 계속 비교해서 가장 큰 값을 뒤로 보내는 단순한 구조였고,

퀵 정렬과 병합 정렬은 분할 정복 기법을 활용해 효율적으로 정렬하는 고급 정렬 방식이었다.

정렬만큼 중요한 게 탐색이었다.

선형 탐색은 단순히 앞에서부터 찾는 방식,

이진 탐색은 정렬된 배열을 반으로 나누며 탐색하는 방식이었다.

또, DFS와 BFS는 그래프 탐색에서 자주 쓰이는 기본 알고리즘으로,

DFS는 깊이 우선, BFS는 너비 우선이라는 차이를 가졌다.

최단 경로 알고리즘도 정리했는데,

다익스트라는 우선순위 큐와 거리 배열을 활용해서 가장 짧은 경로를 찾고,

벨만-포드는 음수 간선이 있을 때도 사용할 수 있지만 시간이 오래 걸리는 알고리즘이었다.

문제 풀이도 여러 개 해봤다.

• 84번 히스토그램 문제에서는 스택을 이용해 최대 직사각형 넓이를 구했고,
• 733번 Flood Fill 문제는 DFS를 활용해서 같은 색 영역을 바꾸는 문제였다.
• 300번 LIS 문제에서는 DP를 활용해 가장 긴 증가 수열의 길이를 찾았다.

마지막으로 C#의 제네릭 컬렉션도 다시 정리했다.

List<int>는 단순 리스트고, List<int>[]는 리스트 배열,

List<(int, int)>은 튜플로 좌표나 쌍을 저장할 때 유용하다는 걸 배웠다.

사실 모든걸 이해하지는 못했지만 반복학습이 답일듯 싶다. 배울때 많이 배우고 복습 열심히하자!

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

1. 문제정의: 삽입 정렬에서 j--의 동작이 직관적으로 이해되지 않았음

💻 관련 코드 예시:

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;
}

• 시도:
• j--가 어떤 역할을 하는지 흐름을 직접 손코딩하며 추적함
• 해결방법:
• 정렬된 구간 안에서 값을 비교하면서 왼쪽으로 한 칸씩 이동한다는 구조를 시각화함
• 새롭게 알게 된 점:
• j--는 값을 한 칸 왼쪽으로 이동하면서 앞쪽 값과 계속 비교하기 위한 인덱스 조절임
• 다시 만나게 된다면:
• 반복문에서 인덱스 흐름이 복잡할 땐 직접 배열 상태를 표로 그려보며 흐름을 따라가자. 사실 내가 순간적으로 이해하지 못했었다.. 다시 천천히 보니 이해 확실!

2. 문제정의: 2차원 배열의 특정 값을 변수로 복사할 때 참조와 복사의 차이를 헷갈렸음

💻 관련 코드 예시:

int[,] image = {
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 1}
};

int sr = 0, sc = 0;
int originalColor = image[sr, sc];  // ❗ 이 값이 원본과 어떻게 연결되는지 헷갈림

• 시도:
• originalColor를 수정해도 원본 배열이 바뀌는지 실험해봄
• 해결방법:
• int는 값 형식이라 복사되는 값이며, 배열의 참조가 아님을 확인
• 새롭게 알게 된 점:
• originalColor는 image 내부의 값을 복사한 독립된 값이므로 이후 원본과는 무관함
• 다시 만나게 된다면:
• 값 형식인지 참조 형식인지부터 먼저 따지고, 복사인지 연결인지를 구분하자

3. 문제정의: Longest Increasing Subsequence 문제 풀이에서 while문 흐름이 어려웠음

💻 관련 코드 예시:

List<int> dp = new List<int>();
foreach (int num in nums)
{
    int left = 0, right = dp.Count;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (dp[mid] < num)
            left = mid + 1;
        else
            right = mid;
    }

    if (left == dp.Count)
        dp.Add(num);
    else
        dp[left] = num;
}

• 시도:
• while문 조건과 이진 탐색 흐름이 감이 안 와서 각 변수 변화 과정을 출력해봄
• 해결방법:
• 람다식, 컬렉션 등을 하나씩 분해해서 단계별로 해석하고, dp 리스트의 변화 과정을 직접 따라감
• 새롭게 알게 된 점:dp는 증가 수열을 시뮬레이션하는 용도임
• 이 방식은 실제 LIS를 구하는 게 아니라 길이와 패턴만 유지하는 방식이며,
• 다시 만나게 된다면:
• 복잡한 알고리즘일수록 흐름을 그대로 받아들이기보다, 데이터 변화 흐름을 눈으로 확인하는 게 중요함

📝 메모

오늘은 정말 많은 알고리즘들을 배우고 복습한 하루였다. 처음엔 삽입 정렬이나 LIS 문제처럼 익숙하지 않은 로직 앞에서 살짝 멍해졌지만, 그럴수록 흐름을 따라가고 손으로 써보면서 하나씩 내 걸로 만들었다. 특히 “왜 이 코드가 이렇게 작동하지?”라는 질문을 놓지 않았던 게 결국 이해로 이어졌다는 걸 느꼈다.

“모르는 걸 부끄러워하지 말고, 이해하려는 과정을 포기하지 말자.” 오늘도 이 말이 딱 내 하루였다.

혼란스러웠던 코드들을 곱씹고 정리하는 이 시간이 내 실력을 한 단계 올려주는 귀한 과정이라는 걸 잊지 말자. 오늘보다 조금 더 성장한 나로 다시 공부 시작하면 된다!!!오예!! 😊

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 다익스트라의 선택이 중요함 (가중치 유무)

🌐 그래프 탐색 알고리즘 – DFS vs BFS

1. 그래프 탐색이란?

그래프 탐색 알고리즘은 노드와 간선으로 이루어진 구조에서 특정 노드까지 도달하거나 모든 노드를 방문하는 알고리즘이다.
대표적으로 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있다.

2. DFS (깊이 우선 탐색)

📌 개념

• 가장 깊은 노드까지 계속 들어갔다가, 막히면 다시 돌아오는(backtrack) 방식
• 스택 구조 기반 (재귀 or 직접 스택 사용 가능)

✅ 예시 코드 (C# – 재귀 사용)

void DFS(int node, bool[] visited, List<int>[] graph)
{
    visited[node] = true;
    Console.Write($"{node} ");

    foreach (int neighbor in graph[node])
    {
        if (!visited[neighbor])
            DFS(neighbor, visited, graph);
    }
}

3. BFS (너비 우선 탐색)

📌 개념

• 가까운 노드부터 차례로 탐색, 점점 퍼져 나가는 방식
• 큐(Queue) 구조 기반

✅ 예시 코드 (C#)

void BFS(int start, bool[] visited, List<int>[] graph)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(start);
    visited[start] = true;

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.Write($"{node} ");

        foreach (int neighbor in graph[node])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                queue.Enqueue(neighbor);
            }
        }
    }
}

4. DFS vs BFS 비교

5. 활용 예시

• DFS: 미로 찾기, 순열/조합, 백트래킹 문제
• BFS: 최단 거리, 최소 이동 횟수, 퍼지는 방식 (불 퍼짐, 바이러스 등)

6. 마무리 요약

• DFS는 재귀적, 깊이 있는 문제 해결에 적합
• BFS는 큐 기반, 최단 거리 탐색에 적합
• 그래프 탐색 문제는 대부분 이 두 알고리즘으로 해결 가능
• 실제 문제에서는 종종 양쪽 모두 시도해봐야 정답이 나올 때도 있음

🔍 탐색 알고리즘 정리 – 선형 탐색 vs 이진 탐색

1. 탐색 알고리즘이란?

탐색 알고리즘은 주어진 데이터에서 원하는 값을 찾는 알고리즘이다.
정렬된 데이터든 아니든, 가장 기본이 되는 핵심 알고리즘으로 코딩 테스트에서도 자주 등장한다.

2. 선형 탐색 (Linear Search)

📌 개념

• 데이터를 처음부터 끝까지 순차적으로 탐색하며 값을 찾는 방식
• 배열이 정렬되지 않아도 사용 가능

✅ 예시 코드 (C#)

int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

⏱️ 시간 복잡도

• 최악/평균: O(n)
• 공간 복잡도: O(1)

💡 특징

• 구현이 매우 단순
• 정렬되지 않은 데이터에서도 작동 가능
• 데이터가 작을 때 적합

3. 이진 탐색 (Binary Search)

📌 개념

• 정렬된 배열을 전제로, 중간값과 비교하며 탐색 범위를 절반씩 줄여가는 탐색
• 훨씬 빠르지만 반드시 정렬되어 있어야 함

✅ 예시 코드 (C#)

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

⏱️ 시간 복잡도

• 최악/평균: O(log n)
• 공간 복잡도: O(1)

💡 특징

• 정렬된 배열에서만 사용 가능
• 데이터가 많을수록 성능 차이가 극명함
• 코딩 테스트에서도 자주 등장

4. 비교 요약

5. 선택 가이드

• 정렬되지 않은 배열 → 선형 탐색
• 정렬된 배열이고 데이터가 많음 → 이진 탐색
• 이진 탐색은 C#에서 Array.BinarySearch()로도 지원됨

🏁 마무리 요약

• 탐색은 모든 알고리즘 문제의 기초가 되는 개념
• 이진 탐색을 잘 활용하면 탐색 문제 → log n으로 시간 절약 가능
• 나중에 다룰 DFS, BFS, 다익스트라 등의 고급 탐색 알고리즘의 기반이 되므로 꼭 숙지할 것!