개발일지

이진 탐색 개요 예전 이진 탐색에 대한 개념적인 부분을 해당 글에서 다룬 적이 있었다. 다시 상기하자면, 정렬된 배열을 반으로 나눠가며 원하는 값을 찾는 알고리즘이 이진 탐색이다. 이번 시간에는 해당 알고리즘을 구현한 std::binary_search 함수에 대한 사용법을 알아보도록 하자. 본문 사용법 이진 탐색 또한 탐색의 일종이므로, 배열 내에서 특정 요소가 존재하는지 확인할 때 사용된다. 이때 대상 범위가 이미 정렬되어 있어야 하며, 중복 요소가 있는 경우 어느 요소인지 알 수 없다. 이는 함수가 단순히 주어진 값이 배열 내에 존재하는지 여부만을 체크하기 때문이다. #include #include #include int main() { std::vector v = { 1, 2, 4, 5, 9, 10..

알고리즘 및 이진 탐색알고리즘　알고리즘(Algorithm)이란 주어진 문제를 해결하기 위한 일련의 명령들의 순서와 절차를 의미한다. 다시 말해, 문제를 정의하는 데 필요한 입력을 받아, 일련의 변환 과정을 거쳐 결과를 출력한다는 점에서 함수와 유사한 개념이다. 이러한 알고리즘은 문제를 효율적으로 해결하기 위해 설계되며, 이를 위해 다양한 최적화 기법이 사용된다. 　알고리즘의 효율성은 해당 알고리즘의 동작과 수행에 필요한 명령 수에 따라 결정된다. 예를 들어 소수를 판별하는 알고리즘을 짰다고 가정하자.  // 소수 판별 알고리즘1bool isPrime1(int n){ for (int i = 2; i 　두 개의 소수 판별 알고리즘 중 어떤 게 효율적일까? 먼저 첫 번째 함수는 2부터 n까지 모든 수를 ..

문제설명 입출력 예제 개념 이 전의 포스팅된 문제와 유사하게 해결할 수 있는 문제다. M개의 문자열 중에 N개의 문자열과 겹치는 게 있는지 개수를 카운팅 하는 문제다. 이진 탐색을 이용하여 개수를 늘리는 식으로 해결할 수 있다. 풀이 #include #include #include int main() { int N, M, count = 0; std::string str; std::vector v; std::cin >> N >> M; 문자열의 개수 N, M과 겹치는 문자열의 개수 count를 초기화한다. 그리고 입력으로 받을 문자열 str과 문자열을 저장할 컨테이너 v를 초기화한다. while (N--) { std::cin >> str; v.push_back(str); } std::sort(v.begin(..

문제설명 입출력 예제 개념 이 문제는 M개의 숫자 카드 중에서 N개의 숫자 카드와 겹치는 카드가 있는지 찾는 문제다. find 함수를 사용하면 최악의 경우, 시간 복잡도가 O(MN)이 되므로 시간 초과 문제에 걸리기 십상이다. 따라서 이진 탐색을 이용해 시간 복잡도를 O(M logN)으로 개선하여 해결하면 된다. 풀이 #include #include #include int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N, M, n; std::vector v; 카드의 개수 N, M, 숫자 카드 n을 초기화하고, 숫자 카드들을 담을 컨테이너 vector v를 초기화한다. std::cin >> N; for (int i =..