BLOG main image
분류 전체보기 (466)
Yuno (232)
Travel (130)
Culture (46)
Other (11)
Programming (17)
Picture (22)

[필리핀,마닐라] 그린벨트 (Gr..
월풍도원(月風道院) - Delight..
Tamiflu and parvo.
Tamiflu and side effects.
[미국,라스베가스] 라스베가스..
월풍도원(月風道院) - Delight..
[미국,라스베가스,그랜드캐년]..
월풍도원(月風道院) - Delight..
[태국,방콕]태국 숙소,방콕 -..
월풍도원(月風道院) - Delight..
«   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      
1,476,559 Visitors up to today!
Today 143 hit, Yesterday 253 hit

'Programming'에 해당되는 글 3건
[Yuno.org, 2006/10/12 17:56, Programming/Code Story]

구글(Google)의 R&D 센터가 한국에 생긴다. 조금이라도 IT나 인터넷, 프로그래밍.. 이런 이야기에 관심이 있는 사람이라면 이런 저런 이야기가 많이 듣거나 봤을 것이다. 구글의 사무실 분위기 사원 복지 정책 등을 보고 있자면 소프트웨어 엔지니어의 천국이라는 생각이 들 정도이다.

많은 사람들의 구글의 채용 정책에 관심이 많고.. 또 많은 언론에서 구글의 독특한 채용 방법을 기사에 올리고 있다. 그러던 중에 우연히 매일 경제에 포스트 된 기사를 볼 수 있었다. 구글의 입사 시험 문제 중에 하나 였는데 사무실 옆 자리에 있는 형이 관심을 갖고 있는걸 보고 나도 한번 보게 되었다.

해당 기사 보러 가기 (이곳을 누르면 해당 기사로 갈 수 있습니다.)

" 양수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가. "

풀어서 이야기 하면 양수 N 까지의 숫자를 나열 했을때 1 이 들어간 수를 헤아리는데 양수 N까지의 1의 갯수가 양수 N과 동일한 두번째 값을 찾는 문제이다.

단순하게 N까의 루프에서 1의 숫자를 헤아리게 만든다면 P4 3G 라도 엄청난 시간이 걸린다. -_-

한번쯤 관심이 있다면 풀어 보자~

<< 풀어본 답 열기 >>



--
alklid | 2006/10/12 22:23 | PERMALINK | EDIT/DEL | REPLY
ㅋ 전 못가겠네요..-_-;
superkkt | 2006/10/17 09:18 | PERMALINK | EDIT/DEL | REPLY
저는 이력서도 못내밀겠네요.. 도대체 뭔말이여~^^
xevious7 | 2006/10/20 23:32 | PERMALINK | EDIT/DEL | REPLY
유노님 포스트는 잘 보았습니다만 ,시험문제를 잘 풀려면 문제의 의도를 파악하는게 중요하다고
생각합니다. 이 문제의 의도는 다른데 있는 것 같습니다.
유노님의 코드는 유노님의 설명과 달리 어찌되었는 while 문 안에서 ++n 를 하기 때문에 n번의 수행이 필요합니다.
n번을 수행하는 코드는 대부분의 프로그래머가 쉽게 작성가능합니다.
그 안의 최적화하고 별도의 문제로 n번을 수행해야 합니다. 즉 복잡도가 n이라는 것입니다.
만약 100만번째 숫자였다면 100만번을 돌려야 하는 것이지요.
http://bbs.python.or.kr/viewtopic.php?t=22323 결국 이코드랑 비교하자면
유노님이 최적화 한부분은
1의 검색부분인데 , 이것은 이 시험문제가 의도한 것이 아닌 것 같습니다.
시험문제를 낸 사람이 원하는 것은 n번 돌리는 즉 복잡도 n의 프로그램을 원하는것이
아닌 것 같습니다.
복잡도 n 을 줄여나가는 것이 목표인것 같습니다.
적어도 마지막에 말한 좀더 가속하고자 하는 부분
의 라직을 다듬어 문제의 답을 작성하셔야 될듯 합니다. ~ 초면에 실례가 되었습니다만
도움이 도움이 되고자 적어보았습니다.
Yuno | 2006/10/21 00:13 | PERMALINK | EDIT/DEL
아아 xevious7님의 말씀이 맞습니다. 다만, 저 문제를 푸는 모습을 보고 x까지의 정수에서 1의 출연 횟수 구하는 방식을 줄여 보고자 했기 때문에 저 결과물이 나온겁니다~ ;

저 같은 경우는 간단한 방식으로 연산 횟수를 크게 줄여놨었습니다. shift 를 이용한 x값의 증감을 이용했는데 이는 x와 f(x)가 항상 동시에 증가 한다는 전제를 기준으로 작업을 했습니다만.. 퇴근시간이라 작성은 중단했습니다만-_-;

아무튼 조언 감사드립니다 ;)
xevious7 | 2006/10/21 11:00 | PERMALINK | EDIT/DEL | REPLY
아 그러셨군요 ~ ^^ 역시 ~ 좋은 주말되세요.
rotoRl | 2006/12/03 16:10 | PERMALINK | EDIT/DEL | REPLY
이거 프로그램 돌리면 199980 나오는데여???
답은 199981 인데 뭐가 잘못된건가여???
초보 | 2007/04/27 06:31 | PERMALINK | EDIT/DEL | REPLY
죄송합니다만 도움 좀 주세요. 설명이 이해가 안되요

#include <stdio.h>


void main()
{

int N=0,C=1,D;
int Result=0;

while(C)
{
N;
D=N;

while( D )
{
if( D % 10 == 1){
Result =1;
}

D = D / 10;
printf("M, M, M\n", N, Result, D);

}



if( N == Result
seobi | 2008/06/17 16:42 | PERMALINK | EDIT/DEL | REPLY
저도 한번 한시간동안 끙끙대며 문제 풀어 봤는데요..
아무리해도 복잡도를 줄이는건 이방법 왜엔 없는거 같네요..
제가 푼 방법은 간단히 첫번째 자리가 2~9일때는 1의 갯수가 증가하는 n을 추월할수가 없으니 첫번째 수가 2로 시작하면 바로 다음자리 10^n 으로 넘겨버립니다..
10^n 일때 1의 갯수는 쉽게 계산이 되더라구요..
소스는 좀더 다듬으면 줄어들긴 하겠지만 남이 보기엔 이게 가장 좋아 보이는군요..

사실 while문 안에
do {
if( jari_check%10 == 1 )
s_count++;
}while((jari_check = jari_check/10) > 0);
count += s_count;
이것만 있으면 끝인데 복잡도를 줄이려니 전체 소스가 길어지는군요..
어쨋든.. 구글~ 들어간사람들은 부럽삼...
int n = 0;
int count=0;
int s_count;
bool check;
int jari, jari_check;
while( n > count || n <= 1 ) { //1의 갯수가 n보다 같거나 클때까지..
jari_check = ++n;
check = false;
jari = 0;
s_count = 0;

do {
if( jari_check < 10 && jari_check == 1) //첫번째 자릿수가 1인지 여부 판단
check = true;
else //총 몇자리인지 판단
jari++;
if( jari_check%10 == 1 ) //현재 숫자에서 1이 몇개 있는지 판단하여 기존 count에 더함..
s_count++;
}while((jari_check = jari_check/10) > 0);

if( !check ) { //첫번째 자릿수가 1이 아닐때.. 즉 20, 200, 2000 될때 바로 100, 1000, 10000 으로 점프..
int k = 1;
int tmp_sum = 1;
int tmp_count = 0;
while( k < jari ) { // 1의 갯수.. 100에 21, 1000에 301, 10000에 4001
tmp_count = pow(10, k++ );
tmp_sum = ( tmp_count + (tmp_sum*10) );
}
n = pow(10, k);
count = tmp_sum+1;
}
else
count += s_count;
}
printf("Result f(%d) = %d\n",n,count);
Name
Password
Homepage
Secret
[Yuno.org, 2006/09/30 11:35, Programming/Development Story]

완료 된지 시간이 조금은 지난 프로젝트. 게임으로 따지면 서비스가 시작된지 조금 된 게임들. 프로그램으로 따지면 최초 개발 이후 고객에 따라서 커스터마이징을 하고 있는 과정 정도에 있는 경우에 해당한다.

어떤 프로젝트든지 완벽한 문서와 모든 코드를 숙지 할 수 있는 교육 과정이 있다면야 문제 없지만, 현실적으로는 그런 일은 드물다. 아니 있을 수 없다고 해야 할런지..

완성된 프로젝트를 이어 받아서 커스터마이징 및 유지 보수, 추가 작업을 하다 보면 가끔은 이런 기능이 있으면 좋을 텐데 하고 관련 자료를 찾아서 적용 준비를 하다보면 평소에는 보이지 않던 파일명과 클래스명이 보이곤 한다. 혹시.. 라는 마음에 찾아 보면 역시나 oTL.. 이미 구현이 되어 있지만, 코드 깊은 곳에 묻혀 있어 알 수 없었다던가 특수한 경우에만 작동하게 되어 있다던지 하는 일이 있다.

나름 난감하다. 그 기간동안 이런게 있다는 사실을 몰랐다니! 아쉬워 해봐야 소용 없다.. 하지만 다른 숨겨진 기능을 찾기에는 유지 보수에도 시간이 부족하다. 결국 프로젝트를 구성하고 있는 모든 구성요소를 모른채 계속 일을 이어 갈 수 밖에 없다.

oTL

이런 일은 가끔 예상치 못한 문제를 낳기도 한다.

예를 들어서 게임에서는 유저의 시야권에 다른 케릭터가 접근하게 되면 해당 사실을 서버에게 알려준다. 그런데 완성되고 나서 몇년이 지난후에 새 개발팀이 해당 프로젝트를 맡아서 진행하다가 이미 시야에 들어온 유저의 데이터의 갱신이 필요한 일이 생겼다.

그래서 작업 방법을 고민하다가 시야에 유저가 들어왔을때 해당 사실을 통보해주는 모듈을 사용하여, 같은 UserID를 가진 User Object가 다시 전송되면 업데이트 되는 방식으로 구현. 서비스를 한동안 진행하던 중에 우연히 코드중에 유저의 정보만을 업데이트 시켜주는 현재는 자주 사용되지 않는 패킷 모듈이 있었음을 발견 한다.

그런데 문제는 서버에서는 유저 데이터를 업데이트 시켜줄때 사용하는 정보와 유저가 시야에 들어왔을때 사용 되는 데이터가 동일할 것으로 예상. 공통적으로 유저 정보를 보내는 모듈을 사용하고 있었다.

어느 한쪽이 패킷 규약이 변경되면 다른 한쪽 역시 같은 모듈을 사용하므로 같이 변경 되는 그러한 방식.
그런데 서버 개발자도, 클라이언트 개발자도 이것을 모르고 있었다는거.. 결국 패킷은 데이터가 밀리는 현상이 발생. 특정 유저의 경우에는 예상치 못한 값에 의한 클라이언트 크래쉬가 일어나게 되었다. ;

난감..

한참동안을 원인을 못찾다가 이런걸 발견 하게 되면 정말 가슴이 아프다. 왜 조금 더 꼼꼼하게 살펴 보지 못했을까.. 하는 아쉬움은 이미 늦어 버렸으니까..



--
Name
Password
Homepage
Secret
[Yuno.org, 2006/09/30 03:14, Programming/Code Story]

많은 프로그래머들이 겪고 있는 신비로움일까. 아니면 무지에서 나오는 결과일까.

내가 속한 팀에서는 대부분 사내 테스트이 경우에는 디버그 버젼의 클라이언트를 이용해서 사용한다. 더 많은 클라이언트, 케릭터 정보, 많은 로그들을 얻을 수 있다는 장점이 릴리즈 버젼의 클라이언트 보다 더 크게 작용하기 때문이다.

그런데 여기서 가끔 문제가 생긴다. 릴리즈 버젼의 바이너리와 달리 디버그 버젼은 탱크와도 같아서 정말 튼튼하다. 프로그래머의 가벼운 실수 쯤은 가뿐히 넘어가 버린다.

많은 프로그래머가 실수하는 배열의 인덱스 오류로 인한 오버 플로우 정도는 디버그 컴파일시에 생기는 패딩 효과에 의해서 무마 되어 버린다.

그런데 오늘 정말 거지 같은 일이 있었다.

Windows API를 사용하는데 같은 클래스의 같은 메소드에서 Windows API의 결과가 릴리즈와 디버그가 달랐다. 한시간 넘게 고민하고 고쳐보고 구글질을 해봤지만 결국 원인 규명에는 실패. 참 난감하다.

이렇게 한참을 한 가지 문제를 해결 못해서 끙끙 거리다 보면, 어떤 책의 구절을 찾기 위해서 책장에서 책을 하나 하나 꺼내서 뒤지다가 없으면 책을 내동댕이 쳐서 엉망이 되어버린 방 처럼 머리속이 엉망이 된다.

그럴때는 지우개라도 사용해서 머리를 깨끗하게 비우고 다시 시작하고 싶다.

그리고, 많은 경우가 잠시 바람을 쐬고 처음 부터 차근 차근 하면 해결 되기도 한다. -_-

하지만. 오늘은 실패했다. ㄴㅁ..



--
Remisa | 2006/10/13 02:20 | PERMALINK | EDIT/DEL | REPLY
그래서 저는 디버그도 릴리즈 모드로 한답니다. ^^;;
아무 정보도 없이 테스트 코드만 한참 짜다보면 실력도 늘거든요.. ㅁㄴ알먼아ㅣ;러ㅏㅣ;
Name
Password
Homepage
Secret
*1