직사각형 검색 결과

해당 글 2건
정사각형 직사각형 문제 : A is a B 관계인데 상속을 쓰기에는..

상속과 구성은 많이 들어봤을 법한 주제입니다. A is a B일 때 상속을 쓰라고 합니다. 예를 들자면, 개와 동물은 그러한 관계의 한 예입니다. 몇 레퍼런스를 더 찾아보던 중에, 이 질문글을 보게 되었습니다. 그리고 좋은 답변글들을 보면서, 정사각형과 직사각형, 그리고 타원과 원도 A is a B의 관계에 있다는 것을 알게 되었습니다. 그리고 이 문제와 리스코프 원칙과 관련이 있다는 것도 알게 되었습니다. 아래 예제를 보겠습니다. 정사각형은 직사각형을 상속합니다. square 생성자는 부모 rect의 생성자를 호출하는데, 넘기는 변수는 h, h입니다. 높이와 너비가 같기 때문입니다. rect 클래스입니다. 여기에는 getArea 메서드만 있습니다. 이 프로그램의 출력 결과는 25입니다. 그런데, 사실 ..
디자인패턴 2020. 11. 2. 03:08
배열에서 가장 큰 직사각형 구하기 : 관찰을 통해 풀어봅시다.

(2차원) 배열에서 가장 큰 정사각형을 찾는 것은 dp로 해결할 수 있습니다. 문제를 조금 바꿔보겠습니다. 가장 큰 직사각형은 어떻게 구해야 할까요? 문제의 제한이 딱 하나 바뀌었을 뿐인데, 난이도는 4단계 정도 높아졌습니다. 이 문제를 보도록 하겠습니다. 문제를 요약하면 다음과 같습니다. n이 범위는 1이상 2000 이하입니다. 시간 제한이 3초인 것을 감안했을 때, O(n^2)나 O(n^2logn) 정도에 풀어야 한다는 결론을 얻을 수 있습니다. 그런데, 후자는 생각보다 상수 줄이기가 빡빡하기도 하고 제가 시도해 본 방법이 아니므로, 저는 전자로 시도해 보겠습니다. 먼저 간단한 상식 아닌 상식을 통해서 관찰을 하나 해 보도록 하겠습니다. 길이가 3, 4, 2, 6인 높이 1짜리 직사각형이 있습니다. ..
자료알고/알고리즘 2020. 10. 18. 17:40