오늘 배운 것
탐색 알고리즘 - 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공.
선형 탐색 - 배열의 처음부터 끝가지 하나씩 비교하여 검색하는 알고리즘으로 배열이 정렬되어 있지 않을 경우 사용함
이진 탐색 - 중앙값과 비교하여 탐색 범위를 반으로 줄이는 방법으로 빠른 검색을 함. 배열이 정렬되어 있을 경우 사용
이진탐색 기본코드
static 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;
}
left, right를 지정, left는 0, right는 배열의 길이 -1로 하고, 중앙값을 mid로 지정하여 (left + right) / 2 로 한다. 그 후 while문을 사용하여 right의 값이 left와 크거나 같다라는 조건을 걸어주고 target이 mid일 경우 mid를 return하게 하며, target이 mid보다 작으면 left = mid + 1을, 그렇지 않다면 right = mid - 1 을 하게 한다.
*(탐색에 성공했을때는 반복문 내부에 있는 return을 통해 그 값을 나타내고, 실패했을때에 나타내줄 return을 반복문 바깥에 작성해줘야한다.)
그래프 - 정점(Vertex)에 연결된 선(간선-Edge)들로 경로를 그릴 수 있는 그래프
간선 방향 유무에 따라서 방향/무방향 그래프로 나뉨
간선에 가중치가 있으면 가중치 그래프
그래프 탐색방법은 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이 있음
DFS는 말그대로 그래프의 깊이를 우선 탐색하는 것으로 시작 Vertex에 우선연결된 Edge 하나를 쭉쭉 타고 나간 뒤 더 나갈 Edge가 없으면 돌아와서 새로운 다리 하나로 나아가며 탐색함
BFS는 너비를 우선 탐색하는 것으로 시작 Vertex과 연결된 모든 Edge를 다 탄 뒤 그 뒤의 Vertex들의 Edge도 모두 타는 형식으로 나아가며 탐색함
최단경로 알고리즘은 말그대로 최단경로를 찾는 알고리즘으로 다익스트라 벨만-포드 A* 등 다양한 종류가 있다.
오늘의 회고
알고리즘 부분을 이해하려고 주어진 코드도 열심히 뜯어보고 이진탐색같은 경우는 디버그도 여러번 돌려보고 했다.
그래도 시간을 들여서 이해하려고 해보니 이해가 조금이나마 되었다.
또 그래프 같은 경우는 직접 그려보니 훨씬 수월하게 이해가 되었다.
그리고 고급 알고리즘과 문제해결 부분을 들으며 들었던 생각은,
사람이 아닌 컴퓨터가 되어야 한다.
였다.
내일부터 알고리즘 문제풀이를 시작하게 될텐데 참 걱정이다. 잘할 수 있을까?
그래도 해야지 어떡하겠나..
처음부터 잘하는 사람은 없다. 잘할 수 있도록 열심히 노력하자.
화이팅..!