C# 문법 5주차 - 1 (자료구조와 알고리즘)
📌 탐색 알고리즘
1) 탐색 알고리즘(Search Algorihtm)
01. 탐색 알고리즘 이란?
- 탐색 알고리즘은 주어진 데아터 집합에서 특정 항목을 찾는 방법을 제공한다. 여기서는 가장 일반적인 탐색 알고리즘 몇 가지를 설펴본다.
02. 선행 탐색(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;
}03. 이진 탐색(Binary Search)
-
이진 탐색은 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법이다. 중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색한다.
-
시간 복잡도 : 최악의 경우 O(log n)
구현 예제
-
배열이 정렬되어 있을 경우 사용하는 알고리즘
-
중앙값과 비교하여 탐색 범위를 반으로 줄이는 방법으로 빠른 검색이 가능
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;
}
2) 그래프(Graph)
01. 그래프 개념과 종류
-
정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
-
방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
-
가중치 그래프(Weighted Graph)는 간선에 가중치가 있음
02. 그래프 탐색 방법
깊이 우선 탐색(Depth-First Search, DFS)
-
DFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식이다.
-
시간 복잡도 : 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
**너비 우선 탐색(Breadth-First Search, BFS)
-
BFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식이다.
-
시간 복잡도 : 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
03. 활용 예제
using System;
using System.Collections.Generic;
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);
}
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);
}
}
}
}
}
public class Program
{
public static void Main()
{
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();
}
}3) 최단 경로 알고리즘(Shortest path problem)
01. 최단 경로 알고리즘 개념과 종류
-
다익스트라 알고리즘(Dijkstra Algorithm)
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘. 음의 가중치를 갖는 간선이 없는 경우에 사용된다. -
벨만-포드 알고리즘(Bellman-Ford Algorithm)
음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘이다. 음수 사이클이 있는 경우에도 탐지할 수 있다. -
A*알고리즘(A-star Algorithm)
특정 목적지까지의 최단 경로를 찾는 알고리즘이다. 휴리스틱 함수를 사용하여 각 정점까지의 예상비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색한다.
02. 다익스트라 알고리즘 예제
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);
}
}📌 고급 알고리즘
1) 동적 프로그래밍(Dynamic Programming)
작은 문제 단위로 쪼개서 반복하여 푸는 방식
01. 동적 프로그래밍 이란?
-
동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식이다.
-
작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출한다. 이러한 저장 과정을 "메모이제이션(Memoization)"이라고 한다.
-
동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용된다.
-
일반적으로 재귀적인 구조를 가지며, 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방법으로 구현할 수 있다.
-
동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있다.
02. 동적 프로그래밍 실습 예제
// 문제: 피보나치 수열의 n번째 항을 구하는 함수를 작성하세요.
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];
}위 코드는 피보나치 수열의 n번째 항을 구하는 문제를 해결하는 C# 코드이다.
이 문제를해결하는 데는 동적 프로그래밍 방법을 사용하였으며, 시간 복잡도는 O(n)이고 공간 복잡도는 O(n)이다.
2) 그리디 알고리즘(Greedy Algorithm)
현재에 집중하는 알고리즘
01. 그리디 알고리즘 이란?
-
그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘이다.
-
각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략을 따른다.
-
그리디 알고리즘은 지역적인 최적해를 찾는데 초점을 맞추기 때문에 항상 전역적인 최적해를 보장하지는 않는다.
-
그리디 알고리즘은 간단하고 직관적인 설계가 가능하며, 싱행 시간이 매우 빠른 편이다.
-
그리디 알고리즘은 최적해를 찾는 문제에 사용되는 경우가 많지만, 일부 문제에서는 최적해를 보장하지 않을 수 있다.
02. 그리디 알고리즘 실습 예제
// 문제: 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 함수를 작성하세요.
public int MinCoins(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;
}위 코드는 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 문제를 해결하는 C# 코드이다.
이 문제를 해결하는 데는 그리디 알고리즘을 사용하였으며, 시간 복잡도는 동전의 개수에 비혜하는 O(n)이고, 공간 복잡도는 O(1)이다.
3) 분할 정복(Divide and Conquer)
작은 부분부터 착실히 해결해 나간다.
01. 분할 정복 이란?
-
큰 문제를 작은 부분 문제로 분할하므로 문제의 크기에 따른 성능 향상이 가능하다.
-
재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적이다.
-
분할된 부분 문제들을 독릭적으로 해결되므로 병렬 처리에 유리하다.
-
하지만 문제를 분할할 때 방생하는 부분 문제들 간의 중복 계산이 발생할 수 있다. 이런 경우에는 중복 계산을 피하기 위한 메모이제이션 등의 기법을 활용하여 성능을 향상시킬 수 있다.
02. 분할 정복 실습 예제
// 문제: 주어진 배열을 정렬하는 함수를 작성하세요. (퀵 정렬 사용)
public void QuickSort(int[] arr, int low, int high)
{
if(low < high)
{
int pi = Partition(arr, low, high);
QuickSort(arr, low, pi - 1); // Before pi
QuickSort(arr, pi + 1, high); // After pi
}
}
int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for(int j = low; j <= high - 1; j++)
{
if(arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, high);
return (i + 1);
}
void Swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}위 코드는 주어진 배열을 정렬하는 문제를 해결하는 C# 코드이다. 여기서는 퀵 정렬 알고리즘을 사용하였다.
이 문제를 해결하는 데는 분할 정복 방법을 사용하였으며, 시간 복잡도는 평균적으로 O(n log n)이고, 최악의 경우(이미 정렬된 배열 등)에는 O(n^2)가 된다. 공간 복잡도는 O(log n)이다.(재귀 호출 스택의 크기를 고려)
📌 문제 해결 전략과 실전 연습
1) 문제 해결 전략
01. 문제 이해 :
문제를 정확히 이해하고 요구사항을 파악하는 것이 중요하다. 문제 설명을 꼼꼼히 읽고, 입력과 출력의 형식을 이해하고 분석해야 한다.
02. 예제와 테스트 케이스 :
문제의 예제와 추가적인 테스트 케이스를 활용하여 문제를 이해하고 해결 방법을 검증해야 한다. 예제와 테스트 케이스는 문제의 조건과 제약을 이해하는 데 도움을 줄 수 있다.
03. 알고리즘 설계 :
문제를 해결하기 위한 알고리즘을 설계해야 한다. 문제의 특성에 맞는 알고리즘을 선택하고, 알고리즘의 구현 방법과 시간 복잡도를 고려해야 한다.
04. 코드 작성 :
알고리즘을 기반으로 코드를 작성해야 한다. 코드는 가독성이 좋고, 문제의 요구사항을 정확히 반영해야 한다. 변수명을 명확하게 지어 가독성을 높이고, 주석을 추가하여 코드를 설명하는 것도 좋은 습관이다.
05. 효율성 :
문제의 제약 조건과 입력 크기에 따라 알고리즘의 효율성을 고려해야 한다. 최적화 기법을 사용하고, 시간 복잡도와 공간 복잡도를 최대한 줄이는 방향으로 코드를 작성해야 한다.
06. 디버깅과 테스트 :
코드를 작성한 후에는 디버깅을 통해 오류를 찾고 수정해야 한다. 테스트 케이스를 활용하여 코드의 정확성을 검증하고, 예외 상황을 고려하여 코드를 완성해야 한다.
07. 시간 관리 :
코딩 테스트는 제한된 시간 안에 문제를 해결해야 하는 것이 특징이다. 따라서 시간을 효과적으로 관리하고, 문제에 맞는 효율적인 접근 방법을 선택하는 능력이 필요하다.
08. 연습과 경험 :
코딩 테스트는 많은 연습과 경험이 필요한 분야이다. 다양한 유형의 문제에 노출되고, 해결 방법을 익히며 자신의 실력을 향상시켜야 한다. 코딩 테스트 관련 문제를 많이 풀고 다른 사람들의 풀이를 학습하는 것도 좋은 방법이다.
2) 실전 연습 문제
- 백준 온라인 저지 (https://www.acmicpc.net/): 다양한 난이도의 알고리즘 문제를 제공하며, 많은 사용자들과 소통할 수 있는 커뮤니티도 제공한다.
- 프로그래머스 (https://programmers.co.kr/): 코딩 테스트 연습을 위한 문제들을 다양한 난이도로 제공하고 있다. 실제 취업 시험에서도 출제되는 문제들을 포함하고 있다.
- 바킹독 (**https://blog.encrypted.gg/): 알고리즘 강의 다수 제공하고 있다.
- LeetCode (https://leetcode.com/): 알고리즘 문제와 코딩 테스트 문제를 다양한 난이도로 제공하고 있으며, 실제 기업 코딩 인터뷰에서 출제되는 문제들을 포함하고 있다.
3) 코딩 테스트나 알고리즘 문제의 종류
-
탐색과 정렬: 배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬하는 문제이다. 선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬 등의 알고리즘이 주로 활용된다.
-
그래프: 그래프 구조를 활용하여 문제를 해결하는 문제이다. 최단 경로, 신장 트리, 네트워크 연결 등의 문제가 있을 수 있으며, 대표적인 알고리즘으로는 DFS(Depth-First Search), BFS(Breadth-First Search), Dijkstra, 크루스칼, 프림 등이 있다.
-
동적 프로그래밍: 큰 문제를 작은 하위 문제로 분할하여 해결하는 동적 프로그래밍 알고리즘을 활용하는 문제이다. 피보나치 수열, 최장 공통 부분 수열, 0-1 배낭 문제 등이 있다.
-
그리디 알고리즘: 각 단계에서 가장 최적인 선택을 하는 알고리즘으로, 지역적 최적해를 찾는 문제이다. 거스름돈 문제, 회의실 배정, 작업 스케줄링 등이 있다.
-
분할 정복: 문제를 작은 부분으로 분할하여 해결하는 분할 정복 알고리즘을 사용하는 문제이다. 퀵 정렬, 병합 정렬, 이진 탐색 등이 있다.
-
동적 그래프: 그래프 구조에서 동적인 변화를 다루는 문제이다. 플로이드-와샬 알고리즘, 벨만-포드 알고리즘 등이 있다.
-
문자열 처리: 문자열에 대한 다양한 처리를 다루는 문제이다. 문자열 압축, 회문 판별, 문자열 매칭 등이 있을 수 있다.
-
기타: 그 외에도 수학적인 문제, 비트 연산 문제, 시뮬레이션 문제, 동적 계획법과 그래프의 결합 문제 등 다양한 유형의 문제가 출제될 수 있다.
4) 실전 문제 체험하기
물품의 무게 정렬하기(Quick Sort)
그리기 알고리즘 - 작업 스케줄링
