알고리즘 테스트 사이트 인 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 완전수 출력
어려운 문제는 푸는데 시간이 조금씩 걸릴 듯 하네요.. 차근차근 계속해서 풀어볼 생각입니다. 다들 한 번 풀어보시길 바랍니다.^^;
풀어본 문제 중 하나를 적어보도록 하겠습니다.
프로그램 명: center1
제한시간: 1 초
1 부터 n-1 까지의 합이 n+1,n+2,... 의 합과 같을 때 n 을 중간수라 한다.
예를 들어 , 4 는 1+2+3=6 이고 5 부터 차례대로 더해갈 때 5+6=11 이므로 4 는 중간수가 될 수 없다.
음 한 주가 지나가고 새로운 한 주가 시작되는 시점입니다. 뭐 이런저런 일들이 저번 주에는 많았군요. 어떻게 하다보니 필요에 의한 근무지를 경산으로 잠시 옮기게 되었습니다. 기간은 약 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
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 커맨드가 이 중엔 제일 이겠군요. 그래도 별로 어렵지는 않으니 ^^. 재미있게 대충대충 ㅎㅎ
깔끔하게 해보려고 했지만 일단 그냥 푸는게 더 좋을것 같아서 대충대충 했습니다. 일단 결과물이 나와야 과정이 중요하지 않겠습니까^^? 그럼 새로운 한 주 잘보세요.
금방 풀어봤던 한 문제는 The Trip(여행)이라는 문제입니다. 이 것도 초반 문제다 보니 별로 어렵지는 않네요. 대략적인 문제의 개요는 여행을 가는데 여러명이 사용하는 경비를 각자 내려니 너무 귀찮다는거죠. 그리하여 각 사람마다 여행경비, 숙박비 등을 지불하게 되는데 이게 또 그냥 넘어가면 껄쩍지근 하잖습니까?^^ 그래서 돈을 나중에 서로 교환을 하여 서로 지불액수를 맞추게 됩니다. 여기서 포인트는 액수를 맞추기 위하여 이동하는 돈의 개수를 센트까지 세어라 입니다. 물론 입력은 달러 단위로 받게 되구요. 일단 입력과 출력 예제를 보겠습니다.
입력: 3 10.00 20.00 30.00 4 15.00 15.01 3.00 3.01
출력: $10.00 $11.99
이 문제도 사실 어렵지 않기 때문에 대충대충 해서 풀었습니다. 한 가지 숫자의 정밀도 출력으로 인해서 11.99가 출력되어야할 시점에 12가 출력될 수 있기 떄문에 센트까지만 이라는 힌트를 참조하여 * 100을 한 다음 / 100을 하여 내림을 시켜버리면 문제없이 출력이 됩니다. 다음 문제도 계속 풀어봐야 겠군요^^.
음 뭐 책을 사놓고 도통 보지 않는 것 같아 오늘 야근 하고 돌아온 김에 잠시 봤는데 시간이 없어 많은 것을 생각하는 문제는 선택하지 못하고 아주 간단한 문제를 선택해봤습니다. 아무래도 첫 술부터 배부를 수는 없듯이 차근차근 있는 문제 그냥 연습한다 치고 하나씩 풀어보기로 했습니다. 문제의 이름은 Mine Sweeper네요. 대충 입력, 출력의 예와 코드 는 다음과 같습니다.
입력
4 4 *... .... .*.. ....
출력 *100 2210 1*10 1110
복잡한 문제는 아니죠^^? 그냥 아주 간단하길래 대충 생각하고 대충 풀었습니다. 코드가 즈질 이군요 ㅎㅎ 계속해서 한 문제씩 차근차근 풀어봐야 겠습니다.
***Note: Please keep programs under 7000 characters in length. Thank you
Class Name: SquareDigits Method Name: smallestResult Parameters: int Returns: int
Define the function S(x) as the sum of the squares of the digits of x. For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.
Define the set T(x) to be the set of unique numbers that are produced by repeatedly applying S to x. That is: S(x), S(S(x)), S(S(S(x))), etc... For example, repeatedly applying S to 37: S(37)=3*3+7*7=58. S(58)=5*5+8*8=89. S(89)=145. S(145)=42. S(42)=20. S(20)=4. S(4)=16. S(16)=37. Note this sequence will repeat so we can stop calculating now and: T(37)={58,89,145,42,20,4,16,37}. However, note T(x) may not necessarily contain x.
Implement a class SquareDigits, which contains a method smallestResult. The method takes an int, n, as a parameter and returns the smallest int, x, such that T(x) contains n.
The method signature is (be sure your method is public): int smallestResult(int n);
TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.
Examples: If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.
If n=2: T(0) through T(10) do not contain the value 2. If x=11, however: S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.
If n=10: T(0) through T(6) do not contain 10. If x=7: S(7)=49. S(49)=97. S(97)=130. S(130)=10. S(10)=1. and it starts to repeat... so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.
Class: SquareDigits Method: smallestResult Parameters: int Returns: int Method signature: int smallestResult(int param0) (be sure your method is public)
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
대충 얘기를 하자면 X(11)= 1*1 + 1*1 = 2 라는 X 함수가 존재합니다. 그런데 이 함수는 중첩적으로 계속 하여 호출 될 수 있습니다. 대충 예를 들면 X(11) = 2, X(2) = 4, X(4) = 16 ... 등등으로 계속 호출 될 수 있겠죠. 그러다가 이 함수 호출에 있어서 X(A)=Y 형태 중 A가 이미 호출되었을 때는 해당 N 숫자에 대한 집합에 들어가 있으므로 결국 T(11) = { 2, 4, 16 .. } 형태의 집합으로 나타낼 수 있습니다. 중요한 것은 T(11)로 표현되는 집합에 11이라는 숫자가 들어가 있는가 하는 점입니다. 들어가 있다면 11을 리턴하게 되고, 포함되어있지 않으면 T(12)를 작업해보고, 그 결과에 따라 13, 14로 늘어날 수 있습니다. 그리고 제일 작은 숫자를 리턴하면 됩니다.
이 번엔 제대로 검사를 하긴 했습니다. 그런데 INT_MAX 라는 범위가 있다보니 199까지 최대 숫자를 측정하여 배열을 이용한 O(1)시간의 검색이 되어야 하나, 손해를 약간 보더라도 set에 대한 find 검색작업을 수행하도록 구성하였습니다. 포인트가 안 좋은건 속도 때문일까요?^^. 그냥 풀어본 것에 의미를 가지도록 하겠습니다.
댓글을 달아 주세요