이진탐색
-
BOJ 2352 반도체 설계Algorithm/BOJ 2020. 6. 12. 16:10
출처: www.acmicpc.net/problem/2352 분류: Greedy, LIS 접근방식 포트에 선이 서로 꼬이지 않게 연결하려고 할 때 가장 많이 연결할 수 있는 개수를 찾는 문제입니다. 문제의 예처럼 이렇게 연결되어 있을 때, 왼쪽을 A포트 오른쪽을 B포트라고 생각해보겠습니다. A[1] -- B[4] 포트가 연결되어 있다면 왼쪽에서 A[1]을 제외한 나머지 포트들은 모두 1보다 크기 때문에 B에서 4보다 작은 포트들에는 연결할 수가 없습니다. 다시말해 A[i] 포트 --> B[j] 포트로 연결하려고 할 때 현재까지 B에 연결되어있는 포트 중 가장 큰 녀석보다 작은 경우에는 연결할 수가 없게 됩니다. 즉, 이 경우엔 B에 연결해야 하는 포트들 중에서 연속적으로 증가하는 수의 최대 길이가 몇이야?..
-
Binary Search 이진탐색(2) Lower/Upper boundAlgorithm/Theory 2020. 6. 12. 15:07
이진탐색이 정확히 원하는 값을 찾는 거라면, lower/upper bound는 원하는 값보다 처음으로 크거나 작은 값이 나오는 위치를 찾는 방법으로 중복된 요소나 타겟의 상한 하한을 찾는 경우 등 다양한 방식으로 활용될 수 있습니다. 이진 탐색에서 약간의 변형이 들어간 것으로 이진탐색을 이해하셨다면 어렵지 않게 이해할 수 있습니다. 이진탐색이 궁금하다면? --> 여기로 코드를 보기 전에 lower와 upper의 차이를 간략하게 정리해보고 가겠습니다. lower bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾습니다. upper bound는 타겟보다 처음으로 큰 값이 나오는 위치를 찾습니다. [1, 2, 2, 3, 3, 3, 4, 6] LowerBound(3) --> 3 UpperBound(3)..
-
Binary Search 이진탐색Algorithm/Theory 2020. 6. 12. 12:21
이진탐색 - 배열에서 원하는 원소를 찾는 탐색 방법이다. - 이미 정렬이 되어있는 상태에서만 사용할 수 있다. - 반씩 끊어가며 찾는 방법으로 O(logN) 의 시간복잡도를 갖는다. 이진 탐색은 이미 정렬이 되어있는 배열에서 원하는 원소를 효율적으로 찾을 수 있는 알고리즘입니다. 원리는 간단합니다. 이미 정렬이 되어있는 상태이기 때문에 반을 뚝 짤라서 찾는 원소가 왼쪽인지 오른쪽인지 확인해 아닌 부분은 버립니다. 조금 더 살펴보면, 시작 부분을 low, 끝 부분을 high라고 해볼게요. array = [1, 5, 7, 15, 22, 65, 80, 100] 배열이 이런식으로 있고 65를 찾고 싶다면, 시작할 때 low = 0, hight = 6 (array.count-1) 이고 mid = 3 = (0 + ..