옥상에서 계란을 던져야 할 때: 일상적인 코딩 문제

일상적인 코딩 문제 24

해결해야 할 또 다른 문제로 돌아온 것을 환영합니다! 오늘 우리는 지붕에서 떨어지는 달걀을 다루는 이 정말 멋진 문제를 다루겠습니다. 여기에는 두 가지 가능한 해결책이 포함됩니다. 하나는 꽤 순진하고 하나는 더 영리합니다. 이 마지막 것은 우리에게 꽤 유명한 알고리즘에 대해 이야기할 기회를 줄 것입니다.

늘 그렇듯이 오늘의 문제는 멋진 뉴스레터를 통해 제공됩니다. 일일 코딩 문제 , 무료로 구독하여 일일 코딩 과제도 받을 수 있습니다. 확인해 보시고, 여러분의 문제도 해결해 보세요!

그럼 이야기는 그만하세요. 문제를 보자!

문제

Goldman Sachs가 취업 면접에서 이 문제를 질문했습니다. 문제를 살펴보겠습니다.

N 동일한 계란이 주어지고 k 층의 건물에 접근할 수 있습니다. 당신의 임무는 계란이 바닥에서 떨어지면 깨질 수 있는 가장 낮은 층을 찾는 것입니다. 계란은 한번 깨지면 다시 떨어뜨릴 수 없습니다. 계란이 xth 층에서 떨어졌을 때 깨지면 x 보다 큰 층에서 떨어졌을 때도 달걀이 깨질 것이라고 가정할 수 있습니다.

최악의 경우 이 바닥을 식별하는 데 필요한 최소 시험 낙하 횟수를 찾는 알고리즘을 작성하세요.

예를 들어, N = 1 이고 k = 5 라면 첫 번째 층부터 시작하여 5층에 도달할 때까지 모든 층에 계란을 떨어뜨려야 하므로 해는 5 됩니다.

그래서 우리는 건물의 여러 층에서 던질 수 있는 계란 몇 개를 받았습니다. 특정 층( targetFloor 라고 함)에서 던져진 계란이 땅에 떨어져도 깨지지 않는다는 점은 안타깝습니다.

그 층부터 그 아래 모든 층까지, 창문 밖으로 던져도 계란은 깨지지 않습니다. 우리가 해야 할 일은 targetFloor 찾는 효율적인 방법을 찾는 것입니다.

예상한 대로 이 문제를 해결하는 두 가지 방법을 살펴보겠습니다. 하나는 무차별 대입으로 솔루션을 제거하지만 효율적이지는 않은 매우 간단한 방법입니다. 두 번째 방법은 훨씬 더 효율적이며 최소한의 단계를 거쳐 문제를 해결하려고 시도합니다.

또한 정말 유명하고 중요한 알고리즘에 대해 이야기할 기회도 제공할 것입니다. 당신이 알아야 할 것 중 하나는 ... 기본적으로 무엇이든!

환경 설정

시작하려면 건물과 targetFloor 라는 약간의 환경을 설정해야 합니다. 건물을 만들려면 1층부터 nᵗʰ층까지 층수를 포함하는 배열을 만들기만 하면 됩니다. 그런 다음 targetFloor 가 될 임의의 숫자를 생성합니다.

우리는 Go에서 이 문제를 다시 한 번 작성하겠습니다. 읽을 수 있을 만큼 간단하지만 내부 메커니즘을 이해할 수 있을 만큼 복잡합니다.

먼저 건물 역할을 할 배열을 만듭니다. 원하는 크기를 지정할 수 있습니다. 크기가 클수록 건물도 더 높아집니다. 그런 다음 Go에 내장된 math/rand 모듈을 사용하여 targetFlor 의 인스턴스를 만듭니다.

기본적으로 현재 시간을 소스로 사용하여 0과 건물 높이(…배열의 길이 :D) 사이의 새로운 임의의 정수를 생성합니다.

무차별 대입 솔루션

물론 가장 간단한 해결책은 각 층에 있는 계란을 하나씩 던져서 어느 층에서 계란이 깨지기 시작하는지 확인하는 것입니다. 해당 정보를 포함하는 변수가 있으므로 간단히 for 루프를 수행하여 문제를 해결할 수 있습니다.

이는 가장 간단한 솔루션이지만 불행하게도 매우 비효율적입니다. 오른쪽 층이 꼭대기 층이라고 상상해 보세요. 문제를 해결하려면 계란 100,000개를 깨뜨려야 합니다. 그것은 거대한 오믈렛이 될 것이지만 상당한 낭비입니다!

일반적으로 이 솔루션의 시간 복잡도는 O(n)입니다. 솔루션의 복잡도는 입력 문제의 복잡도에 선형적으로 증가하기 때문입니다. 하지만 이것은 우리가 생각할 수 있는 가장 효율적인 솔루션은 아닙니다.

효율적인 솔루션

그러면 효율적인 해결책을 생각해 봅시다. 한 층씩 돌아다니며 각 층의 달걀을 깨뜨리는 대신, 추측을 하고 그 추측의 결과에 따라 다음 추측을 조정할 수 있습니다.

예를 들어 보겠습니다. 10층 건물이 있고 targetFloor 가 7층이라고 가정합니다(물론 우리는 이를 모릅니다). 우리는 다음과 같은 추측을 할 수 있습니다:

기본적으로 우리는 targetFloor 가 건물의 중간층이라고 추측합니다. 거기에서 계란을 던지면 가능한 결과는 두 가지입니다.

• 계란이 깨지면 우리가 너무 높다는 뜻입니다. 우리는 이 층보다 높은 층을 버리고 추측을 계속할 수 있습니다.

• 계란은 깨지지 않습니다. 이는 우리가 너무 낮거나 올바른 바닥에 있다는 것을 의미합니다. 우리는 이 층보다 낮은 층을 모두 버리고,

이를 고려하여 이제 중간층 또는 "나머지" 건물에 대해 또 다른 정보에 근거한 추측을 취하고 위에서 본 것과 동일한 전략을 적용합니다. 한 층만 남을 때까지 이 접근 방식을 계속할 수 있습니다.

우연히 이 접근 방식을 인식했다면 당신의 생각은 완전히 옳습니다. 이것은 단순히 "실제 세계" 문제에 적용되는 이진 검색일 뿐입니다. 이진 검색은 간단하고 깔끔한 분할 정복 알고리즘입니다. 즉, 솔루션을 찾을 때까지 각 단계에서 문제의 크기가 절반으로 줄어듭니다.

이는 이 알고리즘이 이전 알고리즘에 비해 훨씬 빠르다는 것을 의미합니다. 코드를 보자!

좀 더 자세히 살펴보겠습니다. 이진 검색 기능은 4개의 인수를 사용합니다.

• overArray - 우리가 반복할 건물인 정수 배열입니다.

• bottom 건물의 하단 인덱스입니다.

• top 건물의 최상층 인덱스입니다.

• breakFloor , 건물에서 찾을 수 있는지 확인하기 위해 targetFloor 보유하는 변수입니다.

그런 다음 bottom top 보다 낮은 동안 건물을 반복합니다. 이진 검색에서 두 위치 인수가 인터레이스되어 교환되면 검색된 요소를 찾을 수 없음을 의미합니다.

따라서 알고리즘이 이러한 상황으로 종료되면 루프가 종료되고 -1 반환합니다. 즉, 찾고 있는 요소가 배열에 없다는 의미입니다. 여전히 요소를 검색하는 중이라면 위 이미지에 표시된 내용을 적용합니다.

middlePoint 요소를 bottom 과 top 사이의 바닥으로 계산하고 middlePoint == breakFloor 인지 확인합니다. 그렇다면 middlePoint 결과로 반환합니다.

그렇지 않은 경우 그에 따라 bottom 또는 top 조정합니다. middlePoint breakFloor 보다 크면 건물이 너무 높다는 의미이므로 가능한 top 층을 middlePoint — 1 로 설정하여 예측을 낮춥니다.

middlePoint breakFloor 보다 작으면 middlePoint+1 로 설정하여 bottom 조정합니다.

이제 모든 것을 확인하기 위해 main 함수에서 이전과 같이 환경을 생성하고 결과를 저장할 bsFloor 라는 새 변수를 생성합니다.

알고리즘이 올바른 결과를 얻었는지 확인하기 위해 이전에 무작위로 생성된 bsFloor 및 targetFloor 모두 인쇄합니다.

시간 복잡도

이전에 예상한 대로 이 알고리즘은 선형 알고리즘보다 훨씬 빠릅니다. 각 단계에서 건물을 반으로 나누기 때문에 n이 len(building) 과 동일한 log²(n)에서 올바른 층을 찾을 수 있습니다.

이는 이 알고리즘의 시간 복잡도가 O(log(n)) 임을 의미합니다. 선형 솔루션과 마지막 솔루션을 비교하자면, 건물이 100층이면 선형 알고리즘은 최악의 경우 100번의 반복을 수행하는 반면, 이진 검색 알고리즘은 log²100 = 6.64를 사용하므로 7번의 반복을 수행합니다.

또한 이 마지막 것은 선형보다 점점 더 효율적입니다. 건물이 커질수록 이진 검색이 더 효율적이기 때문입니다. 1.000.000.000층 건물의 경우 선형 건물은 1.000.000.000걸음이 걸리고, 이진 건물은 log²1.000.000.000 = 29.9가 걸리므로 30걸음이 됩니다. 엄청난 개선이 이루어졌습니다!

결론

이거 야! 제가 도전 과제를 해결하려고 노력한 만큼 여러분도 기사를 재미있게 읽으셨기를 바랍니다! 그렇다면 박수 한두번 남겨주시면 큰 힘이 됩니다! 이러한 유형의 기사가 마음에 들고 더 많은 내용을 보고 싶다면 제가 할 수 있을 때마다 이런 유형의 콘텐츠를 공개하므로 페이지를 팔로우하세요.

마지막으로, 이 기사가 흥미롭거나 도움이 되었다고 생각하고 커피를 제공하여 기여하고 싶다면 언제든지 내 계정에서 그렇게 하세요. 코파이 페이지!

그리고 언제나처럼 읽어주셔서 감사합니다!

니콜라

여기에도 게시됨