Unity 내일배움캠프 TIL 0823 (1) | 알고리즘의 시간 및 공간복잡도 | 알고리즘 문제 유형 - 정렬, 그리디, DP, 분할 정복, 그래프 등
1
Unity 내일배움캠프
목록 보기
17/89
아침에 깜짝 공지가 있었다 사실 과제 제출이 6시가 아니라 2시까지라는 것..!!!
다들 6시로 알고 있었는데 이게 머선일
맘 편하고 싶어서 그냥 어제 제출했는데, 어제 제출하길 잘한 것 같다.. 휴!
오늘은 문법종합반 5주차 강의 듣기 시작~!
알고리즘
개념
- 문제를 해결하기 위한 명확한 절차나 방법
- 입력을 받아 출력을 생성하기 위한 절차
- 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 함
중요성
- 효율적인 알고리즘은 그렇지 않은 것보다 더 적은 컴퓨팅 자원(시간, 메모리 등)을 사용
Big O 표기법
개념
- 알고리즘의 효율성을 나타내는 표기법
- 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지 설명
예시
- O(1) : 상수 시간. 입력 크기에 상관없이 항상 일정한 시간이 걸림
- O(n) : 선형 시간. 입력 크기에 비례하는 시간이 걸림
- O(n^2) : 이차 시간. 입력 크기의 제곱에 비례하는 시간이 걸림
- O(logn) : 로그 시간. 입력 크기의 로그에 비례하는 시간이 걸림
계산
- 상수 버리기 : 상수 항목이나 낮은 차수의 항목은 Big O 표기법에서 중요하지 않음
- 최고 차수 항목만 남기기
- 다항식의 경우 최고 차수 항목만 고려 : O(n^3 + 5n^2) = O(n^3)
- 연산자 상수 무시 : O(3n^2 + 4n) = O(n^2)
시간 복잡도 (Time Complexity)
개념
- 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도
- 입력 크기에 대한 연산 횟수로 측정
예제
- O(n)
int Sum(int n) { int sum = 0; for (int i = 0; i <= n; i++) { sum += i; } return sum; } - 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); } } }
공간 복잡도 (Space Complexity)
개념
- 입력 크기에 따라 필요한 저장 공간의 양을 측정 (실제 메모리 크기(바이트)로 측정 X)
예제
// 시간 복잡도 : 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)
- 배열 크기에 비례하여 실행 시간이 증가하므로 시간 복잡도는 O(n)
- 추가적인 메모리 공간을 사용하지 않으므로 공간 복잡도는 O(1)
- FindMax2의 시간 복잡도 : O(n^2), 공간 복잡도 : O(1)
- 이중 반복문을 사용하므로 배열 크기의 제곱에 비례하여 실행 시간 증가. 따라서 시간 복잡도는 O(n^2)
- 추가적인 메모리 공간을 사용하지 않으므로 공간 복잡도는 O(1)
public static int[] RemoveDuplicate(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)
- 공간 복잡도 : O(n)
- 받아온 배열에 중복된 숫자가 없다면 최악의 경우 크기 n만큼의 배열을 더 만들게 되기 때문
정렬 알고리즘
정렬 알고리즘이란?
- 주어진 데이터 세트를 특정 순서로 배열하는 방법
선택 정렬 (Selection Sort)
- 배열의 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법
- 시간 복잡도 : 최악, 평균 O(n^2)
- 공간 복잡도 : O(1)
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
for (int i = 0; i < arr.Length; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}삽입 정렬 (Insertion Sort)
- 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분의 적절한 위치에 삽입하는 방법
- 시간 복잡도 : 최악 O(n^2), 최선 O(n)
- 공간 복잡도 : O(1)
int[] arr = new int[] {5, 2, 4, 6, 1, 3};
for (int i = 1; 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;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}퀵 정렬 (Quick Sort)
- pivot을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법
- 시간 복잡도 : 최악 O(n^2), 평균 O(nlogn)
- 공간 복잡도 : 평균 O(logn), 최악 O(n) (재귀호출에 필요한 스택 공간)
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
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);
// 2, 5, 4, 6, 1, 3
// 2, 1, 4, 6, 5, 3
// 2, 1, 3, 6, 5, 4
// 첫 pivot 인덱스는 2가 됨 (pivot 값 3)
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
QuickSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}
}병합 정렬 (Merge Sort)
- 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후 병합하는 방법
- 시간 복잡도 : 모든 경우 O(nlogn)
- 공간 복잡도 : O(n) (정렬을 위한 임시 배열 필요)
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);
}
}
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];
}
}
int[] arr = new int[] {5, 2, 4, 6, 1, 3};
MergeSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}C# 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));- Join : 각 멤버 사이 지정된 구분 기호를 사용하여 개체 배열을 연결
탐색 알고리즘 (Search Algorithm)
탐색 알고리즘이란?
- 주어진 데이터 집합에서 특정 항목을 찾는 방법
선형 탐색 (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(logn)
- 예제
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; }
그래프 (Graph)
개념과 종류
- 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조
- 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
- 가중치 그래프(Weighted Graph)는 간선에 가중치가 있음
탐색 방법
-
깊이 우선 탐색(DFS: Depth-First Search) : 루트에서 시작하여 가능한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식
- 시간 복잡도 : 최악 O(V+E) (V는 노드 수, E는 간선 수)
-
너비 우선 탐색(BFS: Breadth-First Search) : 루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식
-
예제
public class Graph { private int V; private List<int>[] adj; public Graph(int V) { this.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); } public void DFS(int v) { bool[] visited = new bool[V]; DFSUtil(v, visited); } private void DFSUtil(int v, bool[] visited) { visited[v] = true; Console.Write($"{v} "); foreach (int n in adj[v]) { if (!visited[n]) { DFSUtil(n, 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 m in adj[n]) { if (!visited[m]) { visited[m] = true; queue.Enqueue(m); } } } } } static void Main(string[] args) { 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("DFS travelsal: "); graph.DFS(0); Console.WriteLine(); Console.WriteLine("BFS travelsal: "); graph.BFS(0); Console.WriteLine(); }
최단 경로 알고리즘 (Shortest path problem)
종류
-
다익스트라 알고리즘(Dijkstra Algorithm)
- 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
- 음의 가중치를 갖는 간선이 없을 경우 사용
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; 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); } -
벨만-포드 알고리즘(Bellman-Ford Algorithm)
- 다익스트라 알고리즘의 한계를 해결
- 음의 가중치를 갖는 간선이 있는 그래프에서 사용 가능
- 음수 사이클이 있는 경우도 탐지 가능
public class BellmanFord { public static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { int num = 5; int[][] adj = new int[][] { {0, -4, 5, 2, 3}, {INF, 0, INF, -1, INF}, {INF, INF, 0, -7, INF}, {INF, INF, INF, 0, 6}, {INF, INF, INF, -4, 0}, }; int src = 0; int dst = 1; solve(num, adj, src, dst); } public static void solve(int num, int[][] adj, int src, int dst) { int[] dists = new int[num]; Arrays.fill(dists, INF); dists[src] = 0; for(int v=0; v < num; ++v) { for(int w=0; w < num; ++w) { if(adj[v][w] != INF) dists[w] = Math.min(dists[w], dists[v] + adj[v][w]); } } for(int i=0; i< num; ++i) System.out.println(dists[i]); } } -
A* Algorithm(A-star Algorithm)
- 특정 목적지까지 최단 경로를 찾는 알고리즘
- 휴리스틱 함수를 사용해 각 정점까지의 예상 비용을 계산, 가장 낮은 비용을 가진 정점 선택
-
플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)
- 음수 사이클이 없다면 음의 가중치를 갖는 간선이 존재할 수 있음
- 음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아왔을 때, 최정적인 비용이 음수가 되는 경우/* sample input(첫 번째 숫자는 노드의 개수, 두 번째 숫자는 간선의 개수) 5 8 0 1 5 0 4 1 0 2 7 0 3 2 1 2 3 1 3 6 2 3 10 3 4 4 */public class Floyd { static int N, M; static int[][] dist; public static void main(String[] args) throws NumberFormatException, IOException { // 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); M = Integer.parseInt(br.readLine()); // 플로이드 초기 거리 테이블 초기화 dist = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // 자기 자신으로 가는 길은 최소 비용이 0이다 if (i == j) { dist[i][j] = 0; continue; } // 자기 자신으로 가는 경우를 제외하고는 매우 큰 값 // (N개의 노드를 모두 거쳐서 가더라도 더 큰 값) dist[i][j] = 100_000_000; } } for (int i = 0; i < M; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); // 가는 경로가 하나가 아닐 수 있다. 따라서 그 중 최소 비용을 저장해두면 된다. dist[a][b] = Math.min(dist[a][b], cost); dist[b][a] = Math.min(dist[b][a], cost); } // 플로이드 워셜 알고리즘 // 노드를 1개부터 N개까지 거쳐가는 경우를 모두 고려한다 for (int k = 0; k < N; k++) { // 노드 i에서 j로 가는 경우. for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신 // 또는 연결이 안되어있던 경우(INF) 연결 비용 갱신 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } // 출력 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // 연결이 안되어 있는 경우 if (dist[i][j] == 100_000_000) { System.out.print("INF "); } else { System.out.print(dist[i][j] + " "); } } System.out.println(); } } }
Dijkstra vs Floyd-Warshall
- 플로이드 와샬은 음의 가중치를 갖는 간선이 존재할 수 있음
- 다익스트라는 가장 적은 비용을 가지는 간선을 하나씩 선택하여 알고리즘 수행
- 플로이드 와샬은 거쳐가는 정점을 기준으로 알고리즘 수행
Floyd-Warshall vs Bellman-Ford
- 플로이드 와샬은 모든 쌍에 대한 최단경로를 구할 수 있음
- 벨만 포드는 알고리즘 시작점에서의 최단경로만 알 수 있음
동적 프로그래밍 (Dynamic Programming)
동적 프로그래밍이란?
- 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식
- 메모이제이션(Memoization) : 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 활용해 큰 문제의 해결 방법을 도출하는 것
- 일반적으로 재귀 구조를 가짐
- 하향식(Top-down)과 상향식(Bottom-up)
예제
public 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];
}그리디 알고리즘 (Greedy Algorithm)
그리디 알고리즘이란?
- 각 단계에서 가장 최적의 선택을 하는 알고리즘
- 항상 전역적인 최적해를 보장하지는 않음
- 간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠름
예제
// 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구함
public int MinCoin(int[] coins, int amount)
{
Array.Sort(coins);
int count = 0;
for (int i = coins.Length - 1; i >= 0; i--)
{
while (amount >= coins[i])
{
amount -= coins[i];
count++;
}
}
if (amount > 0) return -1;
return count;
}분할 정복 (Divide and Conquer)
분할 정복이란?
- 큰 문제를 작은 문제로 분할 -> 문제 크기에 따른 성능 향상 가능
- 재귀적 구조를 가짐
- 분할된 부분 문제들은 독립적 해결이 가능하여 병렬 처리에 유리
- 예시는 Quick Sort 알고리즘 확인
알고리즘 문제 종류
- 탐색과 정렬
- 배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬
- 선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬
- 그래프
- 최단 경로, 신장 트리, 네트워크 연결
- DFS, BFS, Dijkstra, 크루스칼, 프림
- 동적 프로그래밍
- 큰 문제를 작은 하위 문제로 분할하여 해결
- 피보나치 수열, 최장 공통 부분 수열, 0-1 배낭
- 그리디 알고리즘
- 각 단계에서 가장 최적의 선택
- 거스름돈, 회의실 배정, 작업 스케줄링
- 분할 정복
- 문제를 작은 부분 문제로 분할하여 해결
- 퀵 정렬, 병합 정렬, 이진 탐색
- 동적 그래프
- 그래프 구조에서 동적인 변화를 다룸
- 플로이드-와샬, 벨만-포드
- 문자열 처리
- 문자열에 대한 다양한 처리
- 문자열 압축, 회문 판별, 문자열 매칭
- 기타
- 수학적 문제, 비트 연산, 시뮬레이션, 동적 계획법 + 그래프
