[Algorithm] 탐색 알고리즘 DFS/BFS

DFS (Depth-First-Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다. DFS의 장점 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다. DFS의 단점 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다. DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문이다. BFS (Breadth-First-Search) 너비 우선 탐색이라고도 부르며 가까운 노드부터 탐색하는 알..

[Algorithm] 그리디(Greedy) : 탐욕법이란?

당장 좋은 것만 선택하는 그리디 그리디(Greedy) 알고리즘은 국내에서 단어 그대로 번역하여 탐욕법으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법 을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 자바코드와 새로 배우고 있는 파이썬 코드로 풀어보았다. 큰 수의 법칙 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번..