점선이 현재 구하고자 하는 영역이고 초록색으로 되어있는 부분들이 이미 구해진 영역이라고 했을때 - 제 생각에는 일부분만 겹친 영역은 제외하고 - 점선 영역안에서 모든 부분이 구해져있는 부분 영역들만 중복 계산을 없애는데 쓸려고 합니다.
- 겹친 영역이 있으면 둘 중에 하나를 선택해야합니다.
- 그런데 생각해보니 가장 큰 영역을 선택하고 나머지 더할 수 있는 구해진 부분 영역들을 더하게 만들면 부분 영역 중 가장 큰 사각형은 1개만 쳤을때는 가장 클수도 있지만 그 사각형을 선택하기 위해 겹쳐지는 다른 사각형들을 포기해야합니다. 만약 포기하는 다른 사각형들의 총합이 1개만 쳤을때 가장 큰 사각형의 영역보다 넓다면 가장 큰 사각형을 포기하고 다른 사각형들을 택하는게 결과적으로 유리합니다. 이 방향이 맞을지와 함께 혹시 최적화를 더 진행한다면 어떻게 진행할수 있을까요?
rancho974 2년 전
점선이 현재 구하고자 하는 영역이고
초록색으로 되어있는 부분들이 이미 구해진 영역이라고 했을때
- 제 생각에는 일부분만 겹친 영역은 제외하고
- 점선 영역안에서 모든 부분이 구해져있는 부분 영역들만 중복 계산을 없애는데 쓸려고 합니다.
- 겹친 영역이 있으면 둘 중에 하나를 선택해야합니다.
- 그런데 생각해보니 가장 큰 영역을 선택하고 나머지 더할 수 있는 구해진 부분 영역들을 더하게 만들면
부분 영역 중 가장 큰 사각형은 1개만 쳤을때는 가장 클수도 있지만 그 사각형을 선택하기 위해 겹쳐지는 다른 사각형들을 포기해야합니다.
만약 포기하는 다른 사각형들의 총합이 1개만 쳤을때 가장 큰 사각형의 영역보다 넓다면
가장 큰 사각형을 포기하고 다른 사각형들을 택하는게 결과적으로 유리합니다.
이 방향이 맞을지와 함께
혹시 최적화를 더 진행한다면 어떻게 진행할수 있을까요?