알고리즘 - 그리디 알고리즘 / 이진탐색

그리디 알고리즘

• 탐욕 알고리즘 - 당장 눈앞에 보이는 가장 좋아보이는 선택지를 고르는 알고리즘

• 현재 상태에서 보는 선택지 중 최선의 선택이 전체 선택지 중 최선의 선택이라고 가정
• 지역적으로 최적인 해답이 전역적으로도 최적인 문제에 대해 적용 가능
• 완전 탐색과 비교하면 시간 복잡도가 압도적으로 줄어드는 경우가 많음

그리디 알고리즘 수행 과정

1) 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택
2) 적절성 검사 : 현재 선택한 해가 전체 문제의 제약조건에 벗어나지 않는지 검사
3) 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사.
전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정 반복

이진 탐색

정렬된 데이터에서 데이터의 중앙값과 찾는 값을 비교해
데이터의 크기를 절반씩 줄이면서 대상을 찾는 탐색 방법

이진 탐색 과정
1) 현재 데이터셋의 중앙값 선택
2) 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터셋 선택
3) 중앙값 < 타깃 데이터 일 때 중앙값 기준으로 오른쪽 데이터셋 선택

중앙값 : (low+high)/2
중앙값 < 목표값 : low = 중앙값+1
중앙값 > 목표값 : high = 중앙값-1
중앙값 == 목표값 : 탐색 성공
low>high, high<low : 엇갈리는 경우 탐색 실패