심심풀이2010. 4. 4. 10:51

더블릿이란 사이트에 빠져버렸다. http://www.dovelet.com/

문제가 있고 문제에 주어진 입력과 출력에 맞춰서 프로그램을 짜서 통과하면 되는 것이다.


나는 될수있는한 짧은 코드? 를 만드는것에 재미를 느끼는데

몇가지 트릭(온갖 코드를 줄이기 위한)을 알아내고나서 몇가지 문제서 1등도 해보았다 ㅋㅋ



예를 들자면 
이와 같이

메인함수 리턴형 없이 자동으로 void형으로 맞추거나  main 함수의 파라미터로 넘기는 식으로 변수 선언.. ㅡ. (디폴트 int 형인가보다) 

단 저렇게 변수 하나를 입력 받아도  25바이트를 소모한다. 여기에 출력 printf("%d",a)

변수 하나만 출력해도 14바이트를 소모

carry가 없는 덧셈 문제로서 
일반적으로 덧셈은 자동적으로 carry가 발생하므로 다음과 같이 써도 된다.
 a+b = (a^b) + (a&b)*2
XOR 하면 비트가 다르다면 1을 발생시키므로 덧셈이 성립하나 1+1 같은경우 캐리가 발생하지 않게 되므로  & 연산을 함으로서  각 자리수의 carry를 찾아낸다음 왼쪽으로 1만큼 쉬프트(2를 곱함)
한것을 더하면 된다. 다만 이 문제는 carry가 발생 안한경우를 찾으므로 그냥 XOR연산 하면 된다.ㅡ.
이 보다 더 줄일수는 없는것 같다. 

이런식으로 온갖 방법을 동원하여 코드수를 줄일수 있다.

또 bit 관련 문제인데.
bit 관련 문제는 bit연산을 적절히 활용하면 코드수를 엄청 줄이기 편한점이 있는것 같다.


59바이트...
각 숫자를 이진트리의 노드라고 했을때  각 노드의 차수는(트리에서 그 노드의 높이)
이진수로 볼때 0의 개수나 마찬가지(또는 오른쪽부터 셋을때 가장 오른쪽의 1의 위치) 이다.   
예를 들어 10 이라면 이진수로  1010 이고  차수는 1
이진트리에서 루트에서 가장 작은 값은 가장 왼쪽 값이므로
가장 오른쪽에 있는 1을 지우고 1을 더하면 가장 작은 값을 찾아낼수 있다.

가장 오른쪽의 1을 찾아내는 간단한 bit 연산 트릭은  a&-a  이다.
2의 보수 표현의 특성을 이용하는것으로서 생각해보면 당연하다. 이것을 찾아낸뒤 XOR 연산을 하면 가장 오른쪽의 나타나는 1을 지워버릴수 있는것이다.

트리에서 가장 큰수를 찾아내는것은 가장 오른쪽의 1 비트부터 시작해서 끝까지 1로 채워버리는것이 된다. 이는 간단하게 a|(a-1) 하면 되는데  예를 들어 12라는 수는 이진수로 1100 이다.

여기서 1을 빼면 이진수 연산으로 생각하면  1011  이 되고 다시 OR 연산하면 1이 끝까지 연장되게 되는것이다.

이러한 줄이기 위한 각종 트릭을 쓰는것도 중요하지만
코드를 짧게 만들기 위해 적절한 표현방법을 선택하는것도 중요한것 같다


오토마타 관련 파트에 있는 문제인데 

상태그래프를 활용하기에 아주 적절한 문제 인것 같다.


이문제에서는 ~ 의 역할이 정규식에서 + 나 마찬가지 이다.

처음상태에서 0을 받으면 상태1로 가고 1을 받으면 상태2로 간다.
상태1에서 0을 받으면 에러상태로 가고 1을 받으면 초기상태로 간다.  01 만 허용
상태2에서 0을 받으면 상태3으로 가고 1을 받으면 에러상태로 간다. 10 만 허용
...
이런식으로 상태그라프를 계속 그려서 그것을 상태테이블로 표현하는데 
여기서는 문자열로 표현했다.
그래서 상태테이블과 순차적으로 입력되는 스트링에 따라서 상태가 적절히 움직이고
최종적으로 상태 0 또는 5에 있어야만 잠수함 소리인것을 알수 있는 것이다. 
123바이트로 되었다. 근데 더 줄일수 있을듯 하다.




87바이트..
이문제는 각 자리수의 합을 구하고 몇자리수인지 알아낸 다음에 1부터 n까지 구하는 공식인 n(n+1)/2  와 각 자리수의 합과 같다는 것을 이용하였다.


하여간 재미있다.
특히 나처럼 코드크기를 줄이는데 미학을 쫒는 굇수 횽님들이 많은거 같다.
가끔 코드가 공개된것이 있는데 감탄스러울 뿐이다..

'심심풀이' 카테고리의 다른 글

[더블릿] prefix 계산기  (0) 2010.06.04
더블릿 dump 문제  (2) 2010.05.06
더블릿  (0) 2010.04.04
xy평면  (2) 2010.04.03
[bits] 산술  (0) 2010.03.03
[bits] 비트 다루기  (0) 2010.03.03
Posted by 멍충한아싸

댓글을 달아 주세요