일단 해보고 기록하는 블로그

문제 정보문제 링크 : BOJ 2467 용액 문제 난이도 : 골드 5유형 : 투 포인터1. 문제 접근 이 문제는 입력으로 주어지는 용액들의 값이 이미 오름차순 정렬되어 있으며,각 값의 크기 범위가 매우 넓어 모든 조합을 확인하는 완전 탐색 방식은 O(N²)라 비효율적이다. 두 용액의 합을 0에 가장 가깝게 만들어야 하므로,정렬된 배열의 양 끝에서 시작해 두 값을 비교하고 조절해 나가는 투 포인터 방식이 가장 적합하다. (1)합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동시키고,합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동시키는 방식으로필요 없는 경우의 수를 빠르게 제거할 수 있다. (2)정렬된 상태에서는 두 인덱스를 동시에 조절하며 합을 좁혀가는 방식이 가장 효율적이기 때문에,투 포인터가 이 문제에서..

문제 정보문제 링크 : BOJ 3079 입국심사 문제 난이도 : 골드 5유형 : 이분탐색 / 매개변수 탐색 1. 문제 접근이 문제는 전체 심사를 끝내는 데 필요한 최소 시간을 찾는 문제이기 때문에“특정 시간 t 안에 m명을 처리할 수 있는가?”를 판단하는 형태로 재정의했다. 어떤 값을 기준으로 이분 탐색하는가? → 시간(time)결과적으로 우리가 구하고 싶은 값이 “최소 시간” 자체이므로탐색의 기준값을 시간(time)으로 두는 것이 가장 자연스럽다. 또한 시간이 커질수록 처리할 수 있는 인원 수가 증가하기 때문에‘가능 / 불가능’을 단조적으로 분리할 수 있어 이분 탐색이 성립한다. 어떤 값을 비교해야 하는가? → t 시간 동안 처리 가능한 총 인원 수특정 시간 t를 가정했을 때,각 심사대는 t // 심사..