이분탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다. 이 알고리즘은 탐색 범위를 절반으로 줄여가며 값을 찾기 때문에, 시간 복잡도는 O(log n)이다. 이 방법은 배열이 클수록 유용하며, 선형 탐색(O(n))보다 훨씬 효율적이다. 다만, 이분탐색 알고리즘은 정렬된 배열에서만 사용할 수 있다.
풀어본 문제: 숫자_카드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b)
{
int int_a = *(int *)a;
int int_b = *(int *)b;
return (int_a > int_b) - (int_a < int_b);
// return int_a - int_b; 도 사용 가능 (오버플로우가 없다면)
}
void bs(int arr[], int low, int high, int find)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == find){
printf("1 ");
return;
}
else if (arr[mid] > find)
high = mid - 1;
else
low = mid + 1;
}
printf("0 ");
return;
}
int main(void)
{
int *have = NULL;
int m;
scanf("%d", &m);
have = (int *)malloc(sizeof(int) * m);
for (size_t i = 0; i < m; i++)
{
scanf("%d", &have[i]);
}
qsort(have, m, sizeof(int), compare);
int n;
scanf("%d",&n);
for (size_t i = 0; i < n; i++)
{
int t;
scanf("%d",&t);
bs(have,0,m-1,t);
}
free(have);
}
이분탐색 함수(bs):
bs 함수는 이분탐색 알고리즘을 구현한 부분이다. 주어진 정렬된 배열 arr에서 찾고자 하는 값 find가 있는지 확인한다.low와 high는 탐색 범위를 나타내며, 반복문을 통해 중간값 mid를 계산하여 탐색을 진행한다.arr[mid]가 찾고자 하는 값과 같다면, 1을 출력하고 탐색을 종료한다.arr[mid]가 찾고자 하는 값보다 크면, 탐색 범위를 mid 이전으로 줄이고, 반대의 경우 탐색 범위를 mid 이후로 늘린다.0을 출력한다.풀어볼 문제: 베스트셀러
입력 중 가장 많이 나온 문자열을 출력하는 문제이다, 가장 많이 나온 문자열이 여러개일경우, 사전순으로 앞서는 문자열을 출력하는 조건이 추가로 있다.
import sys
input = sys.stdin.readline
def most_sold_book(titles):
from collections import Counter
title_counts = Counter(titles)
max_count = max(title_counts.values())
most_sold_titles = []
for title, count in title_counts.items():
if count == max_count:
most_sold_titles.append(title)
return sorted(most_sold_titles)[0]
N = int(input())
titles = []
for _ in range(N):
title = input()
titles.append(title)
print(most_sold_book(titles))
파이썬으로 ps를 할 때에는 input 대신 sys.stdin.readline를 이용해 빠른 입력 처리가 가능하다는 것을 알게 되었다.
collections 모듈의 Counter사용 방법을 참고하였다. https://www.daleseo.com/python-collections-counter/
most_sold_book 함수에서 title 리스트에서 나온 횟수를 세어 딕셔너리형태로 정리한다. max(title_counts.values())를 통해 가장 많이 팔린 책의 판매량을 구하고 최고 판매량과 같은 책 이름들을 most_sold_titles 에 추가한 다음 사전순으로 정렬하여 첫번째 것을 반환한다.