21. 8. 6(금) TIL(이진탐색, DFS, BFS, 그리디)

배준형·2021년 8월 6일

TIL

목록 보기

5/21

Javascript 자료구조

📌 이진탐색(Binary Search)

선형탐색 : 순서대로 하나씩 찾는 탐색으로 O(n)의 시간 복잡도를 가진다.
이진탐색 : 정렬 되어있는 요소들을 반씩 제외하며 찾는 탐색으로 O(logn)의 시간 복잡도를 가진다.

정렬되어 있는 요소들 중 탐색할 때 사용이 가능하다.
정렬되어 있지 않은 요소를 정렬한 후 이진탐색 하면 선형탐색보다 늦을 수 있다.

위 요소에서 이진탐색을 통해 23의 Index를 찾는 과정

1. Left=0, Right=9 / Mid=4 로 중간값인 16을 23과 비교한다.
2. 이후 16이 23보다 작으므로 Left = Mid + 1 = 5
3. Left=5, Right=9 / Mid=7 로 중간값인 56이 23보다 크므로 Right = Mid - 1 = 6
4. Left=5, Right=6 / Mid=5 로 중간값이 찾는값과 같으므로 탐색을 종료한다.

이미지 출처 : https://www.geeksforgeeks.org/binary-search/

📌 BFS(Breadth-first search)

BFS(너비 우선 탐색) : 임의의 노드에서 인접한 노드를 먼저 탐색하는 그래프 탐색 알고리즘이다.

Queue(큐) 자료구조를 이용하여 구현할 수 있다.
BFS는 재귀적으로 동작하지 않는다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용한다.

이미지 출처 : https://devuna.tistory.com/32

📌 DFS(Depth-first search)

DFS(깊이 우선 탐색) : 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 그래프 탐색 알고리즘이다.

Stack(스택) 자료구조를 이용하여 구현할 수 있다.
재귀적으로 동작하는 순환 알고리즘의 형태를 가지고 있다.
주로 모든 노드를 방문하고자 할 때 사용된다.

이미지 출처 : https://devuna.tistory.com/32

📌 그리디(Greedy)

그리디(Greedy) : 매 선택에서 지금 이 순간 최적의 답을 선택하는 알고리즘이다.

최적해를 보장하지 않는다.
보통 최적해를 구하는 알고리즘보다 빠르다.
직관적인 문제 풀이에 적합하다.

거스름돈 문제

240원의 물건을 1,000원을 주고 구매했을 때 거스름돈의 동전을 가장 적은 수로 주는 방법
(화폐의 단위는 500원, 100원, 50원, 10원이 있다.)

1. 물건의 값인 240원을 뺀 나머지 760원 중 가장 큰 단위인 500원 1개
2. 나머지 260원 중 가장 큰 단위인 100원 2개
3. 나머지 60원 중 가장 큰 단위인 50원 1개
4. 나머지 10원 1개

∴ 500원 1개, 100원 2개, 50원 1개, 10원 1개 로 거스름돈을 줄 수 있다.

단, 위 거스름돈 문제에서 그리디 알고리즘이 적용되려면 화폐의 단위가 5, 10 등 단위가 맞아 떨어지는 경우에만 성립한다.

단위가 맞아 떨어지지 않는 거스름돈 문제

30원의 물건을 100원 주고 구매했을 때 거스름돈의 동전을 가장 적은 수로 주는 방법
(화폐의 단위는 10원, 30원, 40원, 50원이 있다.)

📢 그리디 해법

1. 물건의 값을 뺀 나머지 70원 중 가장 큰 단위인 50원 1개
2. 남은 20원은 10원 2개

∴ 총 50원 1개, 10원 2개로 동전 3개를 거슬러 준다.

📢 최적해

40원 1개, 30원 1개로 동전 2개를 거슬러 준다.

📌 배운점

이진탐색, DFS, BFS, 그리디 자료구조에 대해 학습하였다. 이미 코딩테스트를 준비하면서 한번씩은 들어봤고 해당하는 코딩 문제들도 풀어본 자료구조였는데, 이미 경험했다 하더라도 금일 학습하면서 다시 코드에 적용시키기는 쉽지 않았다. 아직 자료구조에는 익숙하지 않다는 것을 느꼈다.

특히 최초로 그리디 알고리즘을 학습할 때 매우 단순하게 느껴져서 많은 시간을 할애하지 않았는데, 오늘 다시 학습하면서 그리디 알고리즘을 이용한 다양한 알고리즘이 있다는 것을 알게 되었다. 대표적으로 크루스칼, 다익스트라 알고리즘이 있었고, 이 중 다익스트라 알고리즘이 1956년도에 발표되었다는 사실을 듣고 많은 것을 느꼈다.

지금 공부하고 있는 자료구조와 알고리즘이 누군가에겐 쉬울 수 있지만 지금 나에게는 마냥 쉽지만은 않다. 그러나 다익스트라 알고리즘이 약 60년이 지난 지금도 사용되고 있는것을 보면 자료구조와 알고리즘의 기본 틀은 크게 바뀌지 않는 것 처럼 느껴진다. 공부에는 끝이 없지만 그래도 지금 공부하고 있는 내용들을 확실하게 익혀두면 다음에 비슷한 자료구조나 알고리즘이 등장한다고 하더라도 학습하는데 도움이 될것이라고 믿는다.

📌 앞으로

여전히 익숙하지 않은 자료구조와 알고리즘들이라 여러번 반복해서 숙달해야 익숙해 질 것이라고 생각한다. 가장 좋은 방법은 남이 작성한 코드를 읽는 것이 아니라 직접 머리속으로 구상하여 코드를 작성하는 것이라 생각한다. 해당하는 코딩테스트 문제를 풀어보면서 점점 익숙해질 예정이고 오늘 다시 학습했다고 하더라도 다음에 학습할 기회가 생겼을 때 안다고 넘어가지 말고 항상 초심으로 공부하는 자세를 가져야겠다.