블로그는 귀차니즘

Algorithm Traning Book - 다섯번째 문제

Algorithm 2008/06/15 23:13 귀차니스트

음 한 주가 지나가고 새로운 한 주가 시작되는 시점입니다. 뭐 이런저런 일들이 저번 주에는 많았군요. 어떻게 하다보니 필요에 의한 근무지를 경산으로 잠시 옮기게 되었습니다. 기간은 약 1달 정도로 잡고 있구요. 미완된 프로그램을 완전하게 작성하는 부분이 남았습니다. 야근이 계속 된다면 포스팅이 더뎌 질 수도 있겠군요^^.

이번 문제도 쉬운 문제입니다. 이름은 Graphical Editor이구요. 입력되는 명령을 파싱하여 구분별로 입력받은 좌표와 데이터로 간단한 데이터 조작하는 것이 문제 해결의 전부입니다. 어떻게 입력을 받고 출력을 해야 하는지 한 번 살펴보도록 하겠습니다.

입력( 제한 X와 Y 좌표는 1 <= X,Y <= 250 까지만 입력됩니다. )
I 5 6
L 2 3 A
S one.bmp
G 2 3 J
F 3 3 J
V 2 3 4 W
H 3 4 2 Z
S two.bmp
X

출력
one.bmp
OOOOO
OOOOO
OAOOO
OOOOO
OOOOO
OOOOO
two.bmp
JJJJJ
JJZZJ
JWJJJ
JWJJJ
JJJJJ
JJJJJ

대충 이런 출력형식을 띄게 됩니다. 물론 입력값에 대한 정의는 아래와 같죠.

I M N - 모든 픽셀이 M X N 이미지 크기로 됩니다. 데이터는 O로 채워집니다.
C - 모든 픽셀을 O로 채워 지웁니다.

L X Y C - (X, Y) 픽셀을 C색으로 채웁니다.
V X Y1 Y2 C - X열에 해당하는 Y1에서 Y2까지 C색으로 세로선을 그립니다.
H X1 X2 Y C - Y행에 해당하는 X1에서 X2까지 C색으로 가로선을 그립니다.
K X1 Y1 X2 Y2 C - (X1,Y1)에서 (X2, Y2) 까지 사각형을 C색으로 칠합니다.
F X Y C - (X, Y)에 해당하는 픽셀에 인접하는 같은 색의 모든 픽셀을 C색으로 칠합니다.
S Name - 파일 이름을 출력합니다.
X - 프로그램을 종료합니다.

정의는 그렇게 어렵지 않죠^^. 그래도 나름 한 가지 생각해볼 것이라면 F 커맨드가 이 중엔 제일 이겠군요. 그래도 별로 어렵지는 않으니 ^^. 재미있게 대충대충 ㅎㅎ

Graphical.cpp (Language : cpp)

#include <iostream>
#include <string>
#include <deque>
int Width, Height;
char Image[251][251];
void StringTokenizer( const std::string &Str, std::deque< std::string > &Token, const std::string &Delimiter );
void NewImage( std::deque< std::string > &Token );
void ClearImage( std::deque< std::string > &Token );
void SetPixel( std::deque< std::string > &Token );
void VerticalLine( std::deque< std::string > &Token );
void HorizonLine( std::deque< std::string > &Token );
void Square( std::deque< std::string > &Token );
void MagicWord( std::deque< std::string > &Token );
void SaveImage( std::deque< std::string > &Token );
void ExitProgram( std::deque< std::string > &Token );
void NearstFill( int X, int Y, char Color, char OldColor );
int main( int argc, char **argv )
{
char InputString[ 256 ];
while( true ) {
std::cin.getline( InputString, 255 );
std::deque< std::string > TokenContainer;
StringTokenizer( InputString, TokenContainer, "\t " );
std::string &Cmd = TokenContainer.front();
if( Cmd == "I" )
NewImage( TokenContainer );
else if( Cmd == "C" )
ClearImage( TokenContainer );
else if( Cmd == "L" )
SetPixel( TokenContainer );
else if( Cmd == "V" )
VerticalLine( TokenContainer );
else if( Cmd == "H" )
HorizonLine( TokenContainer );
else if( Cmd == "K" )
Square( TokenContainer );
else if( Cmd == "F" )
MagicWord( TokenContainer );
else if( Cmd == "S" )
SaveImage( TokenContainer );
else if( Cmd == "X" )
ExitProgram( TokenContainer );
}
return 0;
}
void StringTokenizer( const std::string &Str, std::deque< std::string > &Token, const std::string &Delimiter )
{
std::string::size_type LastPos = Str.find_first_not_of( Delimiter, 0 );
std::string::size_type Pos = Str.find_first_of( Delimiter, LastPos );
while( std::string::npos != Pos || std::string::npos != LastPos )
{
Token.push_back( Str.substr( LastPos, Pos - LastPos ) );
LastPos = Str.find_first_not_of( Delimiter, Pos );
Pos = Str.find_first_of( Delimiter, LastPos );
}
}
void NewImage( std::deque< std::string > &Token )
{
Width = atoi(Token[1].c_str());
Height = atoi(Token[2].c_str());
ClearImage( Token );
}
void ClearImage( std::deque< std::string > &Token )
{
for( int i = 0; i <= Height; ++i )
for( int j = 0; j <= Width; ++j )
Image[ i ][ j ] = 'O';
}
void SetPixel( std::deque< std::string > &Token )
{
int X = atoi(Token[1].c_str());
int Y = atoi(Token[2].c_str());
char Color = *Token[3].c_str();
Image[ Y ][ X ] = Color;
}
void VerticalLine( std::deque< std::string > &Token )
{
int X = atoi(Token[1].c_str());
int Y = atoi(Token[2].c_str());
int Y2 = atoi(Token[3].c_str());
char Color = *Token[4].c_str();
if( Y2 < Y )
std::swap( Y, Y2 );
for( int i = Y; i <= Y2; ++i )
Image[ i ][ X ] = Color;
}
void HorizonLine( std::deque< std::string > &Token )
{
int X = atoi(Token[1].c_str());
int X2 = atoi(Token[2].c_str());
int Y = atoi(Token[3].c_str());
char Color = *Token[4].c_str();
if( X2 < X )
std::swap( X, X2 );
for( int i = X; i <= X2; ++i )
Image[ Y ][ i ] = Color;
}
void Square( std::deque< std::string > &Token )
{
int X = atoi(Token[1].c_str());
int X2 = atoi(Token[2].c_str());
int Y = atoi(Token[3].c_str());
int Y2 = atoi(Token[4].c_str());
char Color = *Token[4].c_str();
if( X2 < X )
std::swap( X, X2 );
if( Y2 < 2 )
std::swap( Y, Y2 );
for( int i = Y; i <= Y2; ++i )
for( int j = X; j <= X2; ++j )
Image[ i ][ j ] = Color;
}
void MagicWord( std::deque< std::string > &Token )
{
int X = atoi(Token[1].c_str());
int Y = atoi(Token[2].c_str());
char Color = *Token[3].c_str();
char OldColor = Image[ Y ][ X ];
NearstFill( X, Y, Color, OldColor );
}
void SaveImage( std::deque< std::string > &Token )
{
std::cout << Token[1] << std::endl;
for( int i = 1; i <= Height; ++i ) {
for( int j = 1; j <= Width; ++j )
std::cout << Image[ i ][ j ];
std::cout << std::endl;
}
}
void ExitProgram( std::deque< std::string > &Token )
{
exit(0);
}
void NearstFill( int X, int Y, char Color, char OldColor )
{
if( Image[ Y ][ X ] == OldColor ) {
Image[ Y ][ X ] = Color;
if( X > 1 )
NearstFill( X - 1, Y, Color, OldColor );
if( X < Width )
NearstFill( X + 1, Y, Color, OldColor );
if( Y > 1 )
NearstFill( X, Y - 1, Color, OldColor );
if( Y < Height )
NearstFill( X, Y + 1, Color, OldColor );
}
}

깔끔하게 해보려고 했지만 일단 그냥 푸는게 더 좋을것 같아서 대충대충 했습니다. 일단 결과물이 나와야 과정이 중요하지 않겠습니까^^? 그럼 새로운 한 주 잘보세요.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Dovelet - (1) (0)	2010/03/13
Algorithm Traning Book - 세 번째 문제 (0)	2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)	2008/06/09

TAG 알고리즘 트레이닝

받은 트랙백이 없고, 댓글이 없습니다.

댓글을 달아 주세요

Algorithm Traning Book - 세 번째 문제

Algorithm 2008/06/10 23:42 귀차니스트

금방 풀어봤던 한 문제는 The Trip(여행)이라는 문제입니다. 이 것도 초반 문제다 보니 별로 어렵지는 않네요. 대략적인 문제의 개요는 여행을 가는데 여러명이 사용하는 경비를 각자 내려니 너무 귀찮다는거죠. 그리하여 각 사람마다 여행경비, 숙박비 등을 지불하게 되는데 이게 또 그냥 넘어가면 껄쩍지근 하잖습니까?^^ 그래서 돈을 나중에 서로 교환을 하여 서로 지불액수를 맞추게 됩니다.
여기서 포인트는 액수를 맞추기 위하여 이동하는 돈의 개수를 센트까지 세어라 입니다. 물론 입력은 달러 단위로 받게 되구요. 일단 입력과 출력 예제를 보겠습니다.

입력:
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01

출력:
$10.00
$11.99

TheTrip.cpp (Language : cpp)

#include <iostream>
#include <cmath>
int main(int argc, char **argv)
{
int CntInput = 0;
double CostList[1000] = {0.00,};
do{
double Average = 0.00;
double MoveCost = 0.00;
std::cin >> CntInput;
for( int i = 0; i < CntInput; ++i ) {
std::cin >> CostList[i];
Average += CostList[i];
}
if( CntInput != 0 ) {
Average /= static_cast<double>(CntInput);
double DiffCost = 0.00;
for( int i = 0; i < CntInput; ++i ) {
DiffCost = Average - CostList[i];
MoveCost += ( DiffCost > 0.00 ? DiffCost : 0.00 );
}
std::cout.precision(2);
std::cout << std::fixed << '$' << std::floor(MoveCost * 100) / 100 << std::endl;
}
}while( CntInput != 0 );
return 0;
}

이 문제도 사실 어렵지 않기 때문에 대충대충 해서 풀었습니다. 한 가지 숫자의 정밀도 출력으로 인해서 11.99가 출력되어야할 시점에 12가 출력될 수 있기 떄문에 센트까지만 이라는 힌트를 참조하여 * 100을 한 다음 / 100을 하여 내림을 시켜버리면 문제없이 출력이 됩니다.
다음 문제도 계속 풀어봐야 겠군요^^.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Dovelet - (1) (0)	2010/03/13
Algorithm Traning Book - 다섯번째 문제 (0)	2008/06/15
Algorithm Traning Book - 두 번째 문제 (0)	2008/06/09

TAG 알고리즘 트레이닝

받은 트랙백이 없고, 댓글이 없습니다.

댓글을 달아 주세요

Algorithm Traning Book - 두 번째 문제

Algorithm 2008/06/09 23:29 귀차니스트

음 뭐 책을 사놓고 도통 보지 않는 것 같아 오늘 야근 하고 돌아온 김에 잠시 봤는데 시간이 없어 많은 것을 생각하는 문제는 선택하지 못하고 아주 간단한 문제를 선택해봤습니다. 아무래도 첫 술부터 배부를 수는 없듯이 차근차근 있는 문제 그냥 연습한다 치고 하나씩 풀어보기로 했습니다.
문제의 이름은 Mine Sweeper네요. 대충 입력, 출력의 예와 코드 는 다음과 같습니다.

입력

4 4
*...
....
.*..
....

출력
*100
2210
1*10
1110

MineSweeper.cpp (Language : cpp)

#include <iostream>
int Width, Height;
char MineField[100][100];
int GetField(int col, int row)
{
if( (0 <= col && col < Height) &&
(0 <= row && row < Width )) {
return (MineField[col][row] == '*' ? 1 : 0);
}
return 0;
}
char Calculate(int col, int row)
{
if( GetField(col, row) )
return '*';
int Count = 0;
Count += GetField( col - 1, row - 1 );
Count += GetField( col - 1, row );
Count += GetField( col - 1, row + 1 );
Count += GetField( col, row - 1 );
Count += GetField( col, row + 1 );
Count += GetField( col + 1, row - 1 );
Count += GetField( col + 1, row );
Count += GetField( col + 1, row + 1 );
return '0' + Count;
}
int main( int argc, char **argv )
{
while( true ) {
std::cin >> Width >> Height;
if( Width == 0 && Height == 0 )
break;
for( int i = 0; i < Height; ++i ) {
for( int j = 0; j < Width; ++j ) {
std::cin >> MineField[i][j];
}
}
for( int i = 0; i < Height; ++i ) {
for( int j = 0; j < Width; ++j ) {
std::cout << Calculate(i, j);
}
std::cout << std::endl;
}
}
return 0;
}

복잡한 문제는 아니죠^^? 그냥 아주 간단하길래 대충 생각하고 대충 풀었습니다. 코드가 즈질 이군요 ㅎㅎ
계속해서 한 문제씩 차근차근 풀어봐야 겠습니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Dovelet - (1) (0)	2010/03/13
Algorithm Traning Book - 다섯번째 문제 (0)	2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)	2008/06/10

TAG Mine Sweeper, 알고리즘 트레이닝

받은 트랙백이 없고, 댓글이 없습니다.

블로그는 귀차니즘

'알고리즘 트레이닝'에 해당되는 글 3건

Algorithm Traning Book - 다섯번째 문제

"Algorithm" 분류의 다른 글

트랙백 주소 :: http://www.filewiki.net/tc/trackback/78

댓글을 달아 주세요

Algorithm Traning Book - 세 번째 문제

"Algorithm" 분류의 다른 글

트랙백 주소 :: http://www.filewiki.net/tc/trackback/76

댓글을 달아 주세요

Algorithm Traning Book - 두 번째 문제

"Algorithm" 분류의 다른 글

트랙백 주소 :: http://www.filewiki.net/tc/trackback/75

댓글을 달아 주세요

카테고리

달력

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

링크

« 2012/02 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29