알고리즘
알고리즘이란?
문제를 해결하기 위한 명확한 절차나 방법
Big O 표기법?
- 알고리즘의 속도를 나타내주는 것
- 입력의 크기에 따른 알고리즘의 시간과 공간의 사용량을 나타냄
- 최악의 결과를 상정하기 때문에, 효율성 과장이 없음
- 최고차항의 차수만 고려하여 표기함(상수, 최고차항의 계수 등 다 무시)
ex) O(1), O(n), O(n^2), O(logn)
시간복잡도
입력(n)에 비례해 시간이 얼마나 걸리는지
공간복잡도
입력(n)에 비례해 공간이 얼마나 사용되는지
정렬 알고리즘
정렬하는 알고리즘
선택 정렬
- 배열에서 최소값(or 최대값)을 찾아 맨 앞(or 맨 뒤)와 교환하는 방법
- 시간 복잡도: 최악, 평균 모두 O(n^2)
- 공간 복잡도: O(1)
- 예제 코드
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void SelectionSort(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
int minValueIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minValueIndex])
minValueIndex = j;
}
}
Swap(arr, i, j);
}
static void Main(string[] args)
{
//그냥 랜덤 배열 생성기다. 심심해서 만들어봤다.
Random random = new Random();
int arrLength = random.Next(10, 20);
int[] intArr = new int[arrLength];
for (int i = 0; i < arrLength; i++)
{
intArr[i] = random.Next(100);
}
//랜덤 생성된 배열 확인
foreach (int i in intArr)
Console.Write(i + " ");
//Sort진행 후 배열 확인
SelectionSort(intArr);
Console.WriteLine();
foreach (int i in intArr)
Console.Write(i + " ");
}
삽입 정렬
- 정렬된 부분에 요소를 삽입하는 방법
- 시간 복잡도: 최악> O(n^2), 정렬 돼있을 시> O(n)
- 공간 복잡도: O(n)
- 예제 코드
//메커니즘은 두 번째 요소부터 마지막 요소까지 한 번씩 key로 설정하면서,
//key값을 왼쪽 요소들과 비교하면서 한칸씩 왼쪽으로 옮기는 구조이다.
static void InsertionSort(int[] arr)
{
int n = arr.Length;
// 두 번째 요소부터 시작해서 배열을 탐색
for (int i = 1; i < n; i++)
{
int key = arr[i];
int j = i - 1;
// key 값보다 큰 요소들은 한 칸씩 오른쪽으로 이동
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
// 적절한 위치에 key 값을 삽입
arr[j + 1] = key;
}
}
static void Main(string[] args)
{
int[] arr = { 12, 11, 13, 5, 6 };
Console.WriteLine("정렬 전 배열:");
Console.WriteLine(string.Join(" ", arr));
InsertionSort(arr);
Console.WriteLine("정렬 후 배열:");
Console.WriteLine(string.Join(" ", arr));
}퀵 정렬
- 맨 왼쪽이나 오른족 요소를 피벗으로 잡고,
피벗을 기준으로 작은 요소를 왼쪽, 큰 요소를 오른쪽에 배치하는 것을 반복하는 재귀 알고리즘 - 시간 복잡도: 최악> O(n^2), 평균적으로 O(nlogn)
- 공간 복잡도: 평균> O(logn), 최악 O(n)
- 예제 코드
static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
// 분할하고 피벗의 위치를 받아옴
int pivotIndex = Partition(arr, low, high);
// 피벗을 기준으로 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행
QuickSort(arr, low, pivotIndex - 1); // 피벗보다 작은 부분 정렬
QuickSort(arr, pivotIndex + 1, high); // 피벗보다 큰 부분 정렬
}
}
static int Partition(int[] arr, int low, int high)
{
// 피벗을 배열의 마지막 요소로 설정
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
// 현재 요소가 피벗보다 작거나 같으면 i를 증가시키고 교환
if (arr[j] <= pivot)
{
i++;
Swap(arr, i, j);
}
}
// i+1 위치와 피벗(현재 arr[high])을 교환하여 피벗을 제자리로 이동
Swap(arr, i + 1, high);
return i + 1;
}
static void Swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
static void Main(string[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
Console.WriteLine("정렬 전 배열:");
Console.WriteLine(string.Join(" ", arr));
QuickSort(arr, 0, arr.Length - 1);
Console.WriteLine("정렬 후 배열:");
Console.WriteLine(string.Join(" ", arr));
}병합 정렬
- 배열을 반으로 나누고 각 부분을 재귀적으로 정렬하고, 병합하는 방법
- 시간 복잡도: O(nlogn)
- 공간 복잡도: O(n)
근데 우리는 사실 그냥 C#에서 제공하는 Sort를 쓰면된다.
따로 정렬 알고리즘이 필요할 때 만들어서 사용.
- 예제 코드
// 병합 정렬 함수
static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
// 중간점 계산
int mid = left + (right - left) / 2;
// 왼쪽과 오른쪽을 각각 병합 정렬
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
// 정렬된 두 부분을 병합
Merge(arr, left, mid, right);
}
}
// 병합 함수: 두 정렬된 부분을 병합
static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1; // 왼쪽 배열의 크기
int n2 = right - mid; // 오른쪽 배열의 크기
// 임시 배열 생성
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
// 원본 배열의 값을 임시 배열에 복사
Array.Copy(arr, left, leftArray, 0, n1);
Array.Copy(arr, mid + 1, rightArray, 0, n2);
// 병합 작업
int i = 0, j = 0, k = left;
// 두 배열에서 작은 값을 선택해서 원본 배열에 넣음
while (i < n1 && j < n2)
{
if (leftArray[i] <= rightArray[j])
{
arr[k] = leftArray[i];
i++;
}
else
{
arr[k] = rightArray[j];
j++;
}
k++;
}
// 남은 요소들을 원본 배열에 복사
while (i < n1)
{
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = rightArray[j];
j++;
k++;
}
}
static void Main(string[] args)
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
Console.WriteLine("정렬 전 배열:");
Console.WriteLine(string.Join(" ", arr));
// 병합 정렬 호출
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("정렬 후 배열:");
Console.WriteLine(string.Join(" ", arr));
}탐색 알고리즘
데이터 집합 내에서 원하는 데이터를 탐색하는 알고리즘
선형 탐색 (Linear Search)
순차 탐색(Sequential Search)이라고도 함.
- 순서대로 전부 탐색
- 시간복잡도: O(n)
- 예제 코드
// 선형 탐색 함수
int LinearSearch(int[] arr, int target)
{
// 배열을 처음부터 끝까지 순회하며 목표 값 탐색
for (int i = 0; i < arr.Length; i++)
{
// 현재 값이 목표 값과 일치하면 해당 인덱스 반환
if (arr[i] == target)
{
return i;
}
}
// 목표 값을 찾지 못한 경우 -1 반환
return -1;
}이진 탐색 (Binary Search)
- 정렬된 데이터 집합에서의 탐색 방법
- 중간 값을 탐색하고 (작으면 작은쪽, 크면 큰쪽)의 중간 값을 재귀적으로 탐색
- 시간복잡도: O(logn)
- 예제 코드
int BinarySearch(int[] arr, int left, int right, int target)
{
if (left <= right)
{
// 중간 인덱스 계산
int mid = left + (right - left) / 2;
// 중간값이 목표 값과 같은 경우 인덱스 반환
if (arr[mid] == target)
return mid;
// 목표 값이 중간값보다 작으면 왼쪽 절반 탐색
if (arr[mid] > target)
return BinarySearch(arr, left, mid - 1, target);
// 목표 값이 중간값보다 크면 오른쪽 절반 탐색
return BinarySearch(arr, mid + 1, right, target);
}
// 목표 값을 찾지 못한 경우 -1 반환
return -1;
}그래프(Graph)
- 정점(Vertex)와 간선(Edge)로 이루어짐
(정점은 정보가 저장되어 있는 곳, 간선은 정점이 이어져 있는 다리) - 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
(특정 방향으로만 갈 수 있거나 그런 게 없거나) - 간선에 가중치가 있는 가중치 그래프(Weighted Graph)가 있음
(간선에 순서가 있다는 의미)
참고: visualgo: 그래프 탐색을 가시적으로 보여주는 프로그램
DFS(Depth-First Search: 깊이 우선 탐색)
깊은 곳을 먼저 탐색하는 알고리즘(깊이 우선)
BFS(Breadth-First Search: 너비 우선 탐색)
깊이를 순차적으로 탐색하는 알고리즘(너비 우선)
- DFS & BFS 예제 코드
using System;
using System.Collections.Generic;
public class Graph
{
private int V; // 그래프의 정점 개수
private List<int>[] adj; // 인접 리스트 (간선 리스트) // List<int>를 원소로 가지는 배열
//정점 개수 v만큼 배열 내부에 List<int> 초기화
//List는 각 정점에 연결되어있는 정점을 저장해주는 역할
public Graph(int v)
{
V = v;
adj = new List<int>[V];
for (int i = 0; i < V; i++)
{
adj[i] = new List<int>();
}
}
//인접 리스트에 Edge(간선)추가.
public void AddEdge(int v, int w)
{
adj[v].Add(w); //v번째 리스트(정점)에 w(정점)추가
}
//v 정점에서 DFS 시작
public void DFS(int v)
{
//방문했음?에 해당하는 bool값을 가지는, (정점개수와 길이가 같은) visited 배열 선언
bool[] visited = new bool[V];
DFSUtil(v, visited);
}
//DFS방식으로 정점확인하는 재귀
private void DFSUtil(int v, bool[] visited)
{
//v를 방문했으니 visited true로 변경
visited[v] = true;
Console.Write($"{v} ");
//v번째 정점에 연결된 정점을 가본적이 없다면 DFSUtill 실행
//들어간 DFSUtill에서 또다시 정점을 확인하기 때문에, 계속 깊은 곳으로 먼저 가게 된다.
foreach (int n in adj[v])
{
if (!visited[n])
{
DFSUtil(n, visited);
}
}
}
//v 정점에서 BFS 시작
public void BFS(int v)
{
//DFS와 마찬가지로 방문했는지 물어보는 visited배열 작성
//시작 정점을 Queue에 넣고, 나올 때 연결된 정점을 Queue에 넣는다.
bool[] visited = new bool[V];
Queue<int> queue = new Queue<int>();
//시작 정점 true & Queue에 넣음
visited[v] = true;
queue.Enqueue(v);
//queue가 비어있지 않으면 계속
while (queue.Count > 0)
{
// 가장 최근 넣은 정점을 뺌
int n = queue.Dequeue();
Console.Write($"{n} ");
//뺀 정점(n)에 연결된 정점(adj[n])을 Queue에 넣어줌(방문표시-true표시-도 하면서)
foreach (int m in adj[n])
{
if (!visited[m])
{
visited[m] = true;
queue.Enqueue(m);
}
}
}
}
}
public class Program
{
public static void Main()
{
//정점이 6개인 그래프 선언
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 traversal:");
graph.DFS(0);
Console.WriteLine();
Console.WriteLine("BFS traversal:");
graph.BFS(0);
Console.WriteLine();
}
}주석을 너무 친절하게 달아놨으니, 코드 구현을 한 번 해보도록 하자.
최단 경로 알고리즘 (Shortest path problem)
다익스트라 알고리즘(Dijkstra Algorithm)
하나의 시작 정점에서 다른 모든 정점들에 대한 최단 거리를 알 수 있는 알고리즘. 단, 음의 가중치를 가진 간선을 갖는 그래프에선 쓸 수 없다.
시간이 남는다면 다익스트라 알고리즘(Dijkstra Algorithm)에 대해 공부해 보는 것도 좋다.
- 예제 코드
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);
}
}벨만-포드 알고리즘(Bellman-Ford Algorithm)
음의 간선을 가진 그래프에서도 사용가능한 알고리즘
A* 알고리즘 (A-star Algorithm)
특정 목적지까지 최단 경로를 찾는 알고리즘.
휴리스틱 함수를 이용하여 각 정점까지의 예상 비용을 계산하고 가장 낮은 비용을 가진 정점들을 선택하여 탐색.
미숙한 초보 게임 개발자