Python 트릭을 사용하여 최소 코인 변경 (Amazon Interview) 찾기

Oct 04 2020

동전 교환 문제는 무엇입니까? 변화를 만드는 문제는 주어진 금액에 합산되는 (특정 종파의) 최소 코인 수를 찾는 문제를 해결합니다. 정수 배낭 문제의 특수한 경우이며 통화보다 더 넓은 응용 프로그램이 있습니다. 더 읽기 : Wiki

내 코드 :

def coin_change(n,coins,known_results):
     min_coins = n

     if n in coins:
        known_results[n] = 1
        return 1
     
     elif known_results[n] > 0:     
            return known_results[n] 


     else:
        for i in [c for c in coins if c<=n]:
            count = 1 + coin_change(n-i,coins,known_results)
            if count < min_coins:
                min_coins = count
                
                known_results[n] = min_coins

     return min_coins

coins = [1,2,3]
n = 4
known_results = [0]*(n+1) 
print(coin_change(n,coins,known_results))

질문 : 이 코드는 훌륭하고 완벽하게 작동하지만 파이썬 트릭을 사용하여 더 효율적이고 효율적으로 수행 할 수있어 다른 언어보다 우위를 점할 수 있습니까? 더 효율적이고 더 나을 수 있습니까?

답변

3 hjpotter92 Oct 04 2020 at 15:11

Code Review에 오신 것을 환영합니다! 귀하의 코드는 괜찮아 보이고 따라하기가 매우 쉽습니다. 참고해야 할 몇 가지 사항 :

초기 if-elif 절은 즉시 값을 반환하므로 else (그리고 심지어 elif)를 거기에 감쌀 필요가 없습니다.

if n in coins:
    known_results[n] = 1
    return 1
if known_results[n] > 0:     
    return known_results[n] 
for i in [c for c in coins if c<=n]:
    .
    .

같은 일을 성취하고 있습니다.

파이썬에서는 단일 명령문으로 여러 할당을 수행 할 수 있습니다.

known_results[n] = min_coins = count

제쳐두고 타입 힌트를 사용하여 값과 매개 변수를 더 이해하기 쉽게 만들 수 있습니다. 함수 정의 만 읽고 있었다면 무엇을해야하는지 전혀 몰랐을 것 known_results입니다.

3 JörgWMittag Oct 05 2020 at 05:23

코드를 복사하여 편집기에 붙여 넣으면 즉시 81 (!!!) 오류와 경고가 표시됩니다. 공정하게 말하면, 여러 개의 linter가 구성되어 있기 때문에 이들 중 일부는 중복됩니다. 그러나 그중 약 20 개가 실제입니다.

PEP8 위반

Python 커뮤니티에 대한 표준 커뮤니티 코딩 스타일은 Python Enhancement Proposal 8 – Style Guide for Python Code에 정의되어 있습니다. 당신은해야한다 항상 PEP8의 지침을 따르십시오. PEP8 위반 사항을 표시하고 자동 수정하는 도구가 많이 있습니다.

다음은 제 편집자가 플래그를 지정한 몇 가지입니다 (자동으로 수정되었으므로 한 가지 작업을 수행 할 필요가 없습니다).

쉼표 뒤 공백 : 쉼표 를 사용하는 거의 모든 곳에서 공백없이 모든 것을 함께 뭉칩니다. 쉼표 뒤에 공백이 있어야합니다.
연산자 주위에 공백 : 이항 중위 연산자의 양쪽에 공백이 있어야합니다. 때로는 그렇게하고, 때로는하지 않습니다.[c for c in coins if c<=n]
들여 쓰기는 4 개의 공백이어야합니다 . 첫 번째 수준의 들여 쓰기에는 5 개의 공백을 elif사용하고 7을 사용 하는 경우를 제외하고 두 번째 수준에는 3 개의 공백을 사용합니다.
앞에 2 개의 빈 줄이 else:있습니다. 일반적으로 함수와의 간격은 빈 줄 1 개 여야합니다.
함수 뒤에 하나의 빈 줄이 있습니다. 함수 또는 클래스 뒤에는 빈 줄이 2 개 있어야합니다.
Docstring : 함수에는 사용법을 설명하는 독 스트링이 있어야합니다. (참고 : 위의 모든 위반 사항은 편집자에 의해 자동으로 수정되었으며 자동 수정이 불가능한 유일한 위반 사항입니다.)

일관성

일관성을 유지하는 것이 매우 중요합니다. 사람들이 당신의 코드를 읽고 당신이 두 가지 다른 방법으로 똑같은 일을 할 때, 그들은 당신이 그들에게 무언가를 말하고 싶다고, 그 차이가 어떻게 든 의미가 있다고 자동으로 가정 할 것입니다.

위에서 몇 가지 불일치에 대해 언급했습니다. 예를 들어 연산자 주위에 공백을 사용하는 경우도 있지만 사용하지 않는 경우도 있습니다.

스타일 가이드를 믿지 않더라도 최소한 자신과 일관성을 유지해야합니다.

린터

자동 수정 기능이있는 린터를 사용해야합니다. 편집기에서 "저장"을 누르면 앞서 언급 한 81 개의 오류와 경고 중 78 개가 자동으로 수정되어 3 개만 남습니다 (이 중 하나는 중복 된 것입니다. 제가 언급했듯이 여러 개의 linter가 구성되어 있기 때문입니다).

위에서 언급했듯이 자동 수정할 수없는 유일한 PEP8 위반은 누락 된 문서입니다.

다른 나머지 문제는 이미 언급 한 무언가 hjpotter92의 대답 : 당신이 직접 반환 이후 if는 필요가 없다 elif. 을 제거 el하면 else.

중복 문

처음 if에는 할당 known_results[n]했지만 즉시 할당 합니다 return 1. return이 함수의 실행 이 종료되고 함수에 known_results로컬이기 때문에이 변수를 더 이상 사용할 수있는 방법이 없으므로 할당이 필요하지 않고 제거 할 수 있습니다.

중복 할당

또한 hjpotter92의 답변에서 언급했듯이 루프 if내부 분기 의 두 가지 할당은 for연결될 수 있습니다.

진실성 / 허위성

에서 elif조건, 당신은 있는지 확인 known_results[amount]보다 크다 0. 0으로 초기화하고 더하기 만하기 때문에 의미 론적으로 수행하는 작업은 기본적으로 값을 입력했는지 확인하는 것입니다. Python에서는 0거짓 값이므로를 확인하는 대신 known_results[amount] > 0간단히 확인할 수 있습니다. known_results[amount].

명명

n그리고 c매우 설명 이름이 아니다. 이러한 변수의 의도를 더 잘 드러내는 이름을 찾으십시오. 예를 들어 및 로 n이름이 변경 될 수 있습니다 .amountccoin

사실, 당신은 질문에 대한 귀하의 의견에 썼습니다 .

n 동전 교환을 생성해야하는 금액입니다.

코드 나이 경우 코드 아래에서 이와 같은 주석을 작성해야한다면 이름이 충분하지 않다는 좋은 신호입니다. 만약 당신이 n금액 과 같은 것을 말해야한다면 그것은 n라고 불러야 하는 좋은 표시입니다 amount. 왜냐하면 당신은 그것이 금액이라고 설명 할 필요가 없기 때문입니다!

i 것이다 루프 인덱스에 허용 될 수 있지만, 여기에서 인덱스 아니다. 컬렉션이나 루프 인덱스에 대한 인덱스가 아니라 컬렉션의 요소입니다. 실제로는 coin헷갈릴 수 있지만 다시 호출 할 수 있습니다.

그것에 대해 생각하면 아마도 coins호출 되어야 denominations하고 .cdenomination

또한 단순히 동전의 수가 아니라 변경에 대한 실제 동전 coin_change을 계산하기 위해 호출되는 함수를 기대합니다 .

데이터 유형

동일한 교단을 여러 번 지정하는 것은 의미가없고 교단의 순서는 중요하지 않기 때문에 교단은 목록이 아닌 Set (또는 변경되지 않았기 때문에 FrozenSet) 일 수 있습니다.

아니면 순서가 중요합니까? 실제로는 명확하지 않으며 실제로 중요하다면 일부 문서에서 도움이 될 수 있습니다.

마찬가지로, known_results아마 될 더 많은 의미가 있습니다 defaultdict.

유형 주석

Python 3는 2008 년 첫 번째 릴리스 이후 (함수) 유형 주석과 잠시 동안 변수 주석을 지원합니다. 최근에는 typing미리 정의 된 유형 의 모듈이 추가되었습니다. 또한 Python 용 Mypy 정적 유형 검사기가 있습니다.

문서화를 위해서라도 이러한 도구를 고급으로 사용하는 것이 좋습니다.

API

known_results(재귀 적) 구현의 개인 내부 구현 세부 사항입니다. 재귀 호출에서 상태를 유지하는 것이 유일한 목적인 누산기입니다. 공개 API의 일부가되어서는 안되며, 호출자에게 여기에 인수로 무엇을 전달할지 알도록 강요해서는 안됩니다.

상기 적어도 , 당신은 호출자가되지 않습니다 그래서, 그것을 기본 인수를 선택적 매개 변수를해야 이 그것을 통과 :

def minimum_number_of_coins_for_change(amount: int, denominations: Set[int]) -> int:
    def minimum_number_of_coins_for_change_rec(
        amount: int, known_results: DefaultDict[int, int]
    ) -> int:
        pass # …

그러나 함수형 프로그래밍을 할 때 재귀 함수의 인수로 누산기를 전달하는 주된 이유는 함수형에서는 상태를 변경할 수 없기 때문에 함수 호출 스택의 인수는 매우 소수의 장소 중 하나입니다. 상태를 유지할 수 있습니다. 그러나 known_results어쨌든 변경 하고 있으므로 인수로 전달할 필요가 없으며 재귀 함수 외부에서 정의하는 것으로 충분합니다.

def def coin_change(amount, denominations, known_results=[0] * (amount + 1)):

그러나 실제로는 호출자 에게 실수로 잘못된 인수를 전달할 기회 를 주지 않아야합니다 . 매개 변수 목록에서 완전히 제거하는 것이 좋습니다.

재귀 중 상태 유지 목적으로 추가 매개 변수를 도입하는 표준 방법은 재귀에 대한 새 중첩 함수를 도입하고 올바른 인수를 사용하여 외부 함수에서 호출하는 것입니다. 이 같은:

def minimum_number_of_coins_for_change(amount: int, denominations: Set[int]) -> int:
    known_results: DefaultDict[int, int] = defaultdict(int)

    def minimum_number_of_coins_for_change_rec(amount: int) -> int:
        min_coins = amount

        if amount in denominations:
            return 1

        if known_results[amount]:
            return known_results[amount]

        for coin in [
            denomination for denomination in denominations if denomination <= amount
        ]:
            count = 1 + minimum_number_of_coins_for_change_rec(
                amount - coin
            )
            if count < min_coins:
                known_results[amount] = min_coins = count

        return min_coins

    return minimum_number_of_coins_for_change_rec(amount)


denominations: Set[int] = {1, 2, 3}
amount = 5

print(minimum_number_of_coins_for_change(amount, denominations))

불행히도 코드에는 여전히 두 가지 PEP8 위반이 있습니다. 너무 긴 줄입니다. 이 문제를 해결하는 데는 여러 가지 다른 방법이 있기 때문에 여기에 남겨 두겠습니다. 그 중 하나는 더 나은 이름입니다.

API, pt. 2

당신이 계산하고 싶은 금액이 교단보다 훨씬 더 자주 변화에 대한 변화를 계산하는 것 같습니다. 따라서 coin_changer특정 종파를 가진 객체 를 가지고 그 종파에 대한 변화를 여러 번 계산할 수있는 것이 합리적 일 수 있습니다. 이 같은:

from collections import defaultdict
from typing import DefaultDict, Set


class CoinChanger:
    def __init__(self, denominations: Set[int]):
        self.denominations = denominations

    def minimum_number_of_coins_for_change(self, amount: int) -> int:
        known_results: DefaultDict[int, int] = defaultdict(int)

        def minimum_number_of_coins_for_change_rec(amount: int) -> int:
            min_coins = amount

            if amount in self.denominations:
                return 1

            if known_results[amount]:
                return known_results[amount]

            for coin in [
                denomination
                for denomination in self.denominations
                if denomination <= amount
            ]:
                count = 1 + minimum_number_of_coins_for_change_rec(amount - coin)
                if count < min_coins:
                    known_results[amount] = min_coins = count

            return min_coins

        return minimum_number_of_coins_for_change_rec(amount)


denominations: Set[int] = {1, 2, 3}
amount = 5

coin_changer = CoinChanger(denominations)

print(coin_changer.minimum_number_of_coins_for_change(amount))

코드를 클래스를 포함하는 모듈로 바꾼 가장 최근에는 누군가가 모듈을 가져 왔기 때문에 맨 아래에있는 테스트 코드가 실수로 실행되지 않도록해야합니다. 일반적으로 이러한 코드는 항상__main__ 가드 로 래핑 되어야합니다 .

if __name__ == '__main__':
    denominations: Set[int] = {1, 2, 3}
    amount = 5

    coin_changer = CoinChanger(denominations)

    print(coin_changer.minimum_number_of_coins_for_change(amount))

이상적으로는 전혀 존재하지 않아야하지만 별도의 테스트 모듈에서 적절한 단위 테스트 여야합니다. (그리고 빈 교단, 0의 금액, 음수 금액, 변경이 불가능한 금액과 교단의 조합 등과 같은 코너 케이스를 포함하여 더 많은 테스트가 있어야합니다.)