5W.2D-이진탐색

✏️문제[정렬된 배열에서 특정 수의 개수 구하기]

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(log N)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 조건
첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
(1 ≤ N ≤ 1,000,000), (-10⁹ ≤ x ≤ 10⁹)
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
(-10⁹ ≤ 각 원소의 값 ≤ 10⁹)
출력 조건
수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

이진탐색을 쉽게 구현하는 라이브러리:bisect

from bisect import bisect_left, bisect_right

N, x = map(int, input().split())
arr = list(map(int, input().split()))

count = bisect_right(arr, x) - bisect_left(arr, x)
if count == 0:
    print(-1)
else:
    print(count)

---

✏️문제[고정점 찾기]

고정점Fixed Point이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2]=2이므로, 고정점은 2가 됩니다.
하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 만약 고정점이 없다면 -1을 출력합니다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력조건
첫째 줄에 N이 입력됩니다. (1≤N≤1,000,000)
이상 기호를 찾았다
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤각 원소의 값 ≤10^9)
지수는 못 찾았다. 숫자를 필요할 때마다 입력해줘야 할 것 같은데 귀찮다
출력조건
고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

고정점의 값= 중간값-> 탐색

def search(arr, first, last):
    if start > end:
        return -1
    mid = (first + last) // 2
    if arr[mid]=mid:
        return mid
    elif arr[mid] > mid:
        return search(arr, first, mid - 1)
    else:
        return search(arr, mid + 1, last)

n = int(input())
arr = list(map(int, input().split()))
res = search(arr, 0, n - 1)
print(res)

문제[반도체 설계]

https://www.acmicpc.net/problem/2352

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

코드를 입력하세요