알고리즘 (2) 썸네일형 리스트형 [알고리즘] 완전탐색 DFS & BFS 깊이 우선 탐색 (DFS) DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색(DFS)은 스택 자료구조(또는 재귀 함수)를 이용한다. 완전탐색 방법 중 하나로 모든 경우의 수를 확인해야 할 경우 사용한다. 예를 들어 모든 조합을 확인하여 특정 조합의 개수를 구하는 문제를 풀 때 사용할 수 있다. DFS 탐색 방법 1번 노드부터 시작 접근하지 않은 노드가 있다면 번호가 낮은 노드부터 접근하여 PUSH PUSH(1) -> PUSH(2) -> PUSH(7) -> PUSH(6) Stack = [1, 2, 7, 6] 다음 노드가 없을 경우 접근하지 않은 노드가 연결된 노드가 나올 때까지 POP POP(6) Stack = [1, 2, 7] 이 과정을 반복하.. [알고리즘] 이진 탐색 이진탐색이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 쉽게 말해 up&down 게임과 유사하다고 볼 수 있다. 시작점, 중간점, 끝점을 이용하여 탐색 범위를 설정하는데 탐색할 숫자가 중간점보다 크다면, 중간점보다 작은 수들은 배척시킴으로써 탐색 범위를 줄여나간다. 예제 찾고자 하는 수가 14일 때 - 중간점이 2개일 경우 둘 중 아무거나 해도 상관 없다. 1. 찾고자 하는 수와 중간점을 비교한다. 2. 찾고자 하는 수(14)가 중간점보다 작다면 중간점 아래를, 높다면 중간점 위의 숫자들을 제거해준다. 3. 찾고자 하는 수(14)가 중간점보다 크기 때문에 중간점보다 작은 수들을 제외하면 아래와 같이 남게 된다. 과정 반복 중간점이 찾고자 하는 숫자와 같다면 종료한.. 이전 1 다음
