C# 강의 5주차

오늘의 키워드 : 알고리즘 기초

빅오 표기법 계산

• 상수 버리기
  예를 들어 O(2n), O(3n^2)같은 경우 O(n), O(n^2)로 간소화할 수 있다.
• 최고 차수 항목만 남기기
  예를 들어 O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있다.
• 연산자 상수 무시
  예를 들어 O(4n^2 + 2n + 1)의 경우 O(n^2)로 간소화할 수 있다.

시간 복잡도

  시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도이다. 코드의 실행 시간을 실제 시간으로 측정하는 것이 아니라 연산 횟수로 측정한다.
예시1)

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

for루프가 0부터 n까지 순회하며 계산하므로 n회의 연산이 필요하다. 시간 복잡도 : O(n)

예시2)

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

두 개의 중첩된 for루프를 포함하고 있다. 전체 연산 횟수는 n^2이다. 시간 복잡도 : O(n^2)

공간 복잡도

  공간 복잡도란 코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 말한다.
예시1)

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

arr는 외부에서 받은 것이므로 공간 복잡도를 계산하지 않는다. 내부에서 추가로 사용하는 변수는 int total하나이고 입력 크기와 관계없이 항상 일정한 공간만 사용한다. 공간 복잡도 : O(1)

✅ 위 예제를 보고 변수 여러개면 공간 복잡도가 증가하나? 라는 궁금증이 생겼지만 그건 아니다! 변수가 100개여도 고정된 수이므로 공간 복잡도는 여전히 O(1)일 것이다. 공간 복잡도는 입력 크기에 따라 메모리가 얼마나 증가하느냐가 기준이기 때문.

예시2)

int[] CopyArray(int[] arr)
{
    int[] result = new int[arr.Length];  // n개 크기만큼 새 공간
    for (int i = 0; i < arr.Length; i++)
    {
        result[i] = arr[i];
    }
    return result;
}

입력 배열 arr은 길이가 n이다. result라는 새 배열을 동일한 크기로 생성했다. 예를 들어 arr.Length == 5라면 → result도 5칸짜리가 되고 arr.Length == 1000라면 → result도 1000칸짜리가된다. 즉 n만큼 새 메모리를 사용하므로 공간 복잡도 : O(n)

정렬 알고리즘

  정렬 알고리즘은 주어진 데이터 세트를 특정 순서(오름차순, 내림차순, 문자열의 사전식 순서 등)로 배열하는 방법을 제공한다.

정렬 알고리즘	평균 시간 복잡도	최악 시간 복잡도	정렬 방식	특징
선택 정렬	O(n²)	O(n²)	비교 기반, 제자리 정렬	가장 작은 값을 찾아 앞에 위치시킴
삽입 정렬	O(n²)	O(n²)	비교 기반, 제자리 정렬	거의 정렬된 데이터에 매우 효율적
퀵 정렬	O(n log n)	O(n²)	분할 정복	평균적으로 매우 빠름, 불안정 정렬
병합 정렬	O(n log n)	O(n log n)	분할 정복	안정 정렬, 배열을 계속 반으로 쪼갬

탐색 알고리즘

  탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공한다.

알고리즘	시간 복잡도	구조	설명
선형 탐색 (Linear Search)	O(n)	배열, 리스트 등	처음부터 하나씩 비교하며 탐색
이진 탐색 (Binary Search)	O(log n)	정렬된 배열	중간값을 기준으로 반씩 나누며 탐색
DFS (깊이 우선 탐색)	O(V + E)	그래프, 트리	한 노드를 깊게 탐색한 후 다음 노드로 이동
BFS (너비 우선 탐색)	O(V + E)	그래프, 트리	가까운 노드부터 넓게 탐색 (큐 사용)

※ V: 노드 수, E: 간선 수

알고리즘	설명
Dijkstra	모든 간선의 가중치가 양수일 때 사용하는 최단 경로 알고리즘. 가장 가까운 노드부터 탐색하며 거리를 갱신함.
Bellman-Ford	음의 가중치가 있는 그래프도 탐색 가능한 알고리즘. 모든 간선을 최대 V-1번 반복해 최단 거리 계산.
A-star	특정 목적지까지 최단 경로를 찾는 알고리즘. 휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택해 탐색

마무리하며

  예전부터 알고리즘이 중요하다... 알고리즘을 열심히 공부해야 한다...라는 말을 많이 들었었는데 정말이었다. 코딩테스트 실전 문제를 봤는데 세상에 어떤 상황을 어떤 알고리즘으로 풀어봐라 이런 문제가 있었다. 이건 확실히 그 알고리즘에 대해 잘 알아야 풀 수 있는 문제 같았고 지금 내 실력으로는 도저히 무리같았다.... 하지만 앞으로 계속 알고리즘 공부를 열심히 하면 나도 풀 수 있는 날이 오지 않을까? 언젠가 내 벨로그에 '어려운 알고리즘 문제 풀이'라는 이름으로 글이 올라올지도 모른다!

내일 할 일

  과제 제출까지 얼마 안남은 시간... 정말로 시작할 때가 온 것이다! 마침 강의도 다 들었으니 내일은 하루동안 과제를 열심히 해볼까 한다.