13.1주차
실습 11
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
step 1. 문제만 풀기
문제만 푼다는 말은 class를 만들 때, 정사각형의 넓이를 구한다는 의미이다.
#include <iostream>
#include <vector>
using namespace std;
/* P11 */
class P11
{
protected:
vector<vector<int>> table;
int width;
int height;
int getArea(int top, int left);
bool isWhatIWant(int top, int left, int bottom, int right);
bool isCorrectSize(int top, int left, int bottom, int right);
public:
P11(vector<vector<int>> table);
int solution();
};
/* P11 구현 */
P11::P11(vector<vector<int>> table)
{
this->table = table;
this->width = table[0].size();
this->height = table.size();
}
int P11::solution()
{
int maxarea = 0;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
int area = getArea(i, j);
if (area > maxarea)
{
maxarea = area;
}
}
}
cout << maxarea << endl;
return maxarea;
}
int P11::getArea(int top, int left)
{
int maxarea = 0;
for (int j = left; j < width; j++)
{
for (int i = top; i < height; i++)
{
if (isWhatIWant(top, left, i, j))
{
int area = (i - top + 1) * (j - left + 1);
if (area > maxarea)
{
maxarea = area;
}
}
}
}
return maxarea;
}
bool P11::isWhatIWant(int top, int left, int bottom, int right)
{
if (!isCorrectSize(top, left, bottom, right))
return false;
for (int i = top; i <= bottom; i++)
{
for (int j = left; j <= right; j++)
{
if (table[i][j] != 1)
{
return false;
}
}
}
return true;
}
bool P11::isCorrectSize(int top, int left, int bottom, int right)
{
if ((bottom - top) != (right - left))
return false;
return true;
}
문제를 보자마자 이렇게 많은 함수를 통해서 구현한 것은 아님,,, 하지만 내가 ㅋ 늦게 정리하는 바람에 기억 복구에 살짝 어렵,,,
일단 처음에는 getArea, solution을 통해서 정사각형의 넓이를 구하고자 하였다. 하지만 class 설계에 대해서는 미래를 보아야하고, 자식 클래스에서는 딱 최소만을 구현하는 것이 목표이다. 결국, 나중에 구현할 P112 클래스는 직사각형 넓이까지 구해야되므로 이 차이를 구현할 수 있도록 함수로 쪼개어서 이와 같은 함수가 나오게 되었다.
int getArea(int top, int left);: top, left를 기준으로 width, height만큼의 넓이를 구한다.bool isWhatIWant(int top, int left, int bottom, int right);: top, left부터 bottom, right까지 모두 1인지 아닌지를 구해준다.bool isCorrectSize(int top, int left, int bottom, int right);: 정사각형인지 직사각형인지를 리턴해준다.int solution();: 인덱스 (0, 0) 부터 width, height까지 getArea를 통해서 넓이를 구하고 최대 넓이인 경우 그 값을 대입한다.
클래스를 설계할 때는 함수 이름이 중립적이어야 되며, 자식 클래스에서는 오버 라잇을 최소화해야 된다.
step 2. 직사각형 최대 넓이 구하기
#include <iostream>
#include <vector>
using namespace std;
/* P11 */
class P11
{
protected:
vector<vector<int>> table;
int width;
int height;
int getArea(int top, int left);
bool isWhatIWant(int top, int left, int bottom, int right);
virtual bool isCorrectSize(int top, int left, int bottom, int right);
public:
P11(vector<vector<int>> table);
int solution();
};
/* // 가장 넓은 직사각형 바꾸기 미션! */
/* P112 */
class P112 : public P11
{
virtual bool isCorrectSize(int top, int left, int bottom, int right);
public:
P112(vector<vector<int>> table);
};
/* P11 구현 */
P11::P11(vector<vector<int>> table)
{
this->table = table;
this->width = table[0].size();
this->height = table.size();
}
int P11::solution()
{
int maxarea = 0;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
int area = getArea(i, j);
if (area > maxarea)
{
maxarea = area;
}
}
}
cout << maxarea << endl;
return maxarea;
}
int P11::getArea(int top, int left)
{
int maxarea = 0;
for (int j = left; j < width; j++)
{
for (int i = top; i < height; i++)
{
if (isWhatIWant(top, left, i, j))
{
int area = (i - top + 1) * (j - left + 1);
if (area > maxarea)
{
maxarea = area;
}
}
}
}
return maxarea;
}
bool P11::isWhatIWant(int top, int left, int bottom, int right)
{
if (!isCorrectSize(top, left, bottom, right))
return false;
for (int i = top; i <= bottom; i++)
{
for (int j = left; j <= right; j++)
{
if (table[i][j] != 1)
{
return false;
}
}
}
return true;
}
bool P11::isCorrectSize(int top, int left, int bottom, int right)
{
if ((bottom - top) != (right - left))
return false;
return true;
}
/* P112 구현 */
P112::P112(vector<vector<int>> table) : P11(table)
{
;
}
bool P112::isCorrectSize(int top, int left, int bottom, int right)
{
return true;
}
P11 을 상속받은 P112 클래스는 직사각형 최대 넓이를 구할 수 있도록 만들어진 클래스이다. 우선 P11 클래스를 상속받았으므로 부모 클래스의 생성자를 사용하여 width, hegiht를 초기화한다.
P112 클래스에서는 최소한만 오버라이딩을 하면 좋다. 그렇다면 P11 에서 재활용할 수 있는 것을 따져보자면, solution 함수와 getArea 함수와 isWhatIWant 함수를 사용할 수 있다.
결국 연속적으로 1이 나온 부분이 직사각형인지 정사각형인지 구별을 하는 isCorrectSize 함수만 오버라이딩을 해주면 된다. 자식 클래스에서 재정의한 내용에 대해서 사용하기 위해서 virtual을 붙혀주었다.
결과적으로 봤을 때, 부모 클래스에서는 최대한 많은 것을 정의를 하고, 자식 클래스에서는 최소한만 오버라이딩을 하는 것이 목표이다. 자식 클래스는 진짜 개간단하도록!
먼 미래를 봐야된다. 교수님 스타트업 썰,,,ㅋ 아이돌들이 나중에 잘 될 수도 있으니 싸인을 받아놓고 싶다.
함수나 변수 이름조차 좀더 중립적으로 가져간다. 클래스 디자인 할 시에 앞으로의 상속을 염두해두어서 상속에 친화적인 코드로 만든다. 즉, 예를 들어서 isWahtIWnat에 굳이 if 문 안에 함수를 넣어서 확인하는 것. 사실 저거는 직사각형까지 고려한 코드가 된다. 상속시에 유리한 코딩을 미리밀 하는게 좋다.
수정을 할수록 코드가 compact해지고 예뻐진다. 심미안이 생긴다. 마음으로 아름다움을 느끼는 눈… 코드에 대한 심미안이 생긴다.,,,
main
int main()
{
P11 myp11( { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 1, 0 } } );
myp11.solution();
P112 myp112( { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 1, 0 } } );
myp112.solution();
}
iostream
C++과 다른 언어의 결정적으로 다른 것이 stream이다.
Input & Output -> 컴퓨터는 바이트 단위로 계산을한다. 이런 바이트 단위의 input과 output은 바이트의 일차원적인 흐름이다. 흐름이라는 단어에 꽂혀서 stream이라고 한것이다.
폰노이만 방식에서는 CPU에서만 데이터를 처리한다. 즉, 모든 길은 CPU를 통한다. CPU 입장에서 들어오는게 input, 나가는게 output이다. 근데 여기서 1 바이트씩 왔다갔다 하는 것이 너무 비효율적이야. 셔틀을 타고 왔다갔다 하고 싶어. 셔틀이 꽉 차면 출발하는 것이 훨씬 효율적이란 말이야. 이 셔틀이 버퍼라는 것이다. 버퍼에 데이터가 꽉 차면 그때 output하고 버퍼에 데이터가 꽉 차면 input하는 식으로.. 해서 스트림이라는 개념이 도입하게 된것이다.
[결] CPU와 IO는 속도가 너무 달라. 그래서 효율성을 위해서 퍼버를 만들어서 모아서 input, 모아서 output하는 개념이다.
stream의 개념을 다 함수로 표현하는데 C++은 «의 경우는 output으로 »는 input으로 표현하였고, 우리는 오퍼레이터 오버로딩을 통해서 확장시켜줄 수 있다.
지금까지는 standard input, standard outpu을 많이 다뤘다. 이것 뿐만이 아니라 이걸 확장해서 파일, 네트워크, 데이터가 오고가는 다양한 장치들에게 모두 적용할 수 있다. 하나의 오퍼레이터를 통해서 파일, 네트워크, 데이터 등의 다른 형식이 모고 갈 수 있는 것을 다형성이라고 한다.
저장 장치에 저장하는 것을 파일이라고 하는데 파일은 읽을수도 있고 쓸 수도 있다. 파일도 기본적으로 바이트가 일렬로 저장된다. 이게 그냥 바이트의 나열인데 여기서 어떻게 해석하는지가 문제이다. 바이트의 나열을 해석하는 것은 전적으로 응용 프로그램의 역할이다.
파일을 CPU로 들어가는 것 역시 stream 개념으로 보는 것은 담 시간에,,,,ㅎ
댓글남기기