René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"이분탐색 \u0026 파라메트릭 서치","articleBody":"## 바이너리 서치\r\n\r\n이분 탐색(Binary Search)은 **정렬된 배열**에서 특정 값을 찾는 효율적인 알고리즘\r\n시간 복잡도는 O(log n)으로, 선형 검색보다 훨씬 빠름\r\n\r\n이분 탐색의 기본 원리는 다음과 같습니다:\r\n\r\n1. 배열의 중간 원소를 선택\r\n2. 중간 원소와 찾고자 하는 값을 비교\r\n3. 찾고자 하는 값이 중간 원소보다 작으면 왼쪽 부분 배열을 탐색하고, 크면 오른쪽 부분 배열을 탐색\r\n4. 찾고자 하는 값을 찾을 때까지 또는 더 이상 탐색할 수 없을 때까지 이 과정을 반복\r\n\r\n```cpp\r\n#include \u003ciostream\u003e\r\n#include \u003cvector\u003e\r\n\r\nint binarySearch(const std::vector\u003cint\u003e\u0026 arr, int target) {\r\n    int left = 0;\r\n    int right = arr.size() - 1;\r\n\r\n    while (left \u003c= right) {\r\n        int mid = left + (right - left) / 2;\r\n\r\n        if (arr[mid] == target) {\r\n            return mid;  // 타겟을 찾았을 때 인덱스 반환\r\n        } else if (arr[mid] \u003c target) {\r\n            left = mid + 1;  // 오른쪽 부분 배열 탐색\r\n        } else {\r\n            right = mid - 1;  // 왼쪽 부분 배열 탐색\r\n        }\r\n    }\r\n\r\n    return -1;  // 타겟을 찾지 못했을 때\r\n}\r\n\r\n```\r\n\r\n## 파라메트릭 서치\r\n\r\n파라메트릭 서치(Parametric Search)는 최적화 문제를 해결하는 알고리즘 기법\r\n주로 이분 탐색(Binary Search)을 응용하여 연속적인 값에 대한 결정 문제를 해결하는 데 사용.\r\n\r\n### 파라메트릭 서치의 주요 특징\r\n\r\n1. 최적화 문제를 결정 문제로 변환: \"최댓값을 찾아라\" 같은 최적화 문제를 \"이 값이 가능한가?\" 같은 결정 문제로 전환\r\n2. 이분 탐색 활용: 가능한 해의 범위를 이분 탐색으로 좁혀가며 최적해를 찾습니다.\r\n3. 연속적인 값에 적용: 정수뿐만 아니라 실수 값에 대해서도 사용할 수 있습니다.\r\n4. 효율성: O(log N) 시간 복잡도로 최적해를 찾을 수 있습니다.\r\n\r\n\r\n### 파라메트릭 서치의 일반적인 절차\r\n\r\n1. 문제의 답이 될 수 있는 범위를 정합니다.\r\n2. 그 범위의 중간값에 대해 결정 문제를 해결합니다.\r\n3. 결과에 따라 탐색 범위를 반으로 줄입니다.\r\n4. 원하는 정확도에 도달할 때까지 2-3 과정을 반복합니다.\r\n\r\n파라메트릭 서치는 다양한 최적화 문제에 적용할 수 있습니다. 예를 들어, 특정 조건을 만족하는 최대 또는 최소값을 찾는 문제, 이진 탐색으로 해결할 수 있는 결정 문제 등에 활용됩니다.\r\n\r\n","author":{"url":"https://github.com/psychehose","@type":"Person","name":"psychehose"},"datePublished":"2024-07-29T12:05:32.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/3/SquirtlesAlgorithmStudyS8/issues/3"}