[진우님] BOJ-1793 코드 리뷰

[psychology50]

타일링

두 분이 쓰신 코드랑, 풀이에 도달하는 흐름이 비슷해서 이슈도 동일한 내용으로 첨부하겠습니다. (귀찮아서가 아니예요.)

• 이 문제의 접근법은 굉장히 다양합니다.
  • 동적 계획법만으로 풀기 (진우님께서 사용한 기저 사례를 채워넣고 bottom-up으로 계산하는 방법입니다.)
  • 수학적으로 분석한 후 dp를 적용하는 방법
  • 분할 탐색에 dp를 적용할 수도 있습니다.

수학적으로 풀기

• 문제를 풀기 위해 접근법 중 그림을 그려보는 건 좋은 전략 중 하나입니다.
• 제가 예전에 이 문제를 풀 때의 아이디너는 블럭을 하나씩 빼서, 기저 사례에 도달하면 어떨까?였습니다.
• 그렇게 되면, 문제는 피보나치 수열과 비슷한 구조를 가지게 되며, 진짜 점화식을 도출해서 해결할 수 있습니다.
• 여기서 최적화를 하려면 공통 부분을 계산해주면 되겠죠?

분할 탐색 (사실 해보진 않았고, 그냥 지금 떠오른 아이디어 입니다.)

• 길이 n(짝수라고 가정)을 n/2, n/2로 divide하고, 이를 반복하여 기저 사례까지 내려갑니다.
• 기저 사례(0, 1, 2)에 도달했을 때, merge를 시작합니다.
• 단, merge를 할 때 단순히 더하기 연산만 하면 안 되고 몇 가지 케이스가 발생할 수 있음을 고려하여 추가 연산이 필요할 겁니다.
• 이를 기반으로도 동적 계획법을 적용할 수 있겠네요.

• 동적 계획법이라는 건, 어떠한 알고리즘이 아닌 말 그대로`최적화를 어떻게 할 거냐를 묻는 거라고 보시면 편합니다.
• 최적 부분 구조
  • 각 부분 문제의 최적해만으로 전체 문제의 최적해를 구할 수 있을 때 성립합니다.
• 또한 메모이제이션을 적용할 수 있는 경우는 참조적 투명 함수일 때만 가능하나는 점에 유의하시면 됩니다.
  • 참조적 투명 함수: 입력이 고정되어 있을 때, 그 결과가 항상 같은 함수

  int counter = 0;
  int count() {
     return ++counter;
  }
  

시간 복잡도는 얼마일까요?

• 동적 계획법 문제의 시간 복잡도를 구한다는 건, 별로 즐겁지도 않고 쉬운 일도 아닙니다.
• 그래도 이 정도 수준의 문제일 때 조금 해보셔야 나중에 감이 오실 것 같아서 여쭤봅니다.
• 힌트는 (존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)입니다.