📚 TIL - 2025년 4월 17일 (목) / 알고리즘 기초 정리

🔹 01. 알고리즘 기초

🔸 알고리즘이란?

• 데이터를 처리하기 위한 정확하고 일관된 절차나 과정
• 구성 요소: 입력 → 처리 → 출력
• 단순히 결과만 보는 것이 아니라, 결과를 만들어내는 '절차' 자체가 중요함

🔸 알고리즘의 필요성

• 하나의 문제를 해결하는 다양한 방법들을 비교하고 평가할 때 필요
• 같은 기능을 수행하는 여러 알고리즘 중 어떤 방식이 더 효율적인지를 분석할 수 있음

---

🔹 02. Big-O 표기법

🔸 어디에 도움이 될까?

• 입력의 크기(N)가 증가할 때 알고리즘의 처리 시간이나 메모리 사용량이 어떻게 변하는지 예측 가능
• 성능을 수치적으로 표현할 수 있어 알고리즘을 평가하고 비교하는 기준이 됨

🔸 대표적인 예시

• O(1): 상수 시간 – 입력 크기에 상관없이 일정한 시간
• O(n): 선형 시간 – 입력 크기에 비례해 증가
• O(n^2): 이차 시간 – 이중 반복문이 대표적
• O(log n): 로그 시간 – 이진 탐색 등에서 사용됨

---

🔹 03. 시간 & 공간 복잡도

🔸 시간 복잡도

int Sum(int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += i;
    }
    return sum;
} // O(n)

0부터 n까지 더하는 반복문. 입력 크기만큼 반복되므로 O(n)

void PrintPairs(int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            Console.WriteLine(i + ", " + j);
        }
    }
} // O(n^2)

이중 반복문. 각 루프가 n번 수행되어 총 n^2번 실행됨

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
} // O(2^n)

재귀적으로 두 번씩 분기되는 구조. 입력이 커질수록 지수적으로 증가함

🔸 공간 복잡도

int FindMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.Length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
} // O(n) 시간 / O(1) 공간

배열을 한 번 순회하면서 최대값을 찾음. 별도 공간이 필요 없으므로 O(1)

---

🔹 04. 실제 문제에서 복잡도 분석

// 문제 1: 특정 숫자 검색
public static bool FindNumber(int[] array, int target) {
    for (int i = 0; i < array.Length; i++) {
        if (array[i] == target) return true;
    }
    return false;
} // O(n) 시간, O(1) 공간

// 문제 2: 최대값 찾기
public static int FindMax(int[] array) {
    int max = int.MinValue;
    for (int i = 0; i < array.Length; i++) {
        if (array[i] > max) max = array[i];
    }
    return max;
} // O(n) 시간, O(1) 공간

// 문제 3: 중복 제거
public static int[] RemoveDuplicates(int[] array) {
    List<int> distinctList = new List<int>();
    foreach (int num in array) {
        if (!distinctList.Contains(num)) {
            distinctList.Add(num);
        }
    }
    return distinctList.ToArray();
} // O(n^2) 시간 (Contains 사용 시), O(n) 공간

---

📚 후기

유니티가 벌써 그립다... 그땐 뭐든 알아서 해줬는데... 지금은 하나하나 다 이해하고 정리하고 써야 하니까, 쉽진 않지만 그래도 이제는 '읽을 줄은 알게 되는' 단계까지는 온 것 같음.

그냥 대충 넘겼던 for문이나 배열 순회 같은 것도, 이제는 얼마나 시간이 걸릴지 대충 감이 잡히니까 좀 다르게 보임.

다만, 아무리 이해가 된다 해도 막상 '이제 직접 만들어 보세요!' 하면 손이 멈춘다. 백지 위에 올려놓으라고 하면 뭐부터 어떻게 해야 할지 아직은 막막하다.

그래도 적어도 다음 주 시험 전에 1주차 4주차 반복하면서 개념만큼은 제대로 복습해두자. 우리는 물론 유니티로 게임을 만들겠지만, 알고리즘은 그 게임의 '속도'와 '구조'를 뒷받침해주는 바닥 체력 같은 거니까.