22.08.03. 풀었던 문제들

오랜만이다! 코로나19 (아마도) 확진 + 휴가로 인해 거의 2주 쉰 것 같다. 너무 오래 쉬니까 이렇게까지 오래 쉬어도 되나..?라는 생각밖에 들지 않는다. 전역 후에는 바로 취업할 수 있게(겨울학기에는 SES와 같은 겨울 인턴을 하지 싶다) 파이팅 하고, 학점도 열심히 들어서 포상휴가를 노려보자.

 

백준 단계별 22 이분 탐색

1920 수 찾기

10816 숫자 카드 2

1654 랜선 자르기

2805 EKO

lower bound로 푸는 것보단 upper bound로 상한을 구한 후 거기서 -1을 하면 답이 된다.

 

2110 공유기 설치

'최대 설치 거리'를 binary search로 찾아가면 된다. '최대 설치 거리'를 기준으로 C개 설치 가불 여부를 따지면 O(n), 이걸 log n번 할 것이니 O(nlogn)이며, upper bound -1을 해야 한다. (최대 설치 기준이기 때문)

 

1300 K번째 수

'B[k]'를 binary search로 찾아가면 된다. lower bound를 써야 하는지, upper bound를 써야 하는지는 조금 헷갈리는데 뭘 쓰든 상관없다. 조건을 어떻게 하냐에 따라 달라진다.

 

1) 'mid보다 작거나 같은 원소의 개수가 K개와 일치'하게 조건을 짠다면 lower bound로 탐색해야만 한다.

2) 'mid보다 작은 원소의 개수가 K-1개와 일치'하게 조건을 짠다면 upper bound로 탐색해야 한다. 'K개와 일치하는 것들 중 제일 작은 것'과 'K-1개와 일치하는 것보다 큰 것'은 동치이기 때문.

 

또 구체적으로, mid보다 작거나 (같은) 원소는 1부터 N까지에 대해 min(mid/i, N)을 더해주면 된다.

 

12015 가장 긴 증가하는 부분 수열 2 - 오랜만이군.

 

이제 parametric search라는 것을 한다! 오래 전에 풀었지만 정리는 하지 않았다. 이번 주말에 해 보자.!