소파와 바보개의 블로그

[백준/BOJ] 2110 공유기 설치 (c++)https://www.acmicpc.net/problem/21102025.02.18 - [Competitive Programming] - 06. 정렬 (Sorting Theory) - Binary Search 06. 정렬 (Sorting Theory) - Binary SearchBinary Search? 배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생dnsldprp.tistory.com20만개의 집이 주어지고 그 집에 C개의 공유기를 배치해야 합니다. 그런 경우 C개를 잘 설치해서 가장 인접한 두 공유기 사이의 최대 거..

[백준/BOJ] 3649 로봇 프로젝트 (c++)https://www.acmicpc.net/problem/36492025.02.18 - [Competitive Programming] - 06. 정렬 (Sorting Theory) - Binary Search 06. 정렬 (Sorting Theory) - Binary SearchBinary Search? 배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생dnsldprp.tistory.com100만개의 레고 조각이 주어지고, 레고 조각 2개를 사용해서 특정 숫자를 만들 수 있는지를 찾는 문제입니다. 특정 숫자는 최대 20억..

Binary Search?배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생성된다면 별다른 방법이 없겠지만 배열이 정렬되어 있다면 훨씬 더 빠른 시간에 수행할 수 있는 좋은 방법이 있습니다. Binary Search는 정렬된 배열에서 요소를 O(logN) 시간에 찾아냅니다.Binary Search Implementation 1 일반적인 구현 방식으로, 초기 상태에는 모든 배열 요소가 탐색 대상입니다. 그러나 step이 진행될 때마다, 탐색 대상을 절반으로 줄입니다. 각 단계에서는, 탐색 대상의 중간 요소를 확인합니다.  만약 중간 요소가 탐색 대상과 같다면 탐색은 종료..