이분탐색 검색 결과

해당 글 2건
가희와 프로세스 2 : 관점을 바꾸어서 이분 탐색을 적용해 봅시다.

안녕하세요. 팀 codingdog입니다. 1회에 출제된 문제 중 가장 어려웠던 문제는 가희와 프로세스 2 문제였는데요. 대회 당시에 단 2분만 푸셨을 정도로 쉽지 않은 문제였습니다. 어떤 점이 발목을 잡았는지, 그래서 어떻게 접근을 해야 했는지만 보겠습니다. 먼저 기본 아이디어는 가희와 프로세스 1 문제와 동일합니다. 나머지 프로세스의 우선순위가 1 상승하는 것을 상대적인 관점에서 생각한다. 즉, 현재 실행되고 있는 프로세스가 실행되면, 우선순위가 1 하락한다. 달라보이지만, '상대적'인 관점에서 생각하면 똑같은 말입니다. 어렵지 않죠? 문제를 요래 변형하는 게 첫 번째 포인트입니다. 이 부분은 2회의 가희와 거북이 인형 문제에서도 교과서에 나온 개념 그대로 연계해서 출제한 적이 있습니다. 예제 1번을 ..
자료알고/알고리즘 2022. 2. 21. 01:01
백준 공유기 설치 : 왜 이분탐색이 가능한가?

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 백준의 공유기 설치 문제는 많이 풀어보셨을 겁니다. 정확히 말하면, N개의 point가 있고, 그 중, C개를 설치하려고 할 때, 가장 인접해 있는 두 공유기 사이의 거리를 최대화 하라는 문제입니다. 어렵네요. 이를, 먼저 결정 문제로 바꾸어 봅시다. 그러면, 먼저 f(x)의 값을 어떻게 구해야 할 지 생각해 봅시다. N개의 집을 x 좌표 오름차순으로 정렬했다고 해 봅시다. 그러면 첫 공유기는 어디에 설치해야 할까요? 1번째 집에 설치해야 합니다. 왜 그럴까요? 문제 조건에 따르면, 같은 x좌표를 가지는 집은 없다고 했습니다. 그렇기 때문에, 집이 n개가 있고, i번째 집의 위치를 x[i]라고 하면, 아래의 식이 성립합니다. 이는 집..
자료알고/알고리즘 2020. 3. 27. 01:52