이진탐색 이란 ? 범위의 절반인 50을 시도해가며 탐색하는 과정을 이진탐색이라고 합니다. 예를 들어, 100페이지인 책에서 70 페이지를 찾아가고 싶다고 가정했을 때 순차탐색의 경우, 1부터 70 까지 하나하나 1,2,3...68,69,70 이런 식으로 찾아가게 됩니다. 이진탐색의 경우,  100의 절반인 50을 찾은 후 타겟(70) 보다 작은 경우이기에 50~100 으로 범위를 변경하고50~100까지의 절반인 75를 찾습니다. 그리고 타겟보다 큰 경우이기에 50~75 로 범위를 다시 변경합니다. 이런식으로 절반씩 범위를 줄여나가는 것을 이진탐색이라합니다.  이진탐색을 통해 푼 무작위 수 찾기 문제코딩테스트 강의를 듣던 중 아래 문제를 푸는 과정을 기록하려합니다. 무작위 숫자로 되어있는 array 에서 ..

Greedy (그리디) 란 ? 탐욕적인 뜻을 가진 Greedy(그리디) 는 탐욕법 이라고도 합니다. 이는, 현재 상황에서 지금 당장 좋은 것만 고르는 방법입니다. 풀어서 설명하자면, 그리디 알고리즘을 사용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 알고리즘입니다. 그렇기 때문에 그리디 알고리즘으로 푼 답이 꼭 최적의 해가 아닐 수도 있다는 것입니다. 더보기 최적의 해란 구하고자 하는 답에 가깝거나, 문제풀이에 있어 정답인 해를 말합니다. 그렇다면, 최적의 해를 보장한다는 건 어떤 의미일까요? 먼저 가장 대표적인 그리디 알고리즘의 문제 예시로 거스름돈 문제풀이 방식을 확인해 보겠습니다. 문제 내용은 주어진 화폐단위 내에서 거스름돈의 동전을 최소한..