게임 프로그래밍중 좋은 포스팅이 있어 공유합니다



출처 : 알콜코더 : http://www.gamedevforever.com/114


안녕하세요. 알콜코더 민군입니다.

 

현재 제작 중인 게임에서, 랜덤 시드 값을 일치 시켜서, 랜덤 결과를 서로 다른 클라이언트끼리 동기화 시키는 작업을 진행 하였습니다. 랜덤 시드값만 서로 일치시키면, 이후에 생성되는 랜덤 함수의 결과값들은 모두 일치가 되기 때문에, 예전에 스타크래프트와 같은 패키지 게임에서 자주 사용했던 테크닉입니다. ^^; 서로 다른 클라이언트끼리 처음 시드값만 일치 시키면, 이후의 랜덤값은 정해져 있기 때문에, 그 랜덤값을 사용한 이벤트등의 동기화에 사용하는 것이죠.

 

이런 테크닉은 패키지 게임 시절에는 리플레이 저장이나 네트워크 동기화등에서 상당히 많이 사용하였습니다. 하지만 온라인 게임으로 넘어오면서, 대부분 서버에서 랜덤값을 직접 생성하여 넘겨주기 때문에, 이 테크닉 쓸일이 거의 없었는데… 이번 상황은 랜덤값이 게임의 결과에 전혀 영향을 끼치 않고, 단지 연출에만 영향을 끼치기 때문에 이 테크닉을 사용하기로 하였습니다. (서버 부담을 줄여달라는 서버쪽의 간절한 요청 때문에.. 아흑..OTL)

 

일반적으로 랜덤 함수라면 C++ 표준 rand() 함수를 사용하게 됩니다. 뭐.. 일반적인 랜덤값을 사용하는 경우에는 사실 이 표준 함수를 사용해도, 별 문제는 없습니다. ^^; 하지만 위와 같은 테크닉을 사용할 때는 rand() 함수를 사용하면 안됩니다!

왜냐하면, C++의 표준 rand() 함수는 아래와 같은 약간의 문제점을 가지고 있습니다.

  1. rand() 함수의 분포는 그리 고르지 않다. 특히 작은 표본을 사용할때는 더욱 그렇다. 
    즉, 이말은 1~10까지 랜덤을 1억번쯤 돌리면, 확률이 다들 비슷하게 나오긴 하지만, 10번 정도만 돌릴때에는 1 하나만 10번이 나온다거나 하는 가능성이 있다는 것입니다.

     

  2. rand() 함수는 전역 함수이다. 어디서든 사용이 가능하다
    이 함수는 표준 함수이기 때문에, 코드의 어디에서도 호출이 가능합니다. 그래서 호출 되는 경우를 제어할 수 가 없습니다.

 

< 즉 이런 기적의 확률이 나올수도 있는거임.. ㅠ.ㅠ >

 

저의 경우에 문제가 되는 것은 1번이 아니라, 2번입니다. 같은 랜덤 시드값으로 서로 다른 클라이언트에서, 싱크를 맞추기 위해서는 랜덤 호출 횟수가 정확히(!) 일치하여야 합니다! 내가 랜덤함수를 5번 호출했으면, 상대방도 5번 호출해야 같은 결과 값이 나와서 싱크가 일치하게 됩니다.

그런데 만약? 내가 작성한 코드가 아니라 어딘가 다른 코드에서 그것도 한쪽 클라이언트에서만 그 사이에 rand()를 호출하게 되면 어떻게 될까요? 넵. 당연히 그 다음부터는 모든 싱크가 아작이 나게됩니다…(그리고 이 경우에는 어디서부터 문제가 발생 했는지 찾는 것도 거의 불가능)

전역 함수라는 특징 때문에, 어디서 어떻게 불리울지 모르기 때문에, 언제 호출 횟수가 어긋날지 모른다는 문제가 발생하기 때문에, 랜덤 시드로 씽크를 맞추는 이 테크닉에서는 rand() 함수를 사용하는 것은 불가능 합니다. (내 코드에서는 절대 그럴리가 없어! 라고 해도… 다른 사람이 작성한 코드에서 과연 부르지 않는다는 보장이 있을까요…)

 

그래서 따로 랜덤 생성 클래스를 만들어 사용하게 됩니다. 랜덤 클래스를 만들고 그 인스턴스만을 사용하게 되면, 호출 횟수가 어긋나는 문제를 해결할 수 있으니까요. ^^

저의 경우가 바로 이런 경우라서, 랜덤 생성 알고리즘을 한번 찾아 봤습니다. 랜덤 생성 알고리즘은 "난수 생성기(Random Number Generator)", 혹은 "의사 난수 생성기" 등으로 불리웁니다. (그냥 저는 편의를 위해.. 이후 '랜덤 생성기'라고 칭하겠습니다. 이게 걍 편해요…)

 

이렇게 따로 랜덤 생성기를 이용해서, 랜덤 생성 클래스를 만들어 사용하면, 위와 같이 코드의 다른곳에서 랜덤값이 불리우는 경우를 제어할 수 있습니다. 물론 그렇다고 랜덤 생성 알고리즘을 혼자 고급 수학책이나 물리책 펴놓고 만들어서 쓰라는 이야기는 아닙니다. 친절하게도 이런 알고리즘은 전문 수학자 분들이 편하게 갖다 쓸수 있도록 편하고도 멋지게 만들어 두었습니다. (아이구~ 이런 감사할때가….)

 

이런 랜덤 생성기중에서 가장 유명하고 널리 쓰이는 알고리즘이 바로 [메르센 트위스터(MT.Mersenne Twister)]와 [WELL]이라는 랜덤 생성기입니다.

그리고 이 랜덤 생성기들은 위와 같은 테크닉에 사용할 수 있는 용도 외에도 다음과 같은 뛰어난 장점들을 가지고 있습니다

  1. 표준 함수보다 랜덤 분포가 훨씬 고르다

    표준 함수의 경우 2^32승의 period를 가지는데 반해, MT의 경우는 2^19937-1를 가집니다. 그리고 623차원까지 동일분포 되어 있습니다. (자세한건 아래 링크 참조)

     

  2. 표준 함수보다 훨씬 속도가 빠르다.

    MT의 경우에 비트 연산만으로 구현되어 있어서, 표준 rand()보다 약 4배가 빠르다고 합니다. 그리고 WELL 같은 경우에는 MT보다 40%가 더 빠르다고 합니다.

 

 

메르센 트위스터

위키백과우리 모두의 백과사전.

메르센 트위스터(Mersenne Twister) 1997년에 마츠모토 마코토(松本 ) 니시무라 다쿠지(西村拓士) 개발한 유사난수 생성기이다.[1] 메르센 트위스터는 동일한 저자들이 개발한 TT800 생성기의 개선판으로기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할  있도록 설계되었다.

메르센 트위스터의 이름은 난수의 반복 주기가 메르센 소수 데에서 유래했다메르센 트위스터는  속도와 난수의 품질 때문에 점점 많은 곳에서 채택되고 있으며흔히 주기가 219937 − 1 MT19937 사용한다. MT19937 같으나 생성해 내는 난수가 32비트가 아닌 64비트인MT19937-64 쓰이며2006년에 동일한 저자들이 발표한 SIMD 기반 메르센 트위스터는 MT19937 비해 대략  정도 빠른 것으로 알려져 있다.

난수의 품질에도 불구하고메르센 트위스터는 암호학적으로 안전한 유사난수 생성기 아니다 난수의 특성(주기난수 범위) 알고 있을  유한한 수의 난수( 경우 624)만으로 현재 생성기의 상태를 알아   있으며 뒤에 나올 난수를 예측해   있다암호학적으로안전한 유사난수 생성기를 얻기 위해서는 해시 함수 사용해야 하지만 난수의 생성 속도가 낮아진다또는 블룸 블룸 (BBS) 같이 암호학적으로 안전하게 설계된 생성기를  수도 있다.

 

< 출처 : 위키피디아 >

 

메르센 트위스터는 현재도 가장 널리 사용되고 있는 랜덤 생성기입니다. C++에서는 Boost에도 이 MT 랜덤 생성기가 구현 되어 있습니다. 또한 MATLAB, Ruby, Python등의 언어에서도 기본 난수 알고리즘으로 채택되어서 사용 되고 있습니다. 뭐 물론 단점이 없는 건 아니지만, 장점이 훨씬 더 크기 때문에 표준으로 채택이 되었겠죠. ^^

그리고 가장 큰 장점은 특별히 따로 구현하지 않아도, Boost에 포함되어 있기 때문에, Boost만 있다면 바로 사용이 가능하다는 장점이 있습니다. 사용 방법에 관해서는 하단의 참조 링크에서 확인하실 수 있습니다.

 

WELL

WELL은 위 MT의 디자이너가 10년후에 고안한 난수 발생 알고리즘 입니다. 그의 주장에 따르면 MT보다 40% 빠르고 코드도 더 간단합니다. WELL은 분포도에 따라서 WELL512, WELL1024, WELL19947, WELL44497의 종류가 있습니다. 숫자가 클수록 분포도가 높긴 하지만, 게임에서 사용하기엔 512나 1024만으로도 충분할 것 같습니다.

WELL의 구현 코드는 이곳에서 받을 수 있습니다. 실제로 보면 정말 구현은 간단합니다.

아래가 WELL512의 구현 코드입니다.

이게 다입니다. Period는 이름 그대로 2^512입니다. 그렇다 해도 일반 PC로 저걸 세는데 10^100년이 걸린다고 하는군요. 초나 분이 아니라 년 말입니다. (googol years라고 부른다고 하는군요)

사용법은 위의 state만 적절히 초기화 해주고, 함수를 호출하면 32비트 정수(난수)가 리턴됩니다.

 

간단한 시물레이터로 두 난수 발생기를 시뮬레이팅 해 보았을 때의 차이를 보여드리겠습니다.


C/C++의 rand함수


WELL512 알고리즘

 

<이미지 출처 : binsoo Blog >

 

일반적으로 게임 개발할때는 이런 랜덤 생성기까지 필요 하지 않을지도 모릅니다. 그러나 MMORPG와 같이 랜덤이 게임의 밸런스에 큰 영향을 끼치는 경우에는, 서버 측에서 이런 고성능의 랜덤 생성기가 필요한 경우가 많습니다. 유저나 해커가 랜덤값을 함부로 예측해서는 안되니까요. ^^; 그리고 저의 경우 처럼 랜덤 시드를 이용해서 이벤트 동기화를 맞추는 경우에는 전역 함수인 rand()를 사용할 수 없기 때문에 꼭 이런 랜덤 함수가 별도로 필요합니다. 그런 경우에 굳이 이런 좋은 난수 알고리즘들을 놔두고 새로 짜는 고생은 안하는게 낫겠죠.(그렇다고 내가 만든 알고리즘이 저것보다 좋을리는 택도 없을 테니…=ㅅ=;)

 


신고
Posted by 준환이형님

댓글을 달아 주세요


지난번처럼 설명을 자세하게 적고 싶었는데.. 하다보니 코드가 너무 길어졌네요 ;ㅁ;


리스트를 이용하여 구현한 삽입정렬, 버블정렬입니다.


배열로 구현한 삽입정렬(http://topnanis.tistory.com/12)과 버블정렬(http://topnanis.tistory.com/11)은  링크를 참조하세요.


싱글로 할 걸 굳이 더블 링크로 구현 한 이유는.. 퀵정렬을 구현하려다.. 그만 두었기 때문이죠.. 막판에 넣은 스왑 디파인아까워..ㅠ

퀵정렬시에는 재귀 함수에 인자값으로 배열의 크기(+피봇), 시작지점이 필요하므로 더블링크드가 더 적합하겠다 싶었습니다(배열쪽이 훨씬 편리한 것 같아요)

 

아래에 소스 첨부하였습니다.  


sort.cpp






#include <iostream>

#include <Windows.h>


#define SWAP(x,y,t) (t=x), (x=y), (y=t)                 //스왑을 정의(못써먹음,아까워;ㅁ;)


using namespace std;


class Node         //노드를 정의

{

public:

int val;

Node *head;

Node *tail;

};


class Link         //더블리스트클래스

{

private:

bool BubbleOrderAscending();         //버블(오름)

bool BubbleOrderDescending();         //버블(내림)

void InsertOrderAscending();         //삽입(오름)

void InsertOrderDescending();         //삽입(내림)


void Col(int color);

void ShowAll();         //링크출력


public:

Node *lHead;         //링크전체의 헤더

Node *tempPoint;         //생성시 동적할당을 위한 노드


Link()         //초기화

{

lHead = new Node();

lHead->head=NULL;         //초기화 하지 않으면 값 넣을때 에러발생

lHead->tail=NULL;         //초기화 하지 않으면 검색시 에러발생

}


void AddLilk(int val)             //노드추가

{

cout<<"add"<<endl;

tempPoint= new Node();         //노드 생성시 동적할당


lHead->head=tempPoint;         //링크 헤더연결


tempPoint->val=val;         //링크 값

tempPoint->tail=lHead;         //링크 테일연결


lHead=tempPoint;         //주소저장


ShowAll();

}


void revShowAll()         //링크 역출력

{

cout<<endl<<"Show Reverse"<<endl;

Node *schPoint= lHead;


while(schPoint->tail->val!=NULL) schPoint=schPoint->tail;

while(schPoint->head!=NULL)

{

if(schPoint->val>=100)Col(15);         //값 크기에 따라 색상(10:녹, 14:황, 15:백)

else if(schPoint->val>=10)Col(14); else Col(10);

cout<<schPoint->val<<"->";

schPoint=schPoint->head;

}

cout<<schPoint->val<<"->";

Col(15);

cout<<endl;


}


void InsertUp() //삽입정렬(오름)스위치

{

cout<<endl<<"Ascending(Insert)"<<endl;

InsertOrderAscending();

}


void InsertDown() //삽입정렬(내림)스위치

{

cout<<endl<<"Decending(Insert)"<<endl;

InsertOrderDescending();

}


void BubbleUp() //버블정렬(오름)스위치

{

cout<<endl<<"Ascending(bubble)"<<endl;

while(BubbleOrderAscending());

}


void BubbleDown() //버블정렬(내림)스위치

{

cout<<endl<<"Decending(bubble)"<<endl;

while(BubbleOrderDescending());

}

};


void Link::InsertOrderAscending()

{

tempPoint=lHead; //기준포인트

tempPoint=tempPoint->tail;         //삽입정렬 초기- 두 수를 비교하기 위해 기준블럭을 한 칸 이동 


while(tempPoint->tail!=NULL)

{

ShowAll();

//노드를 이용한 for문 참조_ serchP는 시작지점에서 기준블럭전 까지 비교하기 위한 포인터

for(Node *serchP = lHead; serchP->val!=tempPoint->val; serchP=serchP->tail)

{

if(serchP->val>tempPoint->val)

{

int tempVal = serchP->val;

serchP->val = tempPoint->val;

tempPoint->val = tempVal;

}

}

tempPoint=tempPoint->tail;

}

ShowAll();

}


void Link::InsertOrderDescending()

{

tempPoint=lHead;

tempPoint=tempPoint->tail;


while(tempPoint->tail!=NULL)

{

ShowAll();


for(Node *serchP = lHead; serchP->val!=tempPoint->val; serchP=serchP->tail)

{

if(serchP->val<tempPoint->val)

{

int tempVal = serchP->val;

serchP->val = tempPoint->val;

tempPoint->val = tempVal;

}

}

tempPoint=tempPoint->tail;

}

ShowAll();

}


bool Link::BubbleOrderAscending()

{

ShowAll();


bool isContinue=false;

tempPoint= lHead;


while(tempPoint->tail->tail!=NULL)

{

if(tempPoint->val>tempPoint->tail->val)

{

isContinue=true;


int temp=tempPoint->val;

tempPoint->val=tempPoint->tail->val;

tempPoint->tail->val=temp;

}

tempPoint=tempPoint->tail;

}

return isContinue;

}

bool Link::BubbleOrderDescending()

{

bool isContinue=false;

tempPoint= lHead;


while(tempPoint->tail!=NULL)

{

if(tempPoint->val<tempPoint->tail->val)

{

isContinue=true;


int temp=tempPoint->val;

tempPoint->val=tempPoint->tail->val;

tempPoint->tail->val=temp;

}

tempPoint=tempPoint->tail;

}

ShowAll();

return isContinue;

}


void Link::ShowAll()

{

Node *schPoint= lHead;


while(schPoint->tail!=NULL)

{

if(schPoint->val>=100)Col(15);else if(schPoint->val>=10)Col(14); else Col(10);

cout<<schPoint->val<<"->";

schPoint=schPoint->tail;

}

Col(15);

cout<<endl;

}


void Link::Col(int color) 

{

int bgcolor=NULL;

color &= 0xf;

bgcolor &= 0xf;

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (bgcolor << 4) | color);

}


int main() //메인

{

Link *link = new Link();


link->AddLilk(86);

link->AddLilk(1);

link->AddLilk(13);

link->AddLilk(4);

link->AddLilk(11);

link->AddLilk(226);

link->AddLilk(104);


link->BubbleUp();

link->BubbleDown();


link->revShowAll();


link->InsertUp();

link->InsertDown();


return 0;

}




신고
Posted by 준환이형님

댓글을 달아 주세요

  1. c++ 삽입 2014.04.14 19:07 신고 Address Modify/Delete Reply

    c++ 삽입정렬


비타민처럼 먹어오던 알고리즘 문제를 이 놈한테 막혀서 한동안 쉬었죠. (제가 좀 부족해요..ㅠ)


마지막 테스트케이스(100 100)에서 자꾸 오답이 나왔는데. 알고보니 다른 축 타일은 세지 않아서 그런거 였답니다.. (먼산)
 
  



출처:.cis.uab.edu 2008 high school programming contest

프로그램 명: tiles(open)
제한시간: 1 초
바닥에 타일을 깔기 위해 필요한 타일수를 구하는 것이다.

타일의 크기는 8*8 이다. 타일은 그대로 이용할 수도 있고 잘라서 부분을 이용할 수도 있다. 그런데 잘라서 사용한 타일의 나머지는 반드시 버려야 한다.

문제는 사용되어진 온전한 타일수와 잘라서 사용한 타일수를 구하는 것이다. 모든 단위는 inch 이고 생략한다.

입력

방의 가로 , 세로 크기가 주어진다. 각 수는 1000 이하이다.

출력

출력 예의 형식으로 출력한다.

입출력 예

입력

160 240

출력

The number of whole tiles is 600 part tiles is 0

입력

100 120

출력

The number of whole tiles is 180 part tiles is 15

입력

100 100

출력
The number of whole tiles is 144 part tiles is 25 
신고
Posted by 준환이형님

댓글을 달아 주세요


영상 라벨링을 할 일이 생겨서 만들었어요 (인터넷에서..소스를 못찾았던 거죠 ㅠ)

글래스파이어(GrassFire) 알고리즘은

잔디에 불이 붙어서 불붙은 곳을 중심으로 주변이 야금야금 타들어가듯이 씨드와 같거나 유사한 주변의 객체의 값을 바꾸는 구조로 되어 있습니다.

예전엔 어떻게 했었는지 정확히 기억이 나지 않는데.. '야금야금'이 되려면 재귀가 되어야 할 것 같아서 그렇게 구현 해 보았습니다.



보통 이렇게 일치 시킨 값을 하나로 묶어 사용하는 일이 많고 구조가 복잡하지 않기 때문에 라벨링의 기본 알고리즘으로 많이 사용됩니다.

(교수님께서는 너 '라벨링' 그거 촌스러운 발음, '레~이블링'이라고 발음하라고 말씀하셨었죠. 문득 기억이 나는군요)

영상처리를 위해 배우긴 하였으나 게임 내 적군의 길찾기 알고리즘으로 쓰이기도 했지요

(이것을 응용한 게임을 보시려면 다음링크를 클릭 해 주세요 ->  http://topnanis.tistory.com/100 ) 

 

'GrassFire'라니.. 무척 직관적인 이름 아닌가요?



결과값의 첫번째는 기본값, 두번째는 라벨링, 세번째는 라벨링된 크기값 출력 입니다. 생각해보니.. 타들어가는 모습을 캡쳐 할 껄, 잘 못했네요

아래에 소스코드와 실행파일을 첨부합니다.


labeling.cpp

labeling.exe

--------------------------------------------------------------------------------------------------------------------------------------------

2012.9.5 수정하여 다시 올립니다. 배열을 늘리고, 테두리 부분 예외처리를 추가 하였습니다.

(혹시 실행했는데 MSVCR100.dll 에러가 발생하시면 VS2010 재배포패키지를 받아주세요.; http://topnanis.tistory.com/201 )


GrassFire(20x25).cpp

GrassFire(20x25).exe




신고
Posted by 준환이형님

댓글을 달아 주세요

  1. 온순한감자 2011.09.23 23:38 신고 Address Modify/Delete Reply

    맥에서는 실행이 안되요 ㅠㅠ

  2. 초심자 2012.06.29 23:45 신고 Address Modify/Delete Reply

    안녕하세요, 영상처리에 대해 관심이 있는 학생인데...이번에 영상인식에 대해 공부를 하고있습니다. 완전 초보라 이 알고리즘의 응용에대해서 여쭤보고 싶은데요....
    혹시 캡쳐한 영상을 특정 색에 대해 이진화한 배열에도 사용할 수 있을까요? 그리고 일정기준 갯수이상을 가진 라벨이 존재한다면 그 라벨이 무엇인지 찾을수도 있을까요?


알고리즘 문제를 풀고 싶다면 아래 주소를 참고하세요. 저도 시간 날 때마다 풀고 있답니다~

30계단을 하나씩 풀면서 느끼는 소소한 재미가 있어요 :D

http://211.228.163.31/index.php





1. 구글 코드 잼
    :
 http://code.google.com/codejam/

2. 알고스팟
      : http://algospot.com/
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

ACM - 타일수 구하기 문제 tiles(open)  (0) 2011.10.06
C - GrassFire 라벨링 알고리즘  (2) 2011.09.21
알고리즘 사이트 모음  (0) 2011.09.19
Algorithm - Counting Sort  (1) 2011.03.30
C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
Posted by 준환이형님

댓글을 달아 주세요


오늘.. 수업시간에 이게 나왔는데.. ㅋ

제목 느낌상 어려울 것 같지는 않았는데 왠일인지 들어도 무슨 말인지 도통 이해가 가지 않아서..

왜 난 못 알아듣지를 왜 난 못알아듣지를 혼자 반복하다가.. 

잘 설명해 놓은 블로그가 있길래 포스팅합니다. (교수님이 설명을 어렵게 하신거였어요~ㅋㅋ)

카운팅소트의 특징은 안정적으로 정렬하므로.. 짬밥이 같은 숫자라도 순서를 잘 유지해서 정리 해준대요  :D


출처: http://redwave102.blog.me/80076259189

계수 정렬(Counting Sort)

 

  • 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.

  • 계수 정렬의 개념
    • 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘
    • 속도가 빠르며 안정적이다.
    • 제한 사항
      • 정수나 정수로 표현할 수 있는 자료에 대해서만 동작
      • 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

 

  • 계수 정렬 수행 과정

    •  

      1단계

      1. Data에서 각 항목들의 발생 횟수를 센다.
      2. 횟수들은 정수 항목들로 직접 인덱스 되는 카운트 배열 Counts에 저장

    • 1단계 
      3. 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위하여 카운트들을 조정한다.

    • 2단계 : 정렬된 집합
      1. Temp에 1을 삽입하고 Counts[1]을 감소시킨 후

    • 2단계 : 정렬된 집합
      2. Temp에 4을 삽입하고 Counts[4]을 감소시킨 후

    • 2단계 : 정렬된 집합
      3. Temp에 2을 삽입하고 Counts[2]을 감소시킨 후

    • 2단계 : 정렬된 집합
      4. Temp에 1을 삽입하고 Counts[1]을 감소시킨 후

    • 2단계 : 정렬된 집합
      5. Temp에 3을 삽입하고 Counts[3]을 감소시킨 후


    • 2단계 : 정렬된 집합
      6. Temp에 0을 삽입하고 Counts[0]을 감소시킨 후

신고

'3_ 담백한알고리즘' 카테고리의 다른 글

C - GrassFire 라벨링 알고리즘  (2) 2011.09.21
알고리즘 사이트 모음  (0) 2011.09.19
Algorithm - Counting Sort  (1) 2011.03.30
C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
Posted by 준환이형님

댓글을 달아 주세요

  1. Denial 2011.05.09 08:24 신고 Address Modify/Delete Reply

    와... 정리 진짜 깔끔하네요 ㅎㅎ

엑셀을 만들라는 문제..드뎌 온갖 야매란 야매는 다 써서 풀었답니다~ ㅋㅋㅋ
D. 휴대폰번호 정렬
(Time Limit: 2 seconds)
LK 텔레콤에 근무하는 신입사원 정희에게 부장님이 새로운 업무를 지시했다. 고객들의 휴대폰 전화번호를 정렬하는 작업이다.
휴대폰 번호는 국번 3 자리와 중간국번 3자리 또는 4자리, 그리고 뒷 자리 수 4 자리로 총 10 개 혹은 11 개의 숫자로 이루어진다.
그리고 휴대폰 국번은 010, 011, 016, 017, 018, 019 의 여섯 가지가 존재한다. 국번과 중간국번, 뒷자리 수는 하이픈(“-”)으로 구분된다. 부장님이 원하는 요구사항은 다음과 같다. 우선, 특정 국번 번호 순서로 정렬이 되어야 하며, 국번이 같은 경우에는 중간국번 숫자끼리 비교해서 오름차순 정렬이 되어야 하며, 중간국번도 같은 경우에는 뒷자리 번호를 비교해서 오름차순으로 정렬이 되야 한다. 단, 부장님이 원하는 정렬순서는 국번이 같을 경우 중간국번 4 자리인 휴대폰 번호가 중간국번 3 자리인 휴대폰 번호보다 항상 정렬 우선순위가 높다. 즉, 국번이 같은 경우 중간국번 4 자리인 휴대폰 번호가 중간국번 3자리인 휴대폰 번호보다 정렬 시 항상 먼저 등장한다. 예를 들어, 다음과 같은 휴대폰 번호를 정렬한다고 하자.

011-275-3587
017-1111-2600
019-222-2222
017-111-1234
018-275-9562
010-333-1111
016-1235-3333
이 번호들을 017 / 011 / 018 / 019 / 010 / 016 국번 순으로, 그리고 중간국번 4 자리가 중간국번 3자리보다 우선순위가 높도록 정렬을 한다면, 아래와 같이 정렬이 될 것이다.
017-1111-2600
017-111-1234
011-275-3587
018-275-9562
019-222-2222
010-333-1111
016-1235-3333
위의 결과에서 첫 번째 라인의 017-1111-2600 과 두 번째 라인의 017-111-1234 를 비교해보면, 중간국번 111 은 1111 보다 작으므로 일반적으로는 정렬 시 017-111-2600 이 먼저 등장해야 하나, 부장님의 요구사항에서 중간국번 4 자리가 중간국번 3 자리보다 항상 정렬 우선순위가 높다는 규칙 때문에 017-1111-2600 이 017-111-1234 보다 먼저 등장한 것을 알 수 있다.
Input
첫 줄에는 테스트 케이스의 개수 T ( 0 < T <= 20 ) 가 주어진다.각각의 테스트케이스의 첫 번째 줄에는 정렬할 휴대폰 번호의 개수 N(0 < N <= 50) 이 주어진다.테스트케이스의 두 번째 줄에는 0, 1, 6, 7, 8, 9 의 6개의 숫자가 임의의 순서로 표시된다.이 숫자들은 휴대폰 국번을 의미하며, 6개의 숫자들이 나열되는 순서는 테스트 케이스마다 바뀔수 있다. 당신은 이 순서대로 국번 별 순서로 휴대폰번호를 정렬해야 한다.예를 들어, 숫자 7 1 8 9 0 6 이 표시됐다면 017 / 011 / 018 / 019 / 010 / 016 국번 순으로 정렬해야 한다. 세 번째 줄부터는 라인 당 하나씩의 휴대폰 번호가 N 개 만큼 입력된다. 휴대폰 번호에서 국번은
010, 011, 016, 017, 018, 019 의 여섯 가지만 입력되며, 휴대폰 번호는 0 부터 9 까지의 숫자와 “–“ 로 구성되며, 빈칸을 포함하지 않으며 그 외 다른 문자는 포함되지 않는다. 참고로, 우리나라 휴대폰 번호에서 010 국번의 경우 중간국번은 항상 4 자리지만 이 문제에서는 010 국번도 중간 국번이 3 자리가 될 수 있다고 정의한다. 즉, 모든 휴대폰번호는 국번에 상관없이 중간국번이 세자리 혹은 네 자리가 될 수 있다.
#include 
#include 		// atoi
#include 		// abs

#define SWAP(x,y,t) (t=x), (x=y), (y=t)		//스왑정의

typedef struct phone_num
{
	unsigned int fst_num;	//사업자번호 (010등)
	unsigned int snd_num;	//나머지번호
}num;

int main(void)
{
	num list[50];			//스트럭쳐 50개
	num list_temp;			//스왑에 사용할 스트럭쳐 한개 
	char in_txt[14];		//문자열 배열
	int N, repeat, temp;	//번호갯수, 테스트케이스, 스왑용변수
	int st_num[6];			//사업자번호 끝자리 정렬용

	scanf("%d",&repeat);
	
	for(int z=0; z[repeat; z++)
	{
	scanf("%d",&N);		
	scanf("%d %d %d %d %d %d ",&st_num[0], &st_num[1], &st_num[2], &st_num[3], &st_num[4], &st_num[5]);
	
	for(int i=0; i[N; i++)
	{
		gets(in_txt);

		list[i].fst_num=atoi(in_txt+2);		//사업자번호 끝자리만 숫자로 변경하여 구조체에 넣음 
		list[i].snd_num=atoi(in_txt+4)*10000+abs(atoi(in_txt+8));	// 중간자리를 받아 10000을 곱함 + 끝자리를 받아 중간자리에 더함
	}

	for(int i=0; i[N; i++)	// 삽입정렬
	{
		if(list[i].snd_num>list[i-1].snd_num){temp=list[i].snd_num;}else{continue;}
		
		for(int j=0; j[N; j++)
		{
			if(list[j].snd_num[temp){SWAP(list[i], list[j], list_temp);}
		}
	}
	printf("------------------\n");

	for(int j=0; j[6; j++)	//정렬된 수를 사업자 번호의 순서에 맞게 출력
	{
		for(int i=0; i[N; i++)
		{
			if(st_num[j]==list[i].fst_num){printf("01%d-%d-%d\n", list[i].fst_num, list[i].snd_num/10000, list[i].snd_num%10000);}
		}
	}
	printf("------------------\n");
	}

	return 0;
}
 
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

알고리즘 사이트 모음  (0) 2011.09.19
Algorithm - Counting Sort  (1) 2011.03.30
C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
Posted by 준환이형님

댓글을 달아 주세요

예전에 우리 벽보를 함부로 덮은 타동아리 포스터 면적을 계산해서 따지러가는 문제가 있었는데 그거랑 유사하네요. 스토리도 은근탄탄 ㅋ


 임씨는 1950년 한국전쟁으로 많은 손해를 본 사람들 중 하나다. 전쟁 통에 손해보지 않은 사람이 어디 있을까 만은 그는 6.25가 일어나기 전만 해도 충청도 지방에 넓은 대지를 소유한 큰 부자였다. 전쟁이 나자 임씨는 땅문서와 값 나가는 것들만 챙겨서 일본으로 피난을 가지만 피난 중에 그만 땅문서를 잃어버리고 만다. 전쟁이 끝난 후에 임씨의 땅은 이미 다른 사람들의 논밭이 되어 있었고, 임씨는 땅을 되찾으려 했지만 문서가 없으니 생떼 쓰는 것과 다를 바 없었다. 이러다가 임씨는 길바닥에 나앉게 생겼다.
이 때, 임씨에게 좋은 생각이 떠올랐으니 바로 자신이 습관처럼 땅 깊숙이 뭔가 표식을 해놓았던 사실이다. 임씨는 한적할 때마다 자신의 논밭을 거닐다가 땅속 깊은 곳에 자신의 이름이 씌어진 옥구슬을 묻어놓았던 것이다. 즉, 어떤 지점에서 그의 이름이 적힌 옥구슬이 나온다면 그 지점은 예전에 임씨의 땅이었다는 것을 증명하는 것이다.
  임씨는 즉시 민사소송을 통해 자신의 땅을 찾고자 했고 논리적인 근거를 들어 옥구슬이 나오는 지점이 원래 자신의 땅의 한 지점이었다는 것을 주장하여 결국 담당판사를 설득하는 데에 성공하였다. 담당판사는 다음과 같은 판결을 내렸다. "6.25이전의 개인소유 대지들은 99%가 남북, 동서 방향으로 평행한 직사각형 모양이었으므로, 임씨의 이름이 새겨진 옥구슬이 나오는 모든 지점을 포함하는 가장 작은 남북, 동서 방향으로 평행한 변을 갖는 직사각형의 대지를 임씨의 소유로 인정한다." 임씨는 많은 손해를 보는 셈이지만 더 이상을 요구할 만한 근거가 없었기 때문에 이 판결을 따르기로 했다.

  임씨의 이름이 새겨진 옥구슬의 위치 N 개가 주어질 때에, 임씨에게 돌아갈 대지의 넓이를 계산하는 프로그램을 작성하시오. 단, 옥구슬의 위치는 2차원 정수 좌표로 주어지고 옥구슬은 같은 위치에 여러 개가 발견될 수도 있으며, x축의 양의방향을 동쪽, y축의 양의방향을 북쪽이라고 가정한다. 
 

   예를 들어 위와 같이 (2, 1), (3, 2), (5, 2), (3, 4) 네 점에서 옥구슬을 발견하였다면, 임씨에게 돌아갈 대지는 (2, 1), (5, 1), (2, 4), (5, 4)를 네 꼭지점으로 하는 직사각형이며, 넓이는 (5 - 2) × (4 - 1) = 9가 된다.
 
입력
입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에는 점의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다. 이어지는 N 줄에는 각 점의 좌표가 두 개의 정수로 한 줄에 하나씩 주어진다. 각각의 좌표는 -10,000 이상 10,000 이하의 정수이다.

출력
출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 N 개의 점을 둘러싸는 최소 크기의 직사각형의 넓이를 출력하시오.

#include 
#include 

int main(void)
{
	int num,x,y,dir_N,dir_E,dir_W,dir_S;
	
	dir_N=dir_E=-10000;		//디폴트
	dir_W=dir_S=+10000;

	scanf("%d",&num);

	for(int i=0; i[num; i++)
	{		
		scanf("%d %d",&x,&y);

		if(y]dir_N){dir_N=y;}
		if(y[dir_S){dir_S=y;}
		if(x]dir_E){dir_E=x;}
		if(x[dir_W){dir_W=x;}
	}
	printf("%d\n",abs(dir_E-dir_W)*abs(dir_N-dir_S));
	return 0;
} 
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

Algorithm - Counting Sort  (1) 2011.03.30
C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
C- ACM - 지뢰찾기  (4) 2010.06.23
Posted by 준환이형님

댓글을 달아 주세요

양말 짝을 맞추는 문제입니다. 저는 젓가락 행진곡 처럼 양 끝에서 가운데로 한짝씩 맞춰나가는 문제라고 이해하고 풀었어요~/ 

양말 장사를 하는 지훈이는 오랜만에 창고 정리를 하기로 했다. 창고에는 양말짝이 맞지 않은 채 가득 섞여 있었다. 이제 지훈이를 도와 어지럽게 섞여있는 양말의 짝을 맞추어 보자.
- 양말의 종류는 알파벳으로 구분된다.
- 양말의 오른짝은 소문자, 왼짝은 대문자이다.
  즉, Jj가 J 양말의 한 쌍이며, aB는 a양말의 오른짝과 B양말의 왼짝이므로 짝이 맞지 않는다. 
입력의 첫 번째 줄은 테스트 케이스의 개수 T ( 0 < T <= 30)가 주어지며, 각 테스트 케이스는 한 줄에 하나씩 창고에 있는 양말이 종류와 짝에 상관없이 연속으로 입력된다. 최대 입력되는 양말의 개수는 100개이며, 테스트 케이스에는 알파벳 대소문자만이 입력된다.  하나의 테스트 케이스마다 한 줄씩 출력하며, 주어진 양말의 모든 짝이 맞는다면 ‘YES’를 출력하며, 양말의 짝이 맞지 않는 경우는 ‘NO’를 출력한다. 

aaAA ->YES
CAdBb ->NO
Bab ->NO

#include <stdio.h>
#include <math.h>
int CASE()
{
 int tail=30; 
 char sox[30];
 gets(sox);
 while(sox[tail--]);              // 끝에서부터 NULL값을 찾음
 if(tail%2==0){return 0;}    // 양말 홀수개의 입력이면 리턴 0을 반환함
 for(int i=0; i[tail; i++)
 {  
  if(abs(sox[i]-sox[tail])==32){tail--; continue;}  // 짝이 일치할때 회문을 도는 형식
  else return 0;                                                 // 한번이라도 일치하지 않으면 리턴 0을 반환함
 }
 return 1;
}
int main(void)
{
 int repeat;
 scanf("%d",&repeat);
 fflush(stdin);              // 스캔에서의 엔터값 버퍼를 비움
 for(int i=1; i[=repeat; i++)
 {
  if(CASE())printf("Case #%d:\nYES\n",i);
  else{printf("Case #%d:\nNo\n",i);}
 }
 return 0;
}  
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
C- ACM - 지뢰찾기  (4) 2010.06.23
C- ACM - 수 뒤집기  (0) 2010.06.12
Posted by 준환이형님

댓글을 달아 주세요

ㅋㅋㅋ 이런 문제 좋음~
정희는 한 음악 포털 사이트에서 일정 금액을 충전하여 mp3파일을 다운로드 받아서 사용해 왔다.
지금 이 사이트에서 k곡을 다운받으면 한 곡을 무료로 다운받을 수 있는 이벤트를 진행 중이고, 현재 정희가 다운받을 수 있는 mp3파일의 개수는 n개이다. 이벤트 기간 중 정희가 다운받을 수 있는 총 mp3파일의 개수는 몇 개인가?
첫 줄에는 테스트 케이스의 개수 T ( 0 < T <= 100000 ) 가 주어진다.
한 줄당 하나의 입력이 입력되며, 각 입력 케이스는 n과 k 두 개의 정수로 이루어져 있고, 하나의 스페이스로 구분된다. ( 0 < n < 1000000, 1 < k <= 21)
각 테스트 케이스에 대해 각 케이스마다 정희가 다운받을 수 있는 총 mp3파일의 개수를 출력한다.
4 3   ->5
10 3  ->14
100 5 -> 124
#include 

int main(void)
{
	int n ,k, plus;
	scanf("%d %d",&n, &k);
	
	plus=n/k;
	plus+=plus/k;
	
	printf("%d %d -> %d\n",n,k,plus+n);

	return 0;
} 
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
C- ACM - 지뢰찾기  (4) 2010.06.23
C- ACM - 수 뒤집기  (0) 2010.06.12
C- ACM - 소수판정  (0) 2010.06.09
Posted by 준환이형님

댓글을 달아 주세요