늘 헷갈리는 알고리즘 정리
이번 포스트에서는 2주차 마지막 강의에 있는 개념들을 정리해보는 시간을 가질 것이다.
오늘은 진짜 쓸 내용이 많을 것이다... 항상 보는 내용인데 항상 볼 때 마다 새롭고 짜릿하기 때문이다..
크게 6가지 정도의 목차를 나눌 것인데
- 복잡도
- 정렬 알고리즘
- 탐색 알고리즘
- BFS, DFS
- 최단 경로 알고리즘
- 잡 스케쥴러
그렇다. 지겹도록 들었던 내용들인데 지겹도록 까먹는 나다.
이제는 진짜 까먹지 않도록 심혈을 다해서 써보겠다.
- 알고리즘
- 문제를 해결하기 위한 단계적인 방법
- 개념
- 입력을 받아 원하는 출력을 생성하기 위한 절차
- 입력, 출력, 명확한 단계, 실행 가능성의 특성을 갖습니다.
- 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 한다.
- 컴퓨터 프로그래밍뿐만 아니라 다양한 분야에서 사용된다.
- 같은 문제를 해결하는 두 알고리즘이 있다면, 효율적인 알고리즘은 더 적은 컴퓨팅 자원을 사용하기 때문에 가능한 효율적인 알고리즘을 사용하는 것이 중요하다.
- Big 0 표기법
- 알고리즘 전투력 측정기라고 볼 수 있다.
- 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지를 설명한다..
- 최악의 경우 성능을 나타낸다.
- 표기법 예시
- O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸린다.
- O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸린다.
- O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸린다.
- O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸린다.
- 빅오 표기법 계산
- 상수 버리기, 최고 차수 항목만 남기기, 연산자 상수 무시
- 시간 복잡도
- 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도이다.
- 예제
-
void PrintPairs(int n) { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { Console.WriteLine(i + ", " + j); } } } // 두 개의 중첩된 for 루프를 포함하고 있다. 따라서 시간 복잡도는 O(n^2) int Fibonacci(int n) { if (n <= 1) { return n; } else { return Fibonacci(n - 1) + Fibonacci(n - 2); } } // 재귀적으로 피보나치 수열을 계산하는 함수. 각 호출 마다 두 번의 재귀호출을 수행하므로 //시간 복잡도는 O(2^n), 이는 매우 비효율적인 방법
-
- 공간 복잡도
- 코드의 메모리 사용량을 실제 메모리 크기로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장공간의 양을 측정하는 이유를 설명한다.
- 예제
-
// 시간 복잡도: O(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^2) int FindMax2(int[] arr) { for (int i = 0; i < arr.Length; i++) { bool isMax = true; for (int j = 0; j < arr.Length; j++) { if (arr[j] > arr[i]) { isMax = false; break; } } if (isMax) { return arr[i]; } } return -1; } int[] arr = new int[] { 1, 2, 3, 4, 5 }; // FindMax 메서드의 시간 복잡도: O(n), 공간 복잡도: O(1) int max = FindMax(arr); // 배열의 크기에 비례하여 실행 시간이 증가하므로 O(n)이라 할 수 있습니다. //또한 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다. // FindMax2 메서드의 시간 복잡도: O(n^2), 공간 복잡도: O(1) int max2 = FindMax2(arr); // 이중 반복문을 사용하기 때문에 배열의 크기에 제곱에 비례하여 실행 시간이 증가하므로 O(n^2)이라 할 수 있습니다. // 이 알고리즘은 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.
-
- 정렬 알고리즘
- 주어진 데이터 세트를 특정 순서로 배열하는 방법을 제공한다.
- 선택 정렬 ( Selection Sort )
- 배열에서 최소값 또는 최대값을 찾아 맨 앞 또는 맨 뒤와 교환하는 방법
- 시간 복잡도 : 최악의 경우와 평균적인 경우 모두 O(n^2)
- 공간 복잡도 : O(1) (상수 크기의 추가 공간이 필요하지 않음)
- 예제
-
static void SeletionSort(int[] arr) { for (int i = 0; i < arr.Length; i++) { int midIndxt = i; for (int j = i + 1; j < arr.Length; j++) // 굳이 자기 자신이랑 비교할 필요가 없기 때문에 { if (arr[j] < arr[midIndxt]) { midIndxt = j; } } Swap(arr, i, midIndxt); } }
-
- 삽입 정렬 ( Insertion Sort )
- 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법이다.
- 시간 복잡도 : 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)
- 공간 복잡도 : O(1) ( 상수 크기와 추가 공간이 필요하지 않음 )
- 예제
- 현재 위치에서 그 이하의 배열을 정렬된 배열 부분에 삽입하는 방법으로 정렬하는 알고리즘
static void InsertSort(int[] arr) { for (int i = 0; i < arr.Length; i++) { int j = i - 1; int key = arr[i]; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }
- 퀵 정렬 ( Quick Sort )
- 피벗을 기준으로 작은 요소들을 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법이다.
- 시간 복잡도 : 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
- 공간 복잡도 : 평균적으로 O(log n), 최악의 경우 O(n) ( 재귀 호출에 필요한 스택 공간 )
- 예제
- 분할 정복 방법을 이용하여 정렬하는 알고리즘
-
static 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++; Swap(arr, i, j); } } Swap(arr, i + 1, right); return i + 1; } static void QuickSort(int[] arr, int left, int right) { if (left < right) { int pivot = Partition(arr, left, right); QuickSort(arr, left, pivot - 1); QuickSort(arr, pivot + 1, right); } }
- 병합 정렬 ( Merge Sort )
- 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법이다
- 시간 복잡도 : 모든 경우에 대해 O(n log n ) ( 정렬이 되어있든 안되어있든 무조건 재귀적으로 정렬하기 때문)
- 공간 복잡도 : O(n) ( 정렬을 위한 임시 배열이 필요함 )
- 예제
- 분할 정복 방법을 이용하여 정렬하는 알고리즘
-
static void Merge(int[] arr, int left, int mid, int right) { int[] temp = new int[arr.Length]; int i = left; int j = mid + 1; int k = left; 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 l = left; l <= right; l++) { arr[l] = temp[l]; } } 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); } }
- C# Sort
- Sort 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드이다.
- Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없다.
- 예제
-
// 정수 배열 정렬 예제 int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 }; Array.Sort(numbers); Console.WriteLine(string.Join(", ", numbers)); // 문자열 리스트 정렬 예제 List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" }; names.Sort(); Console.WriteLine(string.Join(", ", names));
-
- 탐색 알고리즘
- 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공한다.
- 선형 탐색 ( Linear Search )
- 가장 단순한 탐색 알고리즘이다. 배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾는다.
- 시간 복잡도 : 최악의 경우 O(n)
- 예제
- 배열의 처음부터 끝까지 하나씩 비교하여 검색하는 알고리즘
- 배열이 정리되어 있지 않았을 경우 사용
-
int SequentialSearch(int[] arr, int target) { for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) { return i; } } return -1; }
- 이진 탐색 ( Binary Search )
- 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법이다. 중간 요소와 찾고자 하는 항목을 비교하여 대상의 중간 요소보다 작으면 왼쪽, 크다면 오른쪽을 탐색한다.
- 시간 복잡도 : O(log n)
- 예제
- 배열이 정렬되어 있을 경우 사용하는 알고리즘
- 중앙값과 비교하여 탐색 범위를 반으로 줄이는 방법으로 빠른 검색이 가능
- 1
- 그래프
- 정점과 간선으로 이루어진 자료 구조
- 방향 그래프와 무방향 그래프로 나뉨
- 가중치 그래프는 간선에 가중치가 있다.
- 그래프 탐색 방법
- 깊이 우선 탐색 ( DFS )
- 루트에서 시작하여 가능한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식
- 시간 복잡도 : 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
- 너비 우선 탐색 ( BFS )
- 루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식
- 시간 복잡도 : 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
- 예제
-
public class Graph { private int V; private List<int>[] adj; public Graph(int v) { V = v; adj = new List<int>[V]; for(int i = 0;i<V ; i++) { adj[i] = new List<int>(); } } public void AddEdge(int v, int w) { adj[v].Add(w); } private void DFSUtil(int v, bool[] visited) { visited[v] = true; Console.Write($"{v}"); foreach (int i in adj[v]) { if (!visited[i]) { DFSUtil(i, visited); } } } public void DFS(int v) { bool[] visited = new bool[V]; DFSUtil(v, visited); } public void BFS(int v) { bool[] visited = new bool[V]; Queue<int> queue = new Queue<int>(); visited[v] = true; queue.Enqueue(v); while (queue.Count > 0) { int n = queue.Dequeue(); Console.Write($"{n}"); foreach(int i in adj[n]) { if(!visited[i]) { visited[i] = true; queue.Enqueue(i); } } } } } Graph graph = new Graph(6); graph.AddEdge(0, 1); graph.AddEdge(0, 2); graph.AddEdge(1, 3); graph.AddEdge(2, 3); graph.AddEdge(2, 4); graph.AddEdge(3, 4); graph.AddEdge(3, 5); graph.AddEdge(4, 5); Console.WriteLine("\nDFS travelsal : "); graph.DFS(0); Console.WriteLine( ); Console.WriteLine("\nBFS travelsal : "); graph.BFS(0); Console.WriteLine("\n");
-
- 깊이 우선 탐색 ( DFS )
- 그래프 탐색 방법
- 최단 경로 알고리즘
- 다익스트라 알고리즘
- 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘 (음의 가중치가 없는 간선의 경우 사용)
- 벨만-포드 알고리즘
- 음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘
- A* 알고리즘
- 특정 목적지까지의 최단 경로를 찾는 알고리즘이다.
- 휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색한다.
- 다익스트라 알고리즘 예제
-
using System; class DijkstraExample { static int V = 6; // 정점의 수 // 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘 static void Dijkstra(int[,] graph, int start) { int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열 bool[] visited = new bool[V]; // 방문 여부 배열 // 거리 배열 초기화 for (int i = 0; i < V; i++) { distance[i] = int.MaxValue; } distance[start] = 0; // 시작 정점의 거리는 0 // 모든 정점을 방문할 때까지 반복 for (int count = 0; count < V - 1; count++) { // 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음 int minDistance = int.MaxValue; int minIndex = -1; for (int v = 0; v < V; v++) { if (!visited[v] && distance[v] <= minDistance) { minDistance = distance[v]; minIndex = v; } } // 최소 거리를 가진 정점을 방문 처리 visited[minIndex] = true; // 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트 for (int v = 0; v < V; v++) { if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v]) { distance[v] = distance[minIndex] + graph[minIndex, v]; } } } // 최단 경로 출력 Console.WriteLine("정점\t거리"); for (int i = 0; i < V; i++) { Console.WriteLine($"{i}\t{distance[i]}"); } } static void Main(string[] args) { int[,] graph = { { 0, 4, 0, 0, 0, 0 }, { 4, 0, 8, 0, 0, 0 }, { 0, 8, 0, 7, 0, 4 }, { 0, 0, 7, 0, 9, 14 }, { 0, 0, 0, 9, 0, 10 }, { 0, 0, 4, 14, 10, 0 } }; int start = 0; // 시작 정점 Dijkstra(graph, start); } }
-
- 다익스트라 알고리즘
- 그 외로 동적 프로그래밍, 그리디 알고리즘, 분할 정복 등의 많은 알고리즘 등이 있다. 눈에 익혀 두면 손해 볼 건 없을 것이다.
마지막으로 그리디 알고리즘 중 하나인 작업 스케쥴링을 한 번 풀어 보고 정리하겠다.
입력:
- jobs: 작업의 정보를 담은 리스트. 각 작업은 시작 시간과 종료 시간으로 구성되며, 작업의 수는 N입니다. (1 <= N <= 100)
- 예시: [(1, 4), (3, 6), (2, 8), (5, 7), (4, 9)]
출력:
- 최대로 완료할 수 있는 작업의 개수를 반환하세요.
예제: Input: [(1, 4), (3, 6), (2, 8), (5, 7), (4, 9)] Output: 3
using System;
using System.Collections.Generic;
public class Job
{
public int StartTime { get; set; }
public int EndTime { get; set; }
public Job(int startTime, int endTime)
{
StartTime = startTime;
EndTime = endTime;
}
}
public class JobScheduling
{
public int MaxJobScheduling(List<Job> jobs)
{
jobs.Sort((x, y) => x.EndTime.CompareTo(y.EndTime));
int maxJobs = 0;
int prevEndTime = 0;
foreach (var job in jobs)
{
if (job.StartTime >= prevEndTime)
{
maxJobs++;
prevEndTime = job.EndTime;
}
}
return maxJobs;
}
}
public class Program
{
public static void Main(string[] args)
{
List<Job> jobs = new List<Job>
{
new Job(1, 4),
new Job(3, 6),
new Job(2, 8),
new Job(5, 7),
new Job(4, 9)
};
JobScheduling scheduler = new JobScheduling();
int maxJobs = scheduler.MaxJobScheduling(jobs);
Console.WriteLine($"Maximum Jobs: {maxJobs}");
}
}
회고
오늘은 이번 주차 마지막 강의인 알고리즘 파트를 쭈욱 정리해보았다. 긴 코드가 대부분이라 글이 너무 지저분하게 긴 거 같은데
그만큼 중요하다는 의미이니 잊어 버릴 때 마다 꼭 한 번 씩 와서 읽어보기 위해 최대한 모든 내용을 담을려고 했다.
시작할 때도 말했지만 학교 다닐 때 부터 진짜 많이 들었던 내용인데 막상 누가 퀵 정렬이 뭐야? 라고 물어보면 항상 답을 못했던 것 같다. 이번 기회로 누가 물어봐도 설명할 수 있도록 열심히 숙지하자.
또 오늘은 개인 과제인 TextRPG를 거의 마무리 지은 참인데 아직 앱을 다시 실행 시켜도 정보가 남아있는 게임 저장하기를 구현하지 못하고 있다. 구글링을 해봐도 이게 뭔.. 내용인지.. 하면서 멍 때리면서 주욱 주욱 내리고 있다..
다음 포스트에선 아마도 TextRPG에 대해 쭉 정리해보는 시간을 가지도록 해보겠다.
'내일배움캠프 - TIL > 내일배움캠프 - TIL' 카테고리의 다른 글
| 내일배움캠프 7일차 TextRPG 마무리, C# 체크리스트 문제은행 (0) | 2025.04.18 |
|---|---|
| 내일배움캠프 6일차 TextRPG (5) | 2025.04.17 |
| 내일배움캠프 4일차 TIL 2주차 강의 4~ (0) | 2025.04.15 |
| 내일배움캠프 3일차 TIL 2주차 강의 1~4 (0) | 2025.04.14 |
| 내일배움캠프 2일차 TIL 1주차 강의 완 (0) | 2025.04.11 |