종만북을 읽으면서 궁금한점이 있습니다...

  • 코딩신
    코딩신

    안녕하세요! 책 으로 공부 잘 하고 있습니다..

    좋은책 써주셔서 감사합니다

    제가 궁금한점은..

    1권 296P 모스부호사전 정답에서

    Combination 값을 202까지 계산해놓고 시작을 하는데

    답안번호 #452226 해당 코드

    int combination(int n, int r) {

    if (n == r || r == 0) return 1;

int &ret = cache[n][r];
if (ret != -1)
    return ret;
return ret=min((combination(n - 1, r - 1) + combination(n - 1, r)),M);

    }

    이런식으로 필요한 값만 계산하게 하는게 더 효율이 좋지 않을까요??

    물론 n r이 커지면 결국에 비슷하게 계산을 할수도 있지만

    이 이유가 궁금합니다..!!

    아 질문이 하나 더 있는데

    책을 보면서 문제를 만나면 문제를 먼저 풀어보고 책을 읽어 봅니다.

    근데 보면 알고리즘도 알고리즘이지만 코드 자체가 너무 더러워서

    책을 읽으면서 자괴감이 생깁니다 제가 100줄짜리 함수 4개로 만들면

    jm북에서는 함수 한개로 몇줄안되게 만들던데............

    어떤 방식으로 연습해야 늘까요?ㅜㅜㅜ


    7년 전
1개의 댓글이 있습니다.
  • Being
    Being

    먼저 combination()의 경우 "어떻게 구현해도 무방하다"에 더 가까울 것 같습니다. 저렇게 하면 연산 횟수가 더 적은 것은 분명한 사실이나 전체 시간복잡도는 가장 큰 차수의 항으로 계산하고 또 받아들일 수 있는 최대 입력의 크기가 실질적으로 영향을 미치므로 크게 중요하지 않다고 하겠습니다. 한 가지 작은 다른 이슈를 살피자면 200정도의 규모가 아니라 몇천 개 단위가 되면 재귀적으로 구현했을 때 스택 오버플로가 발생할 가능성이 있어서 이항계수의 경우 iterative하게 구현하는 것에 실질적 이득이 있을 수 있습니다.

    깔끔하지 못한 코드를 다시 짜는 연습을 해 보는 것은 현업에서도 도움이 되는 좋은 자세입니다. 저는 코드가 깔끔하지 못한 이유가 크게 두 가지가 있다고 생각합니다. 하나는, 프로그램에 대한 아이디어가 확정되지 않고 구현 도중에 조금씩 바뀌면서 원래 의도와 새 의도가 뒤섞이는 것이고, 나머지 하나는 언어 자체의 여러 기능들에 익숙하지 않아서입니다. 이 두 가지 모두 연습을 통해 훨씬 개선될 수 있다고 믿습니다.


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.