두 개의 대리석과 100층 건물

StackOverflow https://stackoverflow.com/questions/6547

  •  08-06-2019
  •  | 
  •  

문제

고전적인 프로그래밍 인터뷰 질문 중 하나...

두 개의 구슬이 주어졌고 특정 높이에서 떨어뜨리면 깨질 것이라는 말을 들었습니다(아마도 그 높이 아래에서 떨어뜨려도 피해를 입지 않을 것입니다).그런 다음 100층 건물(아마 특정 높이보다 높음)로 이동하여 가능한 한 효율적으로 깨지지 않고 구슬을 떨어뜨릴 수 있는 가장 높은 층을 찾으라는 요청을 받습니다.

추가 정보

  • 정확한 층을 찾아야 합니다. (가능한 범위는 아닙니다)
  • 구슬은 모두 같은 층에서 깨지는 것이 보장됩니다.
  • 바닥을 바꾸는 데 시간이 전혀 걸리지 않는다고 가정합니다. 대리석이 떨어지는 횟수만 계산됩니다.
  • 올바른 층이 건물에 무작위로 분포되어 있다고 가정합니다.
도움이 되었습니까?

해결책

여기서 흥미로운 점은 가능한 최소한의 방울로 이를 수행할 수 있는 방법입니다.50층까지 가서 첫 번째를 떨어뜨리는 것은 파괴층이 49층이라면 50개를 떨어뜨려야 하는 재앙이 될 것입니다.n층에 첫 번째 구슬을 떨어뜨려야 합니다. 여기서 n은 필요한 최대 구슬 수입니다.대리석이 n층에서 깨지면 그 이후에는 n-1개의 방울을 떨어뜨려야 할 수도 있습니다.구슬이 깨지지 않으면 2n-1층으로 올라가고 여기서 깨지면 최악의 경우 두 번째 구슬을 n-2번 떨어뜨려야 합니다.이렇게 100층까지 계속해서 3n-2, 4n-3에서 깨려고 하는데....
그리고 n+(n-1)+(n-2)+...1 <=100
n=14 필요한 최대 드롭 수는 무엇입니까?

다른 팁

이 문제는 책 "의 문제 6.5에서 다룹니다.코딩 인터뷰 크래킹(5차)", 솔루션은 다음과 같이 요약됩니다.

관찰:

Marble1을 삭제하는 방법에 관계없이 Marble2는 선형 검색을 수행해야 합니다.예를 들어, Marble1이 10 층과 15 층 사이에 끊어지면 Marble2와 함께 모든 층을 확인해야합니다.

접근:

첫 번째 시도: 10층에서 구슬을 떨어뜨린 다음 20층에서 구슬을 떨어뜨린다고 가정해 보겠습니다.

  • 첫 번째 방울(10층)에서 첫 번째 대리석이 깨지면 총 10개의 방울이 생깁니다.
  • 첫 번째 대리석이 마지막 방울 (100 층)에서 파손되면 총 19 방울 (층 1-10, 91-99)이 있습니다.
  • 꽤 좋은 일이지만 우리가 고려하는 것은 최악의 경우뿐입니다.우리는 두 가지 사례를 더 고르게 만들기 위해“로드 밸런싱”을해야합니다.

목표: Marble1이 첫 번째 드롭에서 깨지든 마지막 드롭에서 깨지든 상관없이 필요한 대부분의 드롭이 일관되도록 Marble1 드롭 시스템을 만듭니다.

  1. 완벽하게로드 밸런스 시스템은 Marble1이 부러진 곳에 관계없이 Marble1 + 방울의 방울이 항상 동일합니다.
  2. 마블 1 낙하가 한 걸음 더 걸리기 때문에 마블 2는 한 단계 더 적은 단계를 허용합니다.
  3. 그러므로 우리는 매번 Marble2에 필요한 잠재적 인 단계의 수를 매번 한 번씩 한 방울로 줄여야합니다.예를 들어, Marble1이 20 층에 떨어지고 30 층에 떨어지면 Marble2는 9 단계를 수행해야합니다.Marble1을 다시 삭제하면 잠재적인 Marble2 단계를 8단계로 줄여야 합니다.예를 들어 Marble1을 39층에 놓아야 합니다.
  4. 따라서 우리는 Marble1이 X X에서 시작한 다음 x-1 층으로 올라가서 x-2,… 100에 도달해야한다는 것을 알고 있습니다.
  5. X+(X-1)+(X-2)+…+1 = 100을 구합니다.X(X+1)/2 = 100 -> X = 14

14층, 27층, 39층으로 이동합니다. 최대 14단계가 소요됩니다.

코드 및 확장:

같은 높이에서 떨어뜨리면 각각 부서지나요, 아니면 서로 다른가요?

동일하다면 50층으로 가서 첫 번째 구슬을 떨어뜨린다.깨지지 않으면 75층에 가서 똑같이 하고, 계속 깨지지 않는 한 남은 것의 50%씩 계속 올라간다.깨지면 원래 있던 곳보다 높은 곳으로 돌아가서(그래서 75층에서 부러지면 다시 51층으로 돌아감), 두 번째 구슬을 떨어뜨린 뒤 깨질 때까지 한 층씩 올라가면, 그 시점에서 나는 대리석이 깨지지 않고 떨어질 수 있는 가장 높은 층을 알고 있습니다.

아마도 최선의 대답은 아닐 것입니다. 다른 사람들은 어떻게 대답하는지 궁금합니다.

첫 번째 대리석을 10층, 20층, 30층 등에 떨어뜨립니다.깨질 때까지 마지막으로 알려진 것으로 다시 점프합니다. 좋은 바닥에서 한 번에 한 층씩 구슬을 떨어뜨리기 시작하세요.최악의 경우는 99가 매직 플로어이고 항상 19방울 이하에서 찾을 수 있습니다.

나는 개인적으로 그런 퍼즐 질문을 그다지 좋아하지 않으며 인터뷰에서 실제 프로그래밍 연습을 선호합니다.

즉, 먼저 내가 떨어뜨리는 바닥에서 부러졌는지 아닌지 알 수 있는지 여부에 따라 달라집니다.나는 할 수 있다고 가정합니다.

나는 2층으로 올라가서 첫 번째 구슬을 떨어뜨렸습니다.고장나면 1층으로 가봐야겠어요.그것이 부서지면 바닥이 아니라는 것을 알았을 것입니다.

첫 번째가 깨지지 않으면 4층으로 가서 거기에서 내려갈 것입니다.그게 깨지면 다시 내려가서 다른 구슬을 구한 뒤 3층에 떨어지면 깨지는지 안 깨지는지 어느 정도까지인지 알 수 있을 것 같았다.

둘 다 파손되지 않으면 둘 다 구해서 이번에는 6층부터 동일한 과정을 수행합니다.

이렇게 하면 깨지는 구슬을 얻을 때까지 다른 층을 건너뛸 수 있습니다.

이것은 대리석이 일찍 부서지는 경우에 최적화될 것입니다...아마도 건너뛸 때마다 최대한의 효과를 얻기 위해 건너뛸 수 있는 최적의 층 수가 있을 것 같습니다...그러다가 깨지면 마지막으로 알려진 층 위의 1층부터 각 층을 개별적으로 확인해야 하는데...물론 너무 많은 층을 건너뛰면 고통스러울 것입니다(죄송하지만 지금은 최적의 솔루션을 찾지 못할 것입니다).

이상적으로는 대리석 봉지 전체를 원하고 이진 검색 알고리즘을 사용하여 바닥 수를 각 방울마다 반으로 나눌 수 있습니다.하지만 그렇다면 문제는 그게 아니었지, 그렇지?

내 생각 엔 진짜 질문은 당신이 대답을 얼마나 정확하게 원하는지입니다.왜냐하면 당신의 효율성은 실제로 그것에 달려 있기 때문입니다.

대리석에 100% 정확도를 원한다면 저스틴과 동의 할 것입니다. 일단 첫 번째 대리석이 부러지면 마지막으로 알려진 "좋은"바닥에서 어느 층이 있는지 알 때까지 한 번에 1 층으로 올라 가야합니다. 승자." 어쩌면 일부 통계를 던지고 50 층 대신 25 층에서 시작하여 최악의 시나리오가 49 대신 24가 될 수 있습니다.

대답이 플러스 또는 마이너스 1~2층일 수 있다면 몇 가지 최적화가 있을 수 있습니다.

둘째, 계단을 오르내리는 것이 효율성에 영향을 미치나요?그런 경우에는 항상 두 구슬을 모두 떨어뜨리고 위/아래로 움직일 때마다 두 구슬을 모두 집으세요.

3층에서 첫 번째 구슬을 떨어뜨립니다.깨지면 1층인지 2층인지 알 수 있으니 나머지 대리석은 2층에서 떨어뜨리세요.깨지지 않으면 2층이 가장 높다는 것을 알게 됩니다.깨지면 1층이 가장 높다는 것을 알게 됩니다.2 방울.

3층에서 드롭해도 대리석이 깨지지 않으면 6층에서 드롭하세요.깨지면 4층이나 5층이 가장 높다는 걸 알 수 있죠.5층에서 두 번째 구슬을 떨어뜨립니다.깨지지 않으면 5가 가장 높은 것을 발견했습니다.그렇다면 4층이 가장 높다.4 방울.

계속하다.

3층 - 최대 2방울

6층 - 최대 4방울

9층 - 최대 6방울

12층 - 최대 8방울

등.

3개 층 - 최대 2개 드롭

따라서 99층 건물의 경우 최대 66개의 드롭이 가능합니다.그리고 그것이 최대치입니다.아마 그보다 방울 수가 적을 것입니다.아, 그리고 100층 건물의 최대치는 66입니다.휴식층이 98층이나 97층인 경우에는 66방울만 필요합니다.브레이크 플로어가 100이라면 34방울을 사용하게 됩니다.

상관없다고 하셨지만 아마도 최소한의 걷기만 필요할 것이고 건물이 얼마나 높은지 알 필요도 없을 것입니다.

문제의 일부는 효율성을 정의하는 방법입니다.항상 x 방울 미만으로 솔루션을 얻는 것이 더 "효율적"입니까, 아니면 x 방울보다 더 많이 있을 수 있다는 경고와 함께 y < x인 y 방울에서 솔루션을 얻을 수 있는 좋은 기회를 갖는 것이 더 효율적입니까? ?

단 7개의 구슬로 이 작업을 더 잘 수행할 수 있습니다.

따라서 투표된 답변에 따라 대리석이 최소 49층에서 부서진다고 가정해 보겠습니다.

  1. 50층 -> 휴식 (답변은 1~50까지)
  2. 25층 -> 깨지지 않음 (26~50)
  3. 37층 -> 깨지지 않음 (38~50)
  4. 43층 -> 깨지지 않음 (44~50)
  5. 46층 -> 깨지지 않음 (47~50)
  6. 48층 -> 깨지지 않음 (49 또는 50)
  7. 49층 -> 브레이크(49층, 대리석이 깨질 수 있는 최소층이 50층이었기 때문에 실제로 이 단계가 필요함)

이것은 k에 대해 정렬된 집합에서 이진 검색을 수행하는 것으로 상상할 수 있습니다. 여기서 우리는 각 시도마다 솔루션 공간의 절반을 차지합니다.100층의 경우 log2 100 = 6.644(7회 시도)가 필요합니다.7개의 대리석을 사용하면 대리석이 128층까지 부서지는 최소 층수를 확신할 수 있습니다.

가장 먼저 할 일은 1층에서 시작하여 100에 도달하거나 대리석이 깨질 때까지 한 번에 한 층씩 대리석을 떨어뜨리는 아주 간단한 알고리즘을 사용하는 것입니다.

그런 다음 누군가가 그것이 문제가 될 것이라는 것을 보여줄 수 있을 때까지 왜 그것을 최적화하는 데 시간을 소비해야 하는지 묻고 싶습니다.훨씬 더 간단한 알고리즘으로 문제를 해결할 수 있는데도 사람들은 완벽하고 복잡한 알고리즘을 찾는 데 매달리는 경우가 너무 많습니다.즉, 필요할 때까지 최적화하지 마십시오.

이것은 당신이 두더지 언덕을 산으로 만들 수 있는 사람인지 알아보기 위한 까다로운 질문일 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top