[binary search] 1920번, 수 찾기

binary search 문제 중 가장 simple한 문제이지 않을까 싶다. 혹시 binary search에 대해서 잘 모른다면 아래 글을 읽어주시길 바란다. https://77monkey.tistory.com/15 [알고리즘] binary search, 이진탐색 binary serach, 이진탐색에 대해서 설명하고자 한다. 이름에서 나타나듯이 중간값이 찾고자 하는 값보다 큰지 작은지 따져가면서 찾아가는 탐색 알고리즘이다. binary search를 사용하려면, 오름차순으 77monkey.tistory.com 오늘은 문제는 아래와 같다. 문제를 확인했으면 이제 문제를 풀어보자. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 10..

• format_list_bulleted 개발
• · 2021. 5. 23.
• textsms

[알고리즘] binary search, 이진탐색

binary serach, 이진탐색에 대해서 설명하고자 한다. 이름에서 나타나듯이 중간값이 찾고자 하는 값보다 큰지 작은지 따져가면서 찾아가는 탐색 알고리즘이다. binary search를 사용하려면, 오름차순으로 정렬되어 input이 들어올 때 가능하다. 혹시나 up down 게임을 안다면 이해하기 쉬울 것이다. 1~100 중에서 하나의 숫자를 생각하고, 상대가 이 숫자를 맞추기 위해서 아무렇게 찍지는 않을 것이다. A가 생각한 숫자가 27이었다면, B는 다음과 같이 말할 것이다. A: 50 ( = (1 + 100) / 2 ) B: down A: 25 ( = (1 + 50) / 2 ) B: up A: 37 ( = (25 + 50) / 2 ) B: down A: 31 ( = (25 + 37) / 2 ) ..

• format_list_bulleted 개발
• · 2021. 5. 23.
• textsms