교재에서 설명하는 간결한 코드 작성에 대해...

  • seunghun
    seunghun

    이제 막 '알고리즘 문제해결전략' 책을 구매해서 공부하고 있는 독자입니다.
    아직 학생이고 부족한 점이 많은 초보자라 고수분들께 도움을 청하고 싶습니다.

    '보글게임'이라는 문제를 먼저 완전탐색으로 제가 코드를 작성했고,
    책의 코드와 비교하는 과정에서 의문이 생겨 질문드립니다.
    (정확히 말씀 드리면 책 152쪽에 나온 내용에 대해)

    저도 나름대로 간결하게 작성하려 노력했다고 생각하지만 분명 책에서 저자분이 제시한 코드와는
    당연히 차이가 크다고 생각하는데 정확하게 어떤 부분에서 있어서 책에 있는 코드가 더 효율적인지
    아직 경험도 많지 않고 해서 판단하는데 어려움이 많습니다.

    *우선, 제가 작성한 코드입니다.

    bool Select_ch(int x, int y, const char* word, const char (*box)[5])
{
  word++;  //여기서 입력된 글자를 중심으로 8방향에서 다음글자를 찾습니다.
  x -= 1;  //좌표는 북서쪽을 시작으로 합니다.
  y -= 1;

  if (*word == '\0')  //찾으려는 글자가 '\0'이라면 모두 찾았다는 말이니 true반환
    return true;

  for (int i = 0; i < 3; ++i) { //여기서 부터 차례대로 8방향을 모두 찾기 시작
    for (int j = 0; j < 3; ++j) {
      if (x + i < 0 || y + j < 0 || x + i > 4 || y + j > 4 || 
           (i == 1 && j == 1))
 //앞의 4가지의 게임판 범위를 벗어난 경우와 다음 줄의 정중앙의 경우를 예외처리
            continue;
      if (*word == box[x + i][y + j]) { //찾는 글자가 일치 한다면 
         if (Select_ch(x + i, y + j, word, box)) { 
            //재귀호출로 다음 글자를 탐색합니다.
              return true;
         }
      }
    }
  }

  return false;
}

    첫번째로, 입력이 잘못되거나 버뮈에서 벗어난 경우도 기저 사례로 택해서
    맨 처음에 처리한다는 것인데, 책의 코드와 비교하면 위의 굵은 글자가 주석으로 달린 부분이
    맨 앞으로 올 것입니다. 그러면 함수를 호출하는 시점에서 이런 오류를
    검사할 필요가 없다는 것은 이해가 됩니다. 하지만, 이것은 어차피 검사해야할 부분을
    앞으로 당긴것 밖에 안되지 않나 하는 의문이 듭니다. 책에서는 반복적인 코드를 제거하는 데
    큰 도움이 된다고 하나 어떤 의미에서 반복적인 코드를 줄여주는지 모르겠습니다. 그냥 똑같이
    판별해야 하는 문장을 앞으로 당긴 것 뿐이라면 단순 처리 순서 이동이니 중복이라 할 수 없고,
    아니면 반복문안에 속해서 반복해서 처리되니 그것이 문제라는 말인가요? 그런데 또 생각해보니
    그게 문제라면 어차피 완전탐색으로 전부 다 탐색을 하는 것이라면 하나 하나 일일이 탐색해
    가면서 재귀함수를 호출하여 시행하는 것 보다 반복문에서 해결 하는 게 낫지 않을까 생각이
    듭니다. 단순하게 함수를 호출하는 과정보단 if문을 시행하는 속도가 빠르겠다는 생각에서 입니다.

    두번째로, 다음 칸의 상대 좌표 목록을 함수 내에 직접 코딩해 넣은 것이 아니라
    별도의 변수로 분리해 낸 점도 참고하라고 하는데, 이 점은 속도보다 단순히 보기에
    간결하다는 말일까요? 저는 제가 작성한 코드이게 판단이 잘 서지 못하는 것 같습니다.

    분명, 제 코드가 간결성에서 책에 제시한 부분을 따라가지 못한다고 생각은 합니다만,
    타당한 이유가 제 능력선에선 판단이 잘 서지 않습니다.
    부디, 초심자가 이해하기 쉽게 이유를 설명해주시면 감사하겠습니다.

    감사합니다!


    10년 전
8개의 댓글이 있습니다.
  • Being
    Being
    1. 이러한 탐색은 결국 현재 상태에서 다음 상태를 어떻게 구성할 것인지를 코드로 작성해내는 것입니다. 이 경우 8방향으로 단순히 이동하는 것이지요? 이런 경우는 책의 코드건 질문자님 코드건 반복문의 형태로 묶어낼 수 있습니다.
    2. 그런데 다음 상태를 구성하는 방법이 복잡하거나 혹은 너무 단순하여 반복문의 형태로 구성하기 곤란한 경우가 있습니다. 위의 예에서 만약 8방향이 아니라 2방향만 찾는 상황이라고 가정하면 반복문을 쓰기보다는 같은 코드를 늘여서 쓰겠지요? 아니면 여러 복잡한 조건에 따라 현재 상황에 맞추어 가능한 행동들이 정의될 수도 있겠지요. 이런 경우처럼 반복문으로 나열하지 못하면 중복된 코드가 발생하는 것이구요, 반복되는 코드의 단점이야 잘 아시는 듯 해서 설명은 생략하겠습니다.
    3. 두 번째 질문은 취향 문제일 수 있는데요, 정리하면 규칙을 코딩할 것인가, 규칙의 결과를 코딩할 것인가의 문제입니다. 결과를 코딩하게 되면 그 결과가 쨌든 상수이다보니 실수할 수 있다는 단점이 있는 반면에, 그 결과가 사람이 보기에 자명하다면 가독성이 더 뛰어날 것이고 (이 경우는 거의 아닙니다만) 성능 상의 우위도 있겠지요. 규칙을 코딩하는 건 코드가 조금 길어질 수 있지만 규칙이 복잡한 경우에 훨씬 더 뛰어난 방식이지요. 결론은 케바케입니다. 그러나 저라면 요정도까지는 그냥 배열에 넣었을 것 같아요.

    10년 전 link
  • Being
    Being

    핸드폰이라 생각이 잘 전달됐는지 모르겠네요 ㅎㅎ


    10년 전 link
  • seunghun
    seunghun

    저도 핸드폰으로 지금 답장을 봤습니다ㅋ
    우선 답장 정말 감사합니다. 역시 그랬던 경험조차 없어...이해가 어려웠습니다. 어느 정도 감이 오긴 하는데, 죄송하지만 2번에 써주신 내용에 대해 한 번만 더 질문 드리면 혹시 구성방법이 복잡해서 반복문으로 표현이 어렵다면 그 조건들이 길게 나열될것인데, 기저사례로 뽑아내서 선두에 처리한다 하더라도 똑같이 길게 나열되지 않을까요?; 제가 확실하게 이해를 하지 못 했나요?...;


    10년 전 link
  • 일루
    일루

    첫번째 질문의 경우 일관성만 있으면 됩니다. 어떤 종류 체크는 함수 시작때 하기로 했고 어떤 종류 체크는 (재귀)호출 전에 하기로 정했으면 그렇게 지켜주면 되겠습니다.

    코드의 깔끔함 측면에서는 재귀호출을 하는 부분이 많은 경우 앞쪽에 경계조건을 몰아넣는 편이 낫겠지요. 지금은 한 군데라서 어디 써도 상관없을 것이고요.

    두번째 질문은 지금 코드도 괜찮은것 같구요, 대신 x y는 건드리지 않고 대신 i j를 -1부터 1까지 찾겠습니다. (변수 이름도 아마 dx dy 쪽이 직관적일듯 하네요)


    10년 전 link
  • JongMan
    JongMan

    일단 "어떤 것이 더 좋은 코드인가"이와 같은 문제에는 정답이 없다는 점을 말씀드리고 싶고요. 각자 자신의 기준이 있고 그 기준에 잘 맞는 코드가 좋은 코드이지요. ^^; 저는 제 기준을 설명할 뿐 그 기준이 유일한 최고의 기준이라고 생각하진 않습니다.

    그런 맥락에서 제 생각을 말씀드리면

    1. 범위 처리에 관해: 함수를 호출하는 곳은 항상 두 군데 이상이지요. 재귀 호출을 시작하는 외부 함수(이를테면 main)와 재귀 호출 내부가 있으니까요. 이 문제에서는 상관 없을수도 있지만, 문제에 따라서는 함수를 호출하기 전에 조건을 확인해야 할 경우 이 부분을 두 번 구현해야 할 수도 있겠죠. 반면 함수 내부에 구현하면 한 번만 해도 될 겁니다.
    2. 상대 좌표 목록은 개인적인 선택인데, 별도의 배열에 분리하는 방식이 코드 자체는 더 간결해서 저는 선호합니다. 왜 영문 작문을 배울 때 문장의 난이도가 너무 높아지는 것을 막기 위해 긴 단어의 수를 세는 등의 간단한 기준이 있잖아요. 예를 들어 보여주신 코드에서는 for 안에 for 안에 if 안에 if 들이 중첩되어 들어 있는데, 이것을 for 한개, if 한개 등으로 줄여서 쓸 수 있다면 더 간결해지겠지요. 어떻게 말하자면 "어떤 점들로 이동할 수 있는가"의 문제와 "주변의 점을 순회하면서 그 중 답을 찾는" 문제로 원래 문제를 나눈 것이라고 할 수도 있고요. 그러면 각각의 부분들을 확인하는 것은 더 간단해지지요. 이 문제의 경우 워낙 간단하니 어떻게 짜도 큰 차이가 없을 수 있지만, 경우에 따라선 큰 차이가 될 거라고 생각합니다.
    3. 별개로 작성하신 코드에서 제가 고칠점을 찾는다면 위에 일루님이 말씀해 주신 대로 x y가 있는데요. 여기에서 1을 빼줌으로 인해서 x y가 갖는 값의 의미가 내가 현재 어디의 코드를 수행하고 있는지에 따라 달라지게 되지요. (함수 호출할 때는 좌표, for 문에 들어갈 때는 현재 칸 왼쪽 위의 좌표) 이렇게 비일관적인 정의는 혼란을 불러오기 쉽기 때문에 피하는 것이 좋겠죠.

    10년 전 link
  • seunghun
    seunghun

    아.. 그렇군요!
    많은 배움이 됐어요.
    자세한 답변 정말 고맙습니다^^;ㅋ


    10년 전 link
  • Being
    Being

    워낙 다들 잘 정리해 주셔서 사족일 것 같지만, 조건 검사를 각 동작마다 하는 경우를 의사 코드로 표현하면 다음과 같습니다.

    함수 풀기(현재_상태):
    현재_상태가 기저 사례라면:
        적절한 값을 되돌린다.

    다음_상태 = 다음_상태_생성_1(현재_상태)
    만약 다음_상태가 가능한 사례라면:
        풀기(다음_상태)
    다음_상태 = 다음_상태_생성_2(현재_상태)
    만약 다음_상태가 가능한 사례라면:
        풀기(다음_상태)
    ...
    다음_상태 = 다음_상태_생성_N(현재_상태)
    만약 다음_상태가 가능한 사례라면:
        풀기(다음_상태)

    적절한 값을 되돌림

    만약 다음 상태를 생성하는 것이 단순하다면 반복문으로 묶을 수 있겠죠. 아니면 반복문으로 묶어야만 할 수도 있구요. (그게 상대 좌표 목록일 수도 있고, 다른 방식일 수도 있겠죠.)

    함수 풀기(현재_상태):
    현재_상태가 기저 사례라면:
        적절한 값을 되돌린다.

    i를 1부터 N까지 반복:
        다음_상태 = 다음_상태_생성_i(현재_상태)
        만약 다음_상태가 가능한 사례라면:
            풀기(다음_상태)

    적절한 값을 되돌림

    저렇게 가능한 상태인지를 판단하는 조건이 한 곳에 묶일 수 있다면 기본적으론 어느 쪽에 붙여도 큰 문제가 없다고 봅니다. 그런데 위와 같이 묶이지 못하고 어떤 상태가 가능한 상태인지를 판단하는 조건이 여러 곳에 분리되는 경우는 공통된 로직으로 묶고 중복되는 코드를 제거하는 것이 일반적으로 훨씬 깔끔합니다.

    함수 풀기(현재_상태):
    현재_상태가 불가능한 사례라면:
        적절한 값을 되돌린다.
    현재_상태가 기저 사례라면:
        적절한 값을 되돌린다.

    풀기(다음_상태_생성_1(현재_상태))
    풀기(다음_상태_생성_2(현재_상태))
    ...
    풀기(다음_상태_생성_N(현재_상태))

    적절한 값을 되돌림

    물론 아주 미세한 성능 측면에서의 문제를 고려하면 각각 서술하는 것이 유리한 경우도 있습니다. 예를 들어 격자에서 8방향으로 움직이는 경우를 생각해 보면, (-1, -1)로 가는 경우는 왼쪽이나 위쪽의 경계를 넘어서지는 않는지, 즉 각 좌표가 0이 아닌지만 검사하면 되겠죠. 그렇지만 이러한 로직은 중복되는 부분이 굉장히 많을 것이고, 중복되는 코드가 갖는 여러 단점을 희생하고서라도 영향이 있을 때에만, 즉 올바른 상태인지 검사하는 비용이 매우 비쌀 때에만 의미가 있을 것입니다.


    10년 전 link
  • seunghun
    seunghun

    엄청 자세히 써주셨네요;
    감사합니다^^;


    10년 전 link

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