제가 구현한 방식이 분할 정복이 맞을까요?

작성한 질문수 4

1

안녕하세요 neo님 ㅎㅎ

string recur(int y, int x, int l) {
  // 종료조건
  if(l == 1) {
    return mp[y - 1][x - 1];
  }
  
  string acc = "";

  // 일단 하위 함수를 다 호출해버리고 가장 하위함수에서 올라온다.
  acc += recur(y - l / 2 , x - l / 2, l / 2);
  acc += recur(y - l / 2, x, l / 2);
  acc += recur(y, x - l / 2, l / 2);
  acc += recur(y, x, l / 2);

  // 하위에서 올라온 값이 같을 때 처리
  if(acc == "0000") return "0";
  else if(acc == "1111") return "1";
  // 다를 때는 괄호를 추가해서 처리
  else return "(" + acc + ")";
}

코드리뷰는 다음과 같습니다.

기저사례 : good

l을 반으로 쪼개면서 함수호출 : good

해당 값을 기반으로 0, 1 또는 나눠서 처리. : good

저는 재귀함수를 작성할 때 하위함수를 무조건 호출하고, 가장 하위함수의 결과부터 시작해서 올라오는 방식으로 코드를 짰습니다.

이런 방식을 분할 정복이라고 할 수 있는건가요?

>> 네 함수가 쪼개진 매개변수를 받아 각각의 로직을 수행해서 결국은 global한 해를 갖게 됩니다. 분할정복입니다.

위의 방식으로 코드를 작성하기 위해서 시작 지점을 범위의 우측 하단으로 설정했습니다. 그래서 맨 처음 재귀함수를 호출할 때, N을 시작 지점으로 입력받게 됩니다.

>> 네 괜찮습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.