오늘 한 일
개인 과제 해설 완강
5주차 복습
-탐색 알고리즘
-그래프
-다익스트라
개인 과제 해설
문자 포멧팅
int num=1;
num.To.string("00"); //문자열로 표기될때 01로 표기숫자를 문자열로 바꾸면서도 앞의 자리가 0인 효과를 주고 싶을때 사용
do - while 잘못 이해한 부분
static void Main()
{
int count = 0;
do
{
Console.WriteLine($"Count is {++count}");
} while (count < 5);
}나는 이때까지 do를 한번만 실행하고 while문을 반복하는 줄 알았다. (그래서 왜 쓰는지 이해를 못하기도 했다. 굳이 do를 안써도 메인 내에 쓰면 반복문 전에 한번만 쓰게될텐데)
그런데 이제보니 do는 while문이 False가 되더라고 꼭 한번은 실행하는 반복문이더라.
따라서 앞의 런타임 결과에 따르면 count는 5가 되게 된다.
5주차 강의
탐색
선형 탐색
int SequentialSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
}
가장 단순한 탐색 알고리즘이기도 하다. 배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾는 것인데 반복문을 익히면 바로 사용할 수 있는 탐색 방법이기도 하다. 주로 정렬이 안된 배열을 탐색할 때 사용한다.
이진 탐색
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;
}
이진 탐색은 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법중 하나이다. 정수가 만약 크기순대로 정렬 되있을 경우를 예정하여 로직을 짜기 때문이다. 알고리즘은 아래와 같다.
int left = 0;
int right = arr.Length - 1;
왼쪽과 오른쪽으로 나눈 후 중간값은 왼쪽+오른쪽/2를 한 값을 한다.
if (arr[mid] == target)
{
return mid;
}
타겟이 중간값과 같다면 바로 반환하고 타겟이 중앙값보다 크다면 왼쪽을 +1한다. 그리고 위의 과정을 타겟을 찾을때까지 반복한다.
물론 정렬이 되지 않은 배열로 사용한다면 해당 알고리즘은 데이터를 배제하며 탐색하기에 탐색이 불가하다.
아무래도 이진 탐색보단 기본적인 선형 탐색이 쉽겠지만, 데이터가 훨씬 더 거대해 진다면 탐색하는 시간복잡도도 같이 커지기 때문에 큰 데이터일경우는 데이터를 매번 정렬하여 해당 탐색을 쓰는 것이 좋을 것 같다.
그래프의 탐색 알고리즘
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();
}
}깊이 우선 탐색
한 노드와 이어진 노드를 쭉 탐색하고 더이상 없다면 돌아와서 탐색하는것을 반복하는 구조이다
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);
}
}
}먼저 탐색을 했는지의 여부는 visited로 확인하며 그래프 리스트인 adj[v]를 탐색할 때 아직 visited가 false일 경우 해당 노드와 연결된 노드를 계속해서 탐색한다. 이미 탐색했을 경우 넘어간다.
따라서 결과는 노드를 연결시킨 순으로 0 1 3 4 5 2로 출력된다.
넓이 우선 탐색
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);
}
}
}
}해당 로직을 이해하려면 우선 3주차 강의의 큐(queue)를 이용해야한다. 큐는 선입 선출의 구조를 가지고 있어, 넣은 순(Enqueue)으로 원소를 빼낼 수(Dequeue) 있다.
우선 v를 통해 얻은 노드를 탐색하므로 visited[v]는 true 해준다. 큐에 원소가 들어있다면 가장 처음 들어온 원소는 빼내버린다. 이후foreach문으로 0과 인접한 노드인 1과 2를 큐에 넣는다. 또 다음에는 1을 빼내고 1과 인접한 3을 큐에 넣는다. (탐색했다는 표시로 visited = true;) 이어서 2를 빼내고 인접한 노드인 4를 큐에 넣는다 이를 반복한다.
그렇게 되면 결과는 0 1 2 3 4 5로 나오게 된다.
다익스트라
최선의 경로를 찾아내는 알고리즘 (예시로 네비게이션을 들 수 있을듯)
&
내일부턴 팀과제 시작 (우선)
아직 다익스트라의 이해도가 부족하여 시간 남을 때 다시 듣기
