이진탐색 썸네일형 리스트형 백준 1300 K번째 수 이진 탐색 문제 중, 조금 특이해 보여서 풀어보았다. 처음에 그냥 행렬만들고 정렬해서 하면 되겠지 하다가 골드 3인거 보고 아 안되겠구나 했다. 이거 문제를 어떻게 접근해야하나 고민하다가 답이 안나와서 좀 찾아봤는데, 조금 머리를 써야되는 풀이였다. 만약 이 배열 B에서 11번째, 즉 B[11]을 찾고 싶다고 가정하자. B[11]의 숫자가 x라고 하면, 전체 숫자 중에서 x보다 작거나 같은 숫자의 수가 11보다 작으면 안된다. 만약 작다면, x가 더 커져야 한다. 이 (전체 숫자에서 x보다 작거나 같은 숫자의 수)를 가지고 이진 탐색을 한다. 그렇다면 이 (전체 숫자에서 x보다 작거나 같은 숫자의 수) 는 어떻게 구하느냐 하면, 각 행별로 계산을 접근해본다. 각 행은 i*1, i*2, i*3.... 의 .. 더보기 백준 1981 배열에서 이동 이진탐색 좀 여려워 보이는 문제를 잡았다. 단순히 배열의 값에서 탐색해서 값을 찾는것이 아닌, 뭔가 2D 맵을 탐색하는 문제이다. 2차원 배열의 0,0에서 우하단 자리인 n, n까지 이동할때, 전체 경로의 최대값과 최소값 차이의 최소를 찾는 문제이다. 문제 풀이는 어떻게 되냐하면, 경로상 최소-최대 값 차이가 정해졌을때, 이 경로로 갈 수 있는지 탐색하는 bfs 함수를 만든다. 이 함수를 이용해 diff값을 이진탐색을 하며 찾는다. 처음 diff값은 (start=0, end=(맵 max - 맵 min))이고, mid값은 start와 end값의 중간이다. 만약 mid값으로 탐색이 가능하다면, 우리는 더 낮은 diff값으로 탐색을 해야한다. 여기서 end = mid - 1로 갱신하여 또 탐색을 한다. -> .. 더보기 백준 2470 두 용액 이진 검색 유형의 문제를 풀어보자. 첫 문제는 가볍게 골드5로 잡았다. 이것과 유사한 문제로 세 가지 용액을 섞는 문제가 있었다. 그 때와 유사하게 생각을 해 봤다. 근데 이 문제는 그냥 두개의 용액만 가지고 계산을 하기만 하면 된다. 간단하다. 1부터 n 까지 순회하면서 해당 인덱스 + 1 ~ 끝까지 값들을 이진 탐색으로 훑는다. 현재 값(i, 1~n) 과 탐색하는 값(j, i+1 ~ n) 의 합이 0보다 크면 뒤의 절반, 0보다 작으면 앞의 절반으로 계속 계산해나간다. low와 high가 지나칠때까지 검색을 해서, 0과 가장 인접한 합 상태를 갱신한다. 이외에 출력할 때, 순서를 맞춰 출력하는 것 외에 특이사항은 없다. #include #include #include int main() { int n.. 더보기 이전 1 다음
