일상적인 코딩 문제 24  해결해야 할 또 다른 문제로 돌아온 것을 환영합니다! 오늘 우리는 지붕에서 떨어지는 달걀을 다루는 이 정말 멋진 문제를 다루겠습니다. 여기에는 두 가지 가능한 해결책이 포함됩니다. 하나는 꽤 순진하고 하나는 더 영리합니다. 이 마지막 것은 우리에게 꽤 유명한 알고리즘에 대해 이야기할 기회를 줄 것입니다.  늘 그렇듯이 오늘의 문제는 멋진 뉴스레터를 통해 제공됩니다.  , 무료로 구독하여 일일 코딩 과제도 받을 수 있습니다. 확인해 보시고, 여러분의 문제도 해결해 보세요!   일일 코딩 문제  그럼 이야기는 그만하세요. 문제를 보자!  문제  Goldman Sachs가 취업 면접에서 이 문제를 질문했습니다. 문제를 살펴보겠습니다.    동일한 계란이     층의 건물에 접근할 수 있습니다. 당신의 임무는 계란이 바닥에서 떨어지면 깨질 수 있는 가장 낮은 층을 찾는 것입니다. 계란은 한번 깨지면 다시 떨어뜨릴 수 없습니다. 계란이   층에서 떨어졌을 때 깨지면   보다 큰 층에서 떨어졌을 때도 달걀이 깨질 것이라고 가정할 수 있습니다. N 주어지고 k xth x   최악의 경우 이 바닥을 식별하는 데 필요한 최소 시험 낙하 횟수를 찾는 알고리즘을 작성하세요.      이고   라면 첫 번째 층부터 시작하여 5층에 도달할 때까지 모든 층에 계란을 떨어뜨려야 하므로 해는   됩니다. 예를 들어, N = 1 k = 5 5  그래서 우리는 건물의 여러 층에서 던질 수 있는 계란 몇 개를 받았습니다. 특정 층(   라고 함)에서 던져진 계란이 땅에 떨어져도 깨지지 않는다는 점은 안타깝습니다. targetFloor  그 층부터 그 아래 모든 층까지, 창문 밖으로 던져도 계란은 깨지지 않습니다. 우리가 해야 할 일은   찾는 효율적인 방법을 찾는 것입니다. targetFloor  예상한 대로 이 문제를 해결하는 두 가지 방법을 살펴보겠습니다. 하나는 무차별 대입으로 솔루션을 제거하지만 효율적이지는 않은 매우 간단한 방법입니다. 두 번째 방법은 훨씬 더 효율적이며 최소한의 단계를 거쳐 문제를 해결하려고 시도합니다.  또한 정말 유명하고 중요한 알고리즘에 대해 이야기할 기회도 제공할 것입니다. 당신이 알아야 할 것 중 하나는 ... 기본적으로 무엇이든!  환경 설정  시작하려면 건물과   라는 약간의 환경을 설정해야 합니다. 건물을 만들려면 1층부터 nᵗʰ층까지 층수를 포함하는 배열을 만들기만 하면 됩니다. 그런 다음   가 될 임의의 숫자를 생성합니다. targetFloor targetFloor  우리는 Go에서 이 문제를 다시 한 번 작성하겠습니다. 읽을 수 있을 만큼 간단하지만 내부 메커니즘을 이해할 수 있을 만큼 복잡합니다.   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  먼저 건물 역할을 할 배열을 만듭니다. 원하는 크기를 지정할 수 있습니다. 크기가 클수록 건물도 더 높아집니다. 그런 다음 Go에 내장된   모듈을 사용하여   의 인스턴스를 만듭니다. math/rand targetFlor  기본적으로 현재 시간을 소스로 사용하여 0과 건물 높이(…배열의 길이 :D) 사이의 새로운 임의의 정수를 생성합니다.  무차별 대입 솔루션  물론 가장 간단한 해결책은 각 층에 있는 계란을 하나씩 던져서 어느 층에서 계란이 깨지기 시작하는지 확인하는 것입니다. 해당 정보를 포함하는 변수가 있으므로 간단히 for 루프를 수행하여 문제를 해결할 수 있습니다.   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  이는 가장 간단한 솔루션이지만 불행하게도 매우 비효율적입니다. 오른쪽 층이 꼭대기 층이라고 상상해 보세요. 문제를 해결하려면 계란 100,000개를 깨뜨려야 합니다. 그것은 거대한 오믈렛이 될 것이지만 상당한 낭비입니다!  일반적으로 이 솔루션의 시간 복잡도는 O(n)입니다. 솔루션의 복잡도는 입력 문제의 복잡도에 선형적으로 증가하기 때문입니다. 하지만 이것은 우리가 생각할 수 있는 가장 효율적인 솔루션은 아닙니다.  효율적인 솔루션  그러면 효율적인 해결책을 생각해 봅시다. 한 층씩 돌아다니며 각 층의 달걀을 깨뜨리는 대신, 추측을 하고 그 추측의 결과에 따라 다음 추측을 조정할 수 있습니다.  예를 들어 보겠습니다. 10층 건물이 있고   가 7층이라고 가정합니다(물론 우리는 이를 모릅니다). 우리는 다음과 같은 추측을 할 수 있습니다:  targetFloor  기본적으로 우리는   가 건물의 중간층이라고 추측합니다. 거기에서 계란을 던지면 가능한 결과는 두 가지입니다. targetFloor  계란이 깨지면 우리가 너무 높다는 뜻입니다. 우리는 이 층보다 높은 층을 버리고 추측을 계속할 수 있습니다.  계란은 깨지지 않습니다. 이는 우리가 너무 낮거나 올바른 바닥에 있다는 것을 의미합니다. 우리는 이 층보다 낮은 층을 모두 버리고,  이를 고려하여 이제 중간층 또는 "나머지" 건물에 대해 또 다른 정보에 근거한 추측을 취하고 위에서 본 것과 동일한 전략을 적용합니다. 한 층만 남을 때까지 이 접근 방식을 계속할 수 있습니다.  우연히 이 접근 방식을 인식했다면 당신의 생각은 완전히 옳습니다. 이것은 단순히 "실제 세계" 문제에 적용되는   뿐입니다. 이진 검색은 간단하고 깔끔한   알고리즘입니다. 즉, 솔루션을 찾을 때까지 각 단계에서 문제의 크기가 절반으로 줄어듭니다. 이진 검색일 분할 정복  이는 이 알고리즘이 이전 알고리즘에 비해 훨씬 빠르다는 것을 의미합니다. 코드를 보자!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  좀 더 자세히 살펴보겠습니다. 이진 검색 기능은 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이   과 동일한 log²(n)에서 올바른 층을 찾을 수 있습니다. len(building)  이는 이 알고리즘의 시간 복잡도가   임을 의미합니다. 선형 솔루션과 마지막 솔루션을 비교하자면, 건물이 100층이면 선형 알고리즘은 최악의 경우 100번의 반복을 수행하는 반면, 이진 검색 알고리즘은 log²100 = 6.64를 사용하므로 7번의 반복을 수행합니다. O(log(n))  또한 이 마지막 것은 선형보다 점점 더 효율적입니다. 건물이 커질수록 이진 검색이 더 효율적이기 때문입니다. 1.000.000.000층 건물의 경우 선형 건물은 1.000.000.000걸음이 걸리고, 이진 건물은 log²1.000.000.000 = 29.9가 걸리므로 30걸음이 됩니다. 엄청난 개선이 이루어졌습니다!   결론  이거 야! 제가 도전 과제를 해결하려고 노력한 만큼 여러분도 기사를 재미있게 읽으셨기를 바랍니다! 그렇다면 박수 한두번 남겨주시면 큰 힘이 됩니다! 이러한 유형의 기사가 마음에 들고 더 많은 내용을 보고 싶다면 제가 할 수 있을 때마다 이런 유형의 콘텐츠를 공개하므로 페이지를 팔로우하세요.  마지막으로, 이 기사가 흥미롭거나 도움이 되었다고 생각하고 커피를 제공하여 기여하고 싶다면 언제든지 내 계정에서 그렇게 하세요.  페이지!   코파이  그리고 언제나처럼 읽어주셔서 감사합니다!   니콜라    게시됨 여기에도

Read My Stories

이 오디오는 이야기의 원래 언어로 제작되었습니다!

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

About Author

코멘트

태그 걸기

이 기사는 다음에서 발표되었습니다.

Related Stories

독특한 생태계를 강화하는 비트코인 UTXO 모델

Floki의 Valhalla가 인도 스리랑카 투어의 보조 후원자로 합류

AI/ML 데이터레이크용 참조 아키텍처 구축을 위한 설계자 가이드

AI의 힘을 발휘하세요. 최첨단 기술의 체계적 검토: 개요 및 소개

독특한 생태계를 강화하는 비트코인 UTXO 모델

Floki의 Valhalla가 인도 스리랑카 투어의 보조 후원자로 합류

AI/ML 데이터레이크용 참조 아키텍처 구축을 위한 설계자 가이드

AI의 힘을 발휘하세요. 최첨단 기술의 체계적 검토: 개요 및 소개

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps