[LG 유레카] 이진검색
이진검색(Binary Search)
-
자료의 가운데에 있는 항목의 키 값가 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
-
이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
- 검색 과정🔎
- 자료의 중앙에 있는 원소를 고른다ㅏ.
- 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 중앙 원소의 값과 찾ㄱ고자 하는 목표 값이 일치하면 탐색을 끝낸다.
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 잦료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.
-
알고리즘: 반복구조
binarySearch(S[], n, key) start <-0 end <- n-1 WHILE start <=end mid <- (start+end)/2 IF S[mid] ==key RETURN mid ELIF S[mid] < key start <- mid + 1 ELIF S[mid] > key end < mid - 1 END WHILE RETURN -1
-
알고리즘: 재귀구조
binarySearch(S[], start,end, key) IF start > end RETURN -1 ELSE mid <- (start + end)/2 IF S[mid] ==key RETURN mid ELIF S[mid] <key RETURN binarySearch(S[], mid+1,end, key) ELSE RETURN binarySearch(S[],start, mid-1,key)
백트래킹(Backtracking)
-
백트래킹의 유명한 예시
-
nxn 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제
➡ 8-Queens 문제
- 어떤 두 Queen도 서로 위협하지 않아야한다.
- Queen을 배치한 n개의 위치는?
-
백트래킹의 특성
- 퇴각 검색
- 모든 조합을 시도해서 문제의 해를 찾음
- 해를 얻을 때까지 모든 가능성을 시도
- 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지(선택지) 중에 해결책 존재
- 여러가지(선택지)들이 존재하는 상황에서 하나의 가지를 선택
- 선택이 이루어지면 새로운 선택지들의 집합이 생성
- 이런 선택을 반복하면서 최종 상채에 도달
- 보통 재귀함수로 구현
부분수열
수열(an)이 주어졌을때, 부분수열이란 (an)의 순서는 그대로 유지하면서 몇몇 하들을 제외하여 얻은 수열을 말한다.
DFS(Depth-First Search): 깊이 알고리즘
-
깊이 우선 탐색(DFS, Depth-First Search)
트리나 그래프를 탐색하는 기법 중 하나, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘
깊이를 우선시하여 모든 경우의 수를 탐색
➡ 완전탐색 알고리즘에 속하지만 항상 완전탐색으로 사용되지 않음
- 반복문을 활용하거나, 재귀문을 통하여 구현
DFS의 탐색 과정
특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 멀리 탐색
- 방법
- 현재 노드를 방문한 것으로 표시
- 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색
- 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적
- 모든 정점을 방문할 때까지 프로세스 반복
DFS의 장단점
- DFS의 장점
- DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
- DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
- DFS를 사용하여 그래프에서 순환을 감지할 수 있다.
- DFS의 단점
- 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
- DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.
https://olrlobt.tistory.com/35
오늘 백트래킹 다시 공부하기..
댓글남기기