블로그는 귀차니즘

  알고리즘 테스트 사이트 인 Dovelet.com 입니다.
문제가 엄청 쉬운 것도 있고 어려운 것도 있는 듯 해 보이는데요.. 어제 2시간 정도 오늘 한 5시간 정도 투자하여 쉬운 쪽의 문제를 많이 풀어보았습니다. 대략 70여 문제를 풀었는데.. 이제는 조금 지치네요.. 나중에 차근차근 진행을 해봐야 겠습니다.

사각형 넓이 구하기
삼각형 넓이 구하기
네 수의 평균
두수의 교환
섭씨온도를 화씨온도로 변환
몫과 나머지 구하기
거스름 돈
손해 본 금액
퓨 즈
대소 판별하기
분수 크기 비교
수영장 가는 날
윤 년
중위수
삼각형 성립 조건
사주 팔자
해킹 회사
팀 구성
지하 차도
점수 맞추기
등차/등비 수열
축소 복사
조건 연산자
오버랩
달의 날수(switch 예제)
별 출력
순차 출력
구구단
7 개 합
끼리끼리 합
홀 수
순차 합
팩토리얼 구하기
순차 합II
최대 값
최소 값
달에서 무게
화학 실험
최대,최소값 출력
복리법
가장 부지런한 농부
약수 출력
3*n+1
완전 수
학 점
완전수,부족수,과잉수
총합,최대,최소
최대공약수,최소공배수
소수(prime number)
서로 소
중간 수
speed limit
세자리수 곱셈
수 추측하기
number steps
두 수의 연결
직각 삼각형 (별)
역 직각 삼각형I (별)
역 직각 삼각형II (별)
E 출력(별)
거울에 비친 E(별)
네모(별)
F 출력(별)
T 출력(별)
H 출력(별)
쾌걸 조로 (별)
삼각형 (별)
다이아몬드 (별)
54321
b54321
주사위 던지기 I
주사위 던지기 II
완전수 출력

어려운 문제는 푸는데 시간이 조금씩 걸릴 듯 하네요.. 차근차근 계속해서 풀어볼 생각입니다. 다들 한 번 풀어보시길 바랍니다.^^;

풀어본 문제 중 하나를 적어보도록 하겠습니다.

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

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

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

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


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


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

Graphical.cpp (Language : cpp)

1. #include <iostream>
2. #include <string>
3. #include <deque>
4.  
5. int Width, Height;
6. char Image[251][251];
7.  
8. void StringTokenizer( const std::string &Str, std::deque< std::string > &Token, const std::string &Delimiter );
9.  
10. void NewImage( std::deque< std::string > &Token );
11. void ClearImage( std::deque< std::string > &Token );
12. void SetPixel( std::deque< std::string > &Token );
13. void VerticalLine( std::deque< std::string > &Token );
14. void HorizonLine( std::deque< std::string > &Token );
15. void Square( std::deque< std::string > &Token );
16. void MagicWord( std::deque< std::string > &Token );
17. void SaveImage( std::deque< std::string > &Token );
18. void ExitProgram( std::deque< std::string > &Token );
19.  
20. void NearstFill( int X, int Y, char Color, char OldColor );
21.  
22. int main( int argc, char **argv )
23. {
24.     char InputString[ 256 ];
25.  
26.     while( true )   {
27.  
28.         std::cin.getline( InputString, 255 );
29.         std::deque< std::string > TokenContainer;
30.  
31.         StringTokenizer( InputString, TokenContainer, "\t " );
32.  
33.         std::string &Cmd = TokenContainer.front();
34.         if( Cmd == "I" )
35.             NewImage( TokenContainer );
36.         else if( Cmd == "C" )
37.             ClearImage( TokenContainer );
38.         else if( Cmd == "L" )
39.             SetPixel( TokenContainer );
40.         else if( Cmd == "V" )
41.             VerticalLine( TokenContainer );
42.         else if( Cmd == "H" )
43.             HorizonLine( TokenContainer );
44.         else if( Cmd == "K" )
45.             Square( TokenContainer );
46.         else if( Cmd == "F" )
47.             MagicWord( TokenContainer );
48.         else if( Cmd == "S" )
49.             SaveImage( TokenContainer );
50.         else if( Cmd == "X" )
51.             ExitProgram( TokenContainer );
52.     }
53.  
54.     return 0;
55. }
56.  
57. void StringTokenizer( const std::string &Str, std::deque< std::string > &Token, const std::string &Delimiter )
58. {
59.     std::string::size_type LastPos = Str.find_first_not_of( Delimiter, 0 );
60.     std::string::size_type Pos     = Str.find_first_of( Delimiter, LastPos );
61.    
62.     while( std::string::npos != Pos || std::string::npos != LastPos )
63.     {
64.         Token.push_back( Str.substr( LastPos, Pos - LastPos ) );
65.         LastPos = Str.find_first_not_of( Delimiter, Pos );
66.         Pos = Str.find_first_of( Delimiter, LastPos );
67.     }
68. }
69.  
70. void NewImage( std::deque< std::string > &Token )
71. {
72.     Width = atoi(Token[1].c_str());
73.     Height = atoi(Token[2].c_str());
74.  
75.     ClearImage( Token );
76. }
77.  
78. void ClearImage( std::deque< std::string > &Token )
79. {
80.     for( int i = 0; i <= Height; ++i )
81.         for( int j = 0; j <= Width; ++j )
82.             Image[ i ][ j ] = 'O';
83. }
84.  
85. void SetPixel( std::deque< std::string > &Token )
86. {
87.     int X = atoi(Token[1].c_str());
88.     int Y = atoi(Token[2].c_str());
89.     char Color = *Token[3].c_str();
90.  
91.     Image[ Y ][ X ] = Color;
92. }
93.  
94. void VerticalLine( std::deque< std::string > &Token )
95. {
96.     int X = atoi(Token[1].c_str());
97.     int Y = atoi(Token[2].c_str());
98.     int Y2 = atoi(Token[3].c_str());
99.     char Color = *Token[4].c_str();
100.  
101.     if( Y2 < Y )
102.         std::swap( Y, Y2 );
103.  
104.     for( int i = Y; i <= Y2; ++i )
105.         Image[ i ][ X ] = Color;
106. }
107.  
108. void HorizonLine( std::deque< std::string > &Token )
109. {
110.     int X = atoi(Token[1].c_str());
111.     int X2 = atoi(Token[2].c_str());
112.     int Y = atoi(Token[3].c_str());
113.     char Color = *Token[4].c_str();
114.  
115.     if( X2 < X )
116.         std::swap( X, X2 );
117.  
118.     for( int i = X; i <= X2; ++i )
119.         Image[ Y ][ i ] = Color;
120. }
121.  
122. void Square( std::deque< std::string > &Token )
123. {
124.     int X = atoi(Token[1].c_str());
125.     int X2 = atoi(Token[2].c_str());
126.     int Y = atoi(Token[3].c_str());
127.     int Y2 = atoi(Token[4].c_str());
128.     char Color = *Token[4].c_str();
129.  
130.     if( X2 < X )
131.         std::swap( X, X2 );
132.  
133.     if( Y2 < 2 )
134.         std::swap( Y, Y2 );
135.  
136.     for( int i = Y; i <= Y2; ++i )
137.         for( int j = X; j <= X2; ++j )
138.             Image[ i ][ j ] = Color;
139. }
140.  
141. void MagicWord( std::deque< std::string > &Token )
142. {
143.     int X = atoi(Token[1].c_str());
144.     int Y = atoi(Token[2].c_str());
145.     char Color = *Token[3].c_str();
146.     char OldColor = Image[ Y ][ X ];
147.  
148.     NearstFill( X, Y, Color, OldColor );
149. }
150.  
151. void SaveImage( std::deque< std::string > &Token )
152. {
153.     std::cout << Token[1] << std::endl;
154.  
155.     for( int i = 1; i <= Height; ++i )  {
156.         for( int j = 1; j <= Width; ++j )
157.             std::cout << Image[ i ][ j ];
158.        
159.         std::cout << std::endl;
160.     }
161. }
162.  
163. void ExitProgram( std::deque< std::string > &Token )
164. {
165.     exit(0);
166. }
167.  
168. void NearstFill( int X, int Y, char Color, char OldColor )
169. {
170.     if( Image[ Y ][ X ] == OldColor )   {
171.        
172.         Image[ Y ][ X ] = Color;
173.  
174.         if( X > 1 )
175.             NearstFill( X - 1, Y, Color, OldColor );
176.  
177.         if( X < Width )
178.             NearstFill( X + 1, Y, Color, OldColor );
179.  
180.         if( Y > 1 )
181.             NearstFill( X, Y - 1, Color, OldColor );
182.  
183.         if( Y < Height )
184.             NearstFill( X, Y + 1, Color, OldColor );
185.     }
186. }

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

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

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

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

TheTrip.cpp (Language : cpp)

1. #include <iostream>
2. #include <cmath>
3.  
4. int main(int argc, char **argv)
5. {
6.     int CntInput = 0;
7.     double CostList[1000] = {0.00,};
8.  
9.     do{
10.         double Average = 0.00;
11.         double MoveCost = 0.00;
12.  
13.         std::cin >> CntInput;
14.  
15.         for( int i = 0; i < CntInput; ++i ) {
16.            
17.             std::cin >> CostList[i];
18.             Average += CostList[i];
19.         }
20.  
21.         if( CntInput != 0 ) {
22.        
23.             Average /= static_cast<double>(CntInput);
24.             double DiffCost = 0.00;
25.            
26.             for( int i = 0; i < CntInput; ++i ) {
27.    
28.                 DiffCost = Average - CostList[i];
29.                 MoveCost += ( DiffCost > 0.00 ? DiffCost : 0.00 );
30.             }
31.  
32.             std::cout.precision(2);
33.             std::cout << std::fixed << '$' << std::floor(MoveCost * 100) / 100 << std::endl;
34.         }
35.  
36.     }while( CntInput != 0 );
37.  
38.     return 0;
39. }

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

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

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

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

MineSweeper.cpp (Language : cpp)

1. #include <iostream>
2.  
3. int Width, Height;
4. char MineField[100][100];
5.  
6. int GetField(int col, int row)
7. {
8.     if( (0 <= col && col < Height) &&
9.         (0 <= row && row < Width )) {
10.  
11.         return (MineField[col][row] == '*' ? 1 : 0);
12.     }
13.  
14.     return 0;
15. }
16.  
17. char Calculate(int col, int row)
18. {
19.     if( GetField(col, row) )
20.         return '*';
21.  
22.     int Count = 0;
23.     Count += GetField( col - 1, row - 1 );
24.     Count += GetField( col - 1, row );
25.     Count += GetField( col - 1, row + 1 );
26.     Count += GetField( col, row - 1 );
27.     Count += GetField( col, row + 1 );
28.     Count += GetField( col + 1, row - 1 );
29.     Count += GetField( col + 1, row );
30.     Count += GetField( col + 1, row + 1 );
31.    
32.     return '0' + Count;
33. }
34.  
35. int main( int argc, char **argv )
36. {
37.     while( true )   {
38.         std::cin >> Width >> Height;
39.  
40.         if( Width == 0 && Height == 0 )
41.             break;
42.  
43.         for( int i = 0; i < Height; ++i )   {
44.             for( int j = 0; j < Width; ++j )    {
45.                
46.                 std::cin >> MineField[i][j];
47.             }
48.         }
49.  
50.         for( int i = 0; i < Height; ++i )   {
51.             for( int j = 0; j < Width; ++j )    {
52.                
53.                 std::cout << Calculate(i, j);
54.             }
55.  
56.             std::cout << std::endl;
57.         }
58.     }
59.  
60.     return 0;
61. }

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

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

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

1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=647
   
2.  의   견   : 배열을 이용 참조하여 문자열을 출력하는 식으로 구현해봤습니다. 문제는 Commit 시 공백의 문제점 때문에 Wrong Answer가 뜨더군요. 하지만, 외관상 문자열 출력형식은 같기에 굳이 Accept까지 진행하지는 않았습니다. 가로와 세로의 출력을 분리하여 구현한다면 쉬운 문제일 것입니다.
   
3. 소스
   
   706.cpp (Language : cpp)

   1. #include <iostream>
   2. #include <string>
   3.  
   4. std::string NumberList;
   5.  
   6. unsigned char CharacterTable[ 10 ][ 5 ][ 3 ] = { { { ' ', '-', ' ' }, { '|', ' ', '|' }, { ' ', ' ', ' ' }, { '|', ' ', '|' }, { ' ', '-', ' ' } }, // 0
   7. { { ' ', ' ', ' ' }, { ' ', ' ', '|' }, { ' ', ' ', ' ' }, { ' ', ' ', '|' }, { ' ', ' ', ' ' } }, // 1
   8. { { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', '-', ' ' }, { '|', ' ', ' ' }, { ' ', '-', ' ' } }, // 2
   9. { { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', '-', ' ' } }, // 3
   10. { { ' ', ' ', ' ' }, { '|', ' ', '|' }, { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', ' ', ' ' } }, // 4
   11. { { ' ', '-', ' ' }, { '|', ' ', ' ' }, { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', '-', ' ' } }, // 5
   12. { { ' ', '-', ' ' }, { '|', ' ', ' ' }, { ' ', '-', ' ' }, { '|', ' ', '|' }, { ' ', '-', ' ' } }, // 6
   13. { { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', ' ', ' ' }, { ' ', ' ', '|' }, { ' ', ' ', ' ' } }, // 7
   14. { { ' ', '-', ' ' }, { '|', ' ', '|' }, { ' ', '-', ' ' }, { '|', ' ', '|' }, { ' ', '-', ' ' } }, // 8
   15. { { ' ', '-', ' ' }, { '|', ' ', '|' }, { ' ', '-', ' ' }, { ' ', ' ', '|' }, { ' ', '-', ' ' } } }; // 9
   16.  
   17. void HorizonalPrint( int Width, int Seq )
   18. {
   19.     bool IsFirst = true;
   20.     char PrintChar;
   21.     size_t VectorCount = NumberList.length();
   22.  
   23.     for( unsigned int i = 0; i < VectorCount; ++i ) {
   24.  
   25.         PrintChar = CharacterTable[ NumberList[ i ] - '0' ][ Seq ][ 1 ];
   26.  
   27.         if( i != 0 )
   28.             std::cout << " ";
   29.  
   30.         std::cout << " ";
   31.         for( int j = 0; j < Width; ++j ) {
   32.             std::cout << PrintChar;
   33.         }
   34.         std::cout << " ";
   35.     }
   36. }
   37.  
   38. void VerticalPrint( int Width, int Seq )
   39. {
   40.     bool IsFirst = true;
   41.     size_t VectorCount = NumberList.length();
   42.  
   43.     std::string PrintStr = "";
   44.  
   45.     for( unsigned int i = 0; i < VectorCount; ++i ) {
   46.  
   47.         if( i != 0 )
   48.             PrintStr += " ";
   49.  
   50.         PrintStr += CharacterTable[ NumberList[ i ] - '0' ][ Seq ][ 0 ];
   51.         for( int j = 0; j < Width; ++j ) {
   52.             PrintStr += " ";
   53.         }
   54.         PrintStr += CharacterTable[ NumberList[ i ] - '0' ][ Seq ][ 2 ];
   55.     }
   56.  
   57.     for( int Cnt = 0; Cnt < Width; ++Cnt )
   58.         std::cout << PrintStr.c_str() << std::endl;
   59. }
   60.  
   61. void PrintNumber( int Width )
   62. {
   63.     for( int i = 0; i < 5; ++i ) {
   64.  
   65.         if( i & 1 )
   66.             VerticalPrint( Width, i );
   67.         else {
   68.             HorizonalPrint( Width, i );
   69.             std::cout << std::endl;
   70.         }
   71.     }
   72. }
   73.  
   74. int main( int argc, char **argv )
   75. {
   76.     int CharacterWidth;
   77.  
   78.     while( true ) {
   79.  
   80.         std::cin >> CharacterWidth >> NumberList;
   81.  
   82.         if( CharacterWidth == 0 ) {
   83.  
   84.             if( NumberList == "0" )
   85.                 break;
   86.             else
   87.                 continue;
   88.         }
   89.  
   90.         PrintNumber( CharacterWidth );
   91.     }
   92.  
   93.     return 0;
   94. }
   95.  
   96.  
   
   

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

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