8건의 항목
탐색하는 방법에 대해 알아보자. 검색 문제 n개의 키를 가진 배열 S와 키 x가 주어졌을 때, x=S[i]가 되는 첨자 i를 찾는 것 없다면 오류로 처리한다. 결론 : 이분 검색 알고리즘보다 효율적인 알고리즘은 없다. 이진 검색 상태 공간 트리 순차 검색은 답이없다.
골드4 : 이분 탐색 문제이다. 생각 어려웠다. 여러가지 배열이 섞이고, 계산하는 방법을 생각하지 못했다. 이 문제를 풀면서 배운 것은, 정말 컴퓨터처럼(센다..) 생각해야 된다는 것.
골드2 : 이분 탐색 문제이다. 생각 기존에 dp로 풀었던 문제가 데이터의 개수만 달라져 새로운 문제가 되었다. 이번 문제는 풀이를 좀 참고하였으며 새로운 공부를 할 수 있었다. 이 문제는 먼저, 일반적인 dp문제로 풀수가 없다.
실버2 : 파라메트릭 서치 문제이다. 생각 파라메트릭 서치 문제이다. 일단 완전 탐색이 불가하고, 답을 제시했을 때 분기를 만들 수 있다는 점에서 바로 접근했다. 인접한 집간의 최대 거리를 제시한다.
실버1 : 이분 탐색, Parametric Search 문제이다. 생각 처음에 이 문제를 풀 때, 세그먼트 트리로 풀려고 했다. 그런데, 문제가 생겼다.
실버3 : 이분 탐색 문제이다. 생각 이분 탐색 문제이다. 이전의 문제들과 마찬가지로, 값을 제시하고 그에 대한 분기를 만드는 것이 중요하다. 이 때, 어느 영역에서 답이 나오는지를 잘 체크하고, 답의 후보를 기록해두는 행위가 중요하다.
풀이1 실버4 : 이분 탐색 문제이다. 생각 특정 숫자가 등장하는 lowerBound와 UpperBound를 잡아내면 끝나는 문제이다.
실버3 : 이진 탐색 문제이다. 풀이 예산 금액은 최대예산과 아예 안주는(0원) 방법이 있다. 따라서 0과 max금액을 양 끝으로 잡는다.