코드데이 리넨 레이아웃의 출현

19일차: 리넨 레이아웃

GitHub 솔루션

오늘의 도전은 일반적인 2D 퍼즐과 다익스트라의 알고리즘에서 벗어난 신선한 변화였습니다. 제가 접근한 방법은 다음과 같습니다.

1부

목표는 간단했습니다. 사용 가능한 수건을 사용하여 주어진 수건 배열을 만들 수 있는지 확인하는 것입니다.

하지 말아야 할 일:

처음에는 itertools.combinations를 사용하여 가능한 모든 수건 조합을 생성해 보았습니다. 이것이 실용적이지 않거나 효율적이지 않다는 것이 금방 분명해졌습니다.

효과가 있었던 것:

사전(메모)과 결합된 재귀를 사용하여 이미 처리된 디자인을 캐시합니다. 이는 중복 계산을 방지하고 솔루션을 훨씬 더 효율적으로 만듭니다.

작동 방식:

각 디자인마다 수건 패턴 중 하나로 시작 부분을 맞춰보세요.
일치하는 부분이 있으면 일치하는 부분을 제거하고 나머지 부분을 반복합니다.
이미 확인한 디자인에 대해서는 메모를 사용하여 결과를 캐시하여 중복 작업을 피하세요.
메모이제이션을 통한 재귀적 접근 방식은 더 큰 입력에도 복잡성을 관리 가능하게 유지하고 솔루션을 효율적으로 실행합니다.

2부
두 번째 부분에서는 배분을 높였습니다. 사용 가능한 패턴을 사용하여 각 수건 디자인을 만드는 방법의 수를 세어보세요.

주요 통찰력:
count_arrangements 함수는 1부의 재귀 논리를 확장하지만 이제 설계를 구성하는 가능한 모든 방법을 계산합니다.

각각의 일치하는 수건에 대해 나머지 디자인을 반복합니다.
이전에 해결된 하위 문제에 대한 결과를 캐시하려면 다른 사전(memo_count)을 사용하세요.

예:
"brgr"을 두 가지 방법으로 구성할 수 있는 경우 다시 계산하는 대신 캐시에서 2를 반환하기만 하면 됩니다.

최적화:
Part 1 덕분에 우리는 어떤 디자인이 가능한지 이미 알고 있습니다. 우리는 그에 대한 배열만 계산합니다.

for arrangement in arrangements:
    if arrangement in memo and memo[arrangement]:
        ways = count_arrangements(arrangement, towels, memo_count)
        total_arrangements += ways

유효한 방법을 모두 종합하면 파트 2에 대한 최종 답을 얻을 수 있습니다. 이렇게 간단합니다.

말씀드린 것처럼 오늘의 챌린지는 꽤 재미있었고 좋은 변화였습니다. 이 기사가 향후 과제/코딩에 도움이 되었기를 바랍니다.

언제나 그랬듯이 Twitter를 통해 저를 팔로우하거나 연락해 주세요

위 내용은 코드데이 리넨 레이아웃의 출현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!