본문 바로가기

3_ 담백한알고리즘16

C# - 표준 rand()함수보다 유용한 랜덤 생성 알고리즘 – MT, WELL 게임 프로그래밍중 좋은 포스팅이 있어 공유합니다 출처 : 알콜코더 : http://www.gamedevforever.com/114 안녕하세요. 알콜코더 민군입니다. 현재 제작 중인 게임에서, 랜덤 시드 값을 일치 시켜서, 랜덤 결과를 서로 다른 클라이언트끼리 동기화 시키는 작업을 진행 하였습니다. 랜덤 시드값만 서로 일치시키면, 이후에 생성되는 랜덤 함수의 결과값들은 모두 일치가 되기 때문에, 예전에 스타크래프트와 같은 패키지 게임에서 자주 사용했던 테크닉입니다. ^^; 서로 다른 클라이언트끼리 처음 시드값만 일치 시키면, 이후의 랜덤값은 정해져 있기 때문에, 그 랜덤값을 사용한 이벤트등의 동기화에 사용하는 것이죠. 이런 테크닉은 패키지 게임 시절에는 리플레이 저장이나 네트워크 동기화등에서 상당히 많이 .. 2014. 4. 11.
C++ - 더블 링크드리스트로 구현한 삽입, 버블정렬 지난번처럼 설명을 자세하게 적고 싶었는데.. 하다보니 코드가 너무 길어졌네요 ;ㅁ; 리스트를 이용하여 구현한 삽입정렬, 버블정렬입니다. 배열로 구현한 삽입정렬(http://topnanis.tistory.com/12)과 버블정렬(http://topnanis.tistory.com/11)은 링크를 참조하세요. 싱글로 할 걸 굳이 더블 링크로 구현 한 이유는.. 퀵정렬을 구현하려다.. 그만 두었기 때문이죠.. 막판에 넣은 스왑 디파인아까워..ㅠ퀵정렬시에는 재귀 함수에 인자값으로 배열의 크기(+피봇), 시작지점이 필요하므로 더블링크드가 더 적합하겠다 싶었습니다(배열쪽이 훨씬 편리한 것 같아요) 아래에 소스 첨부하였습니다. #include #include #define SWAP(x,y,t) (t=x), (x=y),.. 2012. 6. 1.
ACM - 타일수 구하기 문제 tiles(open) 비타민처럼 먹어오던 알고리즘 문제를 이 놈한테 막혀서 한동안 쉬었죠. (제가 좀 부족해요..ㅠ) 마지막 테스트케이스(100 100)에서 자꾸 오답이 나왔는데. 알고보니 다른 축 타일은 세지 않아서 그런거 였답니다.. (먼산) 출처:.cis.uab.edu 2008 high school programming contest 프로그램 명: tiles(open) 제한시간: 1 초 바닥에 타일을 깔기 위해 필요한 타일수를 구하는 것이다.타일의 크기는 8*8 이다. 타일은 그대로 이용할 수도 있고 잘라서 부분을 이용할 수도 있다. 그런데 잘라서 사용한 타일의 나머지는 반드시 버려야 한다. 문제는 사용되어진 온전한 타일수와 잘라서 사용한 타일수를 구하는 것이다. 모든 단위는 inch 이고 생략한다. 입력방의 가로 , .. 2011. 10. 6.
C - GrassFire 라벨링 알고리즘 영상 라벨링을 할 일이 생겨서 만들었어요 (인터넷에서..소스를 못찾았던 거죠 ㅠ) 글래스파이어(GrassFire) 알고리즘은 잔디에 불이 붙어서 불붙은 곳을 중심으로 주변이 야금야금 타들어가듯이 씨드와 같거나 유사한 주변의 객체의 값을 바꾸는 구조로 되어 있습니다. 예전엔 어떻게 했었는지 정확히 기억이 나지 않는데.. '야금야금'이 되려면 재귀가 되어야 할 것 같아서 그렇게 구현 해 보았습니다. 보통 이렇게 일치 시킨 값을 하나로 묶어 사용하는 일이 많고 구조가 복잡하지 않기 때문에 라벨링의 기본 알고리즘으로 많이 사용됩니다. (교수님께서는 너 '라벨링' 그거 촌스러운 발음, '레~이블링'이라고 발음하라고 말씀하셨었죠. 문득 기억이 나는군요) 영상처리를 위해 배우긴 하였으나 게임 내 적군의 길찾기 알고리.. 2011. 9. 21.
알고리즘 사이트 모음 알고리즘 문제를 풀고 싶다면 아래 주소를 참고하세요. 저도 시간 날 때마다 풀고 있답니다~ 30계단을 하나씩 풀면서 느끼는 소소한 재미가 있어요 :D http://211.228.163.31/index.php 1. 구글 코드 잼 : http://code.google.com/codejam/ 2. 알고스팟 : http://algospot.com/ 2011. 9. 19.
Algorithm - Counting Sort 오늘.. 수업시간에 이게 나왔는데.. ㅋ 제목 느낌상 어려울 것 같지는 않았는데 왠일인지 들어도 무슨 말인지 도통 이해가 가지 않아서.. 왜 난 못 알아듣지를 왜 난 못알아듣지를 혼자 반복하다가.. 잘 설명해 놓은 블로그가 있길래 포스팅합니다. (교수님이 설명을 어렵게 하신거였어요~ㅋㅋ) 카운팅소트의 특징은 안정적으로 정렬하므로.. 짬밥이 같은 숫자라도 순서를 잘 유지해서 정리 해준대요 :D 출처: http://redwave102.blog.me/80076259189 계수 정렬(Counting Sort) 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나. 계수 정렬의 개념 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘 속도가.. 2011. 3. 30.
C- ACM - 휴대폰번호 정렬 엑셀을 만들라는 문제..드뎌 온갖 야매란 야매는 다 써서 풀었답니다~ ㅋㅋㅋ D. 휴대폰번호 정렬 (Time Limit: 2 seconds) LK 텔레콤에 근무하는 신입사원 정희에게 부장님이 새로운 업무를 지시했다. 고객들의 휴대폰 전화번호를 정렬하는 작업이다. 휴대폰 번호는 국번 3 자리와 중간국번 3자리 또는 4자리, 그리고 뒷 자리 수 4 자리로 총 10 개 혹은 11 개의 숫자로 이루어진다. 그리고 휴대폰 국번은 010, 011, 016, 017, 018, 019 의 여섯 가지가 존재한다. 국번과 중간국번, 뒷자리 수는 하이픈(“-”)으로 구분된다. 부장님이 원하는 요구사항은 다음과 같다. 우선, 특정 국번 번호 순서로 정렬이 되어야 하며, 국번이 같은 경우에는 중간국번 숫자끼리 비교해서 오름차순.. 2010. 7. 13.
C- ACM - 대지 예전에 우리 벽보를 함부로 덮은 타동아리 포스터 면적을 계산해서 따지러가는 문제가 있었는데 그거랑 유사하네요. 스토리도 은근탄탄 ㅋ 임씨는 1950년 한국전쟁으로 많은 손해를 본 사람들 중 하나다. 전쟁 통에 손해보지 않은 사람이 어디 있을까 만은 그는 6.25가 일어나기 전만 해도 충청도 지방에 넓은 대지를 소유한 큰 부자였다. 전쟁이 나자 임씨는 땅문서와 값 나가는 것들만 챙겨서 일본으로 피난을 가지만 피난 중에 그만 땅문서를 잃어버리고 만다. 전쟁이 끝난 후에 임씨의 땅은 이미 다른 사람들의 논밭이 되어 있었고, 임씨는 땅을 되찾으려 했지만 문서가 없으니 생떼 쓰는 것과 다를 바 없었다. 이러다가 임씨는 길바닥에 나앉게 생겼다. 이 때, 임씨에게 좋은 생각이 떠올랐으니 바로 자신이 습관처럼 땅 깊숙.. 2010. 7. 7.
C- ACM - 양말 짝 맞추기 양말 짝을 맞추는 문제입니다. 저는 젓가락 행진곡 처럼 양 끝에서 가운데로 한짝씩 맞춰나가는 문제라고 이해하고 풀었어요~/  양말 장사를 하는 지훈이는 오랜만에 창고 정리를 하기로 했다. 창고에는 양말짝이 맞지 않은 채 가득 섞여 있었다. 이제 지훈이를 도와 어지럽게 섞여있는 양말의 짝을 맞추어 보자. - 양말의 종류는 알파벳으로 구분된다. - 양말의 오른짝은 소문자, 왼짝은 대문자이다. 즉, Jj가 J 양말의 한 쌍이며, aB는 a양말의 오른짝과 B양말의 왼짝이므로 짝이 맞지 않는다. 입력의 첫 번째 줄은 테스트 케이스의 개수 T ( 0 NO Bab ->NO #include #include int CASE() { int tail=30; char sox[30]; get.. 2010. 7. 2.
C- ACM - 다운로드 ㅋㅋㅋ 이런 문제 좋음~ 정희는 한 음악 포털 사이트에서 일정 금액을 충전하여 mp3파일을 다운로드 받아서 사용해 왔다. 지금 이 사이트에서 k곡을 다운받으면 한 곡을 무료로 다운받을 수 있는 이벤트를 진행 중이고, 현재 정희가 다운받을 수 있는 mp3파일의 개수는 n개이다. 이벤트 기간 중 정희가 다운받을 수 있는 총 mp3파일의 개수는 몇 개인가? 첫 줄에는 테스트 케이스의 개수 T ( 0 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; } 2010. 7. 2.