아즈키의 블로그 Ver 2005

역시나 찝찝했던 오늘일..


주먹질..

술 기운 반 진심 반 -_-

가볍게 때린다고 쳤는데..

생각보다는 좀 아프게 때린거 같구나 -_-

피.. 진짜 나온거냐?

괜찮을려나? 괜찮지? 그러리라 믿는다 -_-;;

어째꺼나 미안해

안녕하세요
마비노기 운영팀입니다.

8/19(금) 오전 패치로 세번째 제네레이션 2시즌 시작됩니다.
금일 패치로 인한 변경점은 다음과 같습니다.

===================================

이번 패치로 새롭된 투입된 내용입니다.

생산, 생활스킬의 랭크 제한이 풀립니다.
-방직, 제련, 약초학, 천옷만들기, 블랙스미스, 포션 조제, 핸디크래프트 스킬들을 새 레시피로 올릴 수 있으며 악기 연주, 낚시, 인챈트 등의 스킬도 수련을 계속하면 올릴 수 있습니다.
-메디테이션, 음악적 지식, 작곡, 응급치료, 휴식, 캠프파이어 스킬 등의 스킬북은 몇몇 캐릭터의 비밀 상점 및 특정 퀘스트의 진행, 혹은 판매를 통해 스킬북을 얻어 랭크업할 수 있습니다

생활 스킬의 마스터 타이틀이 추가됩니다.

메이킹 마스터리 스킬이 추가됩니다.
-메이킹 마스터리는 생산 활동에 보너스를 받고, 랭크업 할수록 스태미너와 솜씨의 보너스를 받는 스킬입니다.

앙상블 동물 캐릭터가 추가됩니다.
-자세한 설명은 업데이트 게시판을 참고해 주시기 바랍니다.

애완동물 대전이 추가됩니다.
-자세한 설명은 업데이트 게시판을 참고해 주시기 바랍니다.

힐링 원드가 추가됩니다.- 힐링 원드를 착용하고 힐링을 시전할 경우 생명력 회복량이 늘어납니다.
- 정령 힐링 원드 사용시 힐링, 파티 힐링 보너스가 생깁니다.

파티 힐링이 추가됩니다.
-마법 상점에서 힐링 원드를 구입한 후, 힐링 마법을 사용해 보면 파티 힐링 스킬을 배울 수 있습니다.
-파티 힐링은 한번에 파티원 전체를 치료 할 수 있습니다.

문학, 실용서 등이 추가됩니다.
- 문학 : 유저 여러분이 작성한 소설 중 우수작으로 선발된 9종을 투입합니다.
- 실용서 : 유저 여러분이 작성한 실용서 중 우수작으로 선발된 6종을 투입합니다.

마법음악이 추가됩니다.
-작곡, 음악적 지식스킬이 고랭크일때 작곡을 하면 랜덤하게 악보에 마법음악 효과가 나타납니다.
-마법음악을 연주하면 일정확율로 회복, 조준확율 향상, 마법 캐스팅 속도 향상, 버서커 모드 등의 효과가 생깁니다.

새로운 핸디크래프트 아이템을 만들 수 있습니다.
- 아이템을 획득할 확율을 높여주는 낚싯대와 미끼통, 각종 연극 소품, 효과가 강화된 최고급 수제 화살/볼트/붕대 등 새로운 핸디크래프트 아이템을 만들 수 있습니다.

신규 눈과 입이 투입됩니다.
-프리미엄 카드로 캐릭터 생성, 환생시 신규눈 5종과 입 3종을 추가로 선택 할 수 있습니다.

신규 의상이 투입됩니다
-플레타와 엘레노아의 상점에서 새로운 의상을 구입할 수 있습니다.

플레타와 관련된 미니스토리가 투입됩니다,
-이 미니스토리를 통해 새로 투입되는 스킬북 중 일부를 입수할 수 있습니다.

낚시 성공률을 높이는 낚싯대, 미끼통이 추가 됩니다.
-낚시 스킬이 5랭크가 되면, 아이템들을 낚을 확률을 높일 수 있는 '낚싯대' 와 '미끼통'을 사용할 수 있게 됩니다.
-이 두 아이템은 핸디크래프트 스킬로 만들 수 있습니다.

채집할 수 있는 약초가 추가됩니다.
- 만드레이크, 해독초, 독초가 추가되며 이 약초들은 던전에서 획득할 수 있습니다.
- 상위 마족 던전일수록 이 약초들을 좀 더 높은 확율로 볼 수 있습니다.

독/해독이 적용됩니다.
-약초학 스킬이 높으면 던전의 약초에서 독초와 해독초를 구할 수 있습니다.
-포션 조제 스킬이 높으면 해독 포션과 독 포션을 만들 수 있습니다.
-독 션을 이용하여 무기 아이템에 독을 바를 수 있습니다.
-해독 포션을 이용하여 독에 걸렸을 때 독을 해제 할 수 있습니다.

에린 시계가 투입됩니다.
- 단축키(영어 'O'키)로 켜고 끌 수 있으며, 옵션창에서 좀 더 세부적인 설정을 할 수 있습니다.

G2를 이상한 고양이에게 점프한 경우 얻을 수 없었던 팔라딘 스킬을, 이상한 고양이에게서 배울 수 있는 게임플레이 루트가 추가됩니다.


기존에 적용된 컨텐츠 중 패치로 인하여 변경된 내용입니다.

환생 조건이 기존의 21일 이후에서 20일 이후로 변경됩니다.
-예를 들어, 현재 월요일에 환생했다면 3주후 화요일이 되어야 환생이 가능하게 되었으나, 이 부분이 수정되어 현재 월요일에 환생했다면 3주후 월요일에 환생이 가능하게 됩니다.

던전 보상이 추가됩니다.
-알비하급/중급던전, 바리/바리하급던전, 페카 던전에 신규 인챈트 스크롤 보상이 추가됩니다.
(기존의 보상이 변경되는 것이 아니라 얻을 수 있는 인챈트 스크롤이 1개 이상 늘어납니다.)

나오의 얼굴이 변경되었습니다.
- 게임중에 나타나는 폴리건 캐릭터의 얼굴이 변경되었으며, 대화중의 일러스트에는 변화가 없습니다

면 만들기 요리를 할 수 있습니다.
-이멘 마하의 고든에게서 면 만들기에 관한 스킬북을 구입해 요리 스킬을 B로 랭크업하면, 면 만들기를 할 수 있습니다.
-셰나가 새로운 재료를 판매합니다.

포션 조제법이 변경되어 좀 더 적은 비용으로 포션을 생산할 수 있습니다.

데들리 / 포션중독이 상태이상으로 바뀝니다.
-캐릭터 머리위에 상태이상 아이콘이 뜨고 캐릭터 상태창에도 아이콘이 생깁니다.

투명한 눈빛의 캐릭터가 힐링 시전시 표정이 눈감은 모습으로 변경 됩니다.

상대방이 NPC와 대화중일 때 거래를 할 수 없도록 수정됩니다.
-정령무기와 대화중인 상대에게도 거래를 할 수 없습니다.

필드의 밤이 기존보다 약간 밝아지도록 변경됩니다.

최고급 실크방직 장갑을 착용하고 방직을 했을 때 최고급 실크를 뽑을 확률이 상향조정됩니다.

팔라딘으로 변신 했을 때 팔라딘의 스킬 단축키가 지정되어있지 않으면, 변신 전 캐릭터의 스킬 단축키로 세팅되도록 변경됩니다.


이번 패치로 인하여 수정된 내용입니다.

캐릭터 정보 창에서 환생날짜가 비정상적으로 출력되는 경우가 있던 문제가 수정됩니다.

행동불능 상태에서 나오의 부활을 선택한 후, 나오의 부활 회수가 소모된 상태에서 나오가 오기 전에 동물캐릭터에게 부활을 받을 수 있던 문제가 수정됩니다.

비앙카 드로워즈 레이어드 스커트의 목 색깔이 인벤토리 이미지와 다른 문제가 수정됩니다.

병을 착용하고 공격할 때 스태미나가 소모되지 않던 문제가 수정됩니다.

자동전투모드에서 예약된 마법 스킬을 모두 사용하지 않았는데도 비정상적으로 사라지던 문제가 수정됩니다.

결혼 동행 보너스가 적용되지 않던 문제가 수정됩니다.

결혼 반지의 내구도가 소모되는 문제가 수정됩니다.

캠프 안과 캠프파이어 주위에서 스태미나 회복 속도가 증가하지 않는 문제가 수정됩니다.

부상율 100~100에서 몬스터가 부상을 입지 않는 문제가 수정됩니다.

윈드밀 5랭크이상에서 윈드밀 범위가 늘어나지 않는 문제가 수정됩니다.

윈드밀, 약초학, 컴뱃 마스터리 스킬의 스킬 수련 조건 경험치가 잘못 표시되는 문제가 수정됩니다
- 실제 수련 및 랭크업에는 영향이 없으며, 스킬 정보창에 잘못 나오던 문제만 수정됩니다.

인챈트 위탁 캐릭터의 마나가 부족할 때 위탁을 하면 인벤토리의 아이템을 집을 수 없는 문제가 수정됩니다.
-인챈트를 부탁받은 캐릭터의 마나가 부족하면 인챈트 위탁이 취소됩니다.

인챈트 위탁시 Alt키를 누른상태로 인챈트 버튼을 클릭하면 인챈트 위탁 폼이 라지고 인챈트 스킬 세부 설명이 출력되는 문제가 수정됩니다.

가완성 단계의 아이템이 마무리 공정 중에 바닥에 떨어질 경우, 아이템은 가완성인 태인데 스킬 수련치만 증가하던 문제가 수정됩니다.

정령과의 대화에서 조사가 어색하게 표현되었던 문제가 수정됩니다.

완료되지 않은 파티퀘스트가 파티탈퇴 후에도 파티리더가 아닌 파티원에게 남는 문제가 수정됩니다.

===================================


게임 이용에 참고하여 주시기 바랍니다.
감사합니다.

별들에게 물어봐~
NEW 코코 사랑점


처녀자리
이제는 매사에 안정감을 갖고 현실적으로 다가가는 것이 좋다.
때로는 성과가 없는 일도 하게 되는 것이 인생이다.
다소 힘든 일이 있더라도 인내심을 가지자.
*행운의 장소 : 헬스클럽
*Advice : 너무 계산적인 행동은 상대방을 숨막히게 한다.

사수자리
*행운의 장소 : 중식집
*Advice : 가장 가까운 곳에 있는 사람이 당신의 천생연분이다.

물고기자리
*행운의 장소 : 한식집
*Advice : 감성적인 판단은 현실성이 부족해보이니 이 점을 유념하자.

쌍둥이자리
*행운의 장소 : 찜질방
*Advice : 당신의 지난친 요구는 상대방을 지치게 하는 나쁜 습관이다.

천칭자리
*행운의 장소 : 고깃집
*Advice : 진정한 아름다움은 마음에 있다는 것을 깨닫자.

염소자리
*행운의 장소 : 에스테틱
*Advice : 평소 타인을 존중하는 태도를 가지는 것이 중요하다.

양자리
*행운의 장소 : 보드게임방
*Advice : 자신의 행동이 남에게 해가 되지 않는지 생각하고 행동하자.

게자리
*행운의 장소 : 카페
*Advice : 사랑은 상대방의 인격을 존중하는 것! 너무 구속하지 말자.

전갈자리
*행운의 장소 : BAR
*Advice : 웃는 것이 보약~ 너무 심각한 표정은 상대방에게 부담만 된다.

물병자리
*행운의 장소 : PC방
*Advice : 톡톡 튀는 사고방식의 밑바탕에는 기본 매너가 자리함을 명심하자.

황소자리
*행운의 장소 : 일식집
*Advice : 사랑은 움직이는 것! 소유욕이나 집착은 금물이다.

사자자리
*행운의 장소 : 노래방
*Advice : 자신의 의견에 상대가 꼭 공감을 표시하는 것은 아니므로 주의하자.



쓰느라 힘들었다 =ㅁ=
은근히 잘맞던데ㅋ
매우 신뢰중이심

Character  Recognition

 

Google : 문자인식    Google : Character Recognition

Online Character Recognition (Pen based handwriting) : KAIST AI & Pattern Recognition lab : Demo : HMM based on-line handwriting recognition : 온라인 필기 인식기란 손으로 쓴 글씨를 바로 인식하여 컴퓨터에 입력 하는 시스템이다. 키보드 입력을 대체하여 필기 입력을 사용함으로써 컴퓨터에 익숙하지 않은 사람들도 부담 없이, 편리하게 이용할 수 있으며, 이동 중에도 간편하게 사용할 수 있어서 최근 들어 널리 보급되고 있는 PDA (Personal Digital Assistant), 전자수첩, 전자책 (e-book), 이동전화 등 휴대형 단말기의 입력수단으로 활용되고 있다 ....... 필기는 다양한 변형을 내재하고 있다. 동일한 사람이 동일한 내용을 필기하는 경우에도 그 모양과 크기에서 서로 차이가 나며, 사람에 따른 고유한 필기 습관에 따라 글씨의 모양, 크기, 그리고 필기 순서에 많은 차이가 존재한다. 특히 휴대용 단말기의 경우에는 불안정한 상태에서의 필기로 인하여 불균형성이 더욱 증대된다. 특히 한글의 경우에는 자모의 2차원적인 결합이라는 한글 고유의 특성에 따라 공간적인 변형 및 자모 간의 연결을 통한 변형이 심하다. 이에 따라 지금까지 개발되어온 많은 한글 필기 인식기는 자모의 모양을 제한하거나 자모간의 연결을 제한하는 등 사용자의 필기 형태에 제약을 가하여 불편함을 주고 있다. 한 예로서 현재 시장에 출하된 Palm Pilot의 경우에는 ‘graffiti’ 라는 특정 형태의 필기만을 허용하고 있다.

Offline Chararcter Recognition (handwritten) : KAIST AI & Pattern Recognition lab : Demo : Postprocessing of handwritten Hangul recognition using pair-wise grapheme discrimnation (자모 단위 유사쌍 구분을 이용한 필기체 한글인식의 후처리) : 한글은 자모의 조합으로 이루어져 있으며, 이런 특성상 조합가능한 글자의 수는 11,172 자이다. 하지만 하나의 인식기로 전부를 구분해내기는 매우 어렵다. 특히 필기체 문자의 경우 필기자 간의 변이가 상당히 커서, 인식은 더욱 어려워진다. 예를들어 필기자가 바뀌어서 생기는 변이 (intra-class variation) 는 동일한 필기자가 다른 글씨를 쓸 때 생기는 변이 (inter-class variation) 보다 큰 경우가 많다 .......... 그리고 한글이 자모의 조합으로 이루어진다는 특징 때문에 유사한 형태를 가지는 문자쌍이 많이 나타나게 된다 ..... 하나의 인식기로 필기자간의 변이 흡수나 유사한 형태의 문자쌍의 차이를 식별하기는 매우 어려우며, 인식기의 성능도 떨어지게 된다. 따라서, 인식기의 부족한 점을 보완하고 전체 시스템의 성능을 향상시킬 수 있는 후처리기의 도입이 필요하다 ......... 후처리를 수행하는 방법은 크게 문맥 정보를 이용하는 후처리방법과 글자의 특징을 이용하는 후처리 방법으로 나눌 수 있다. 문맥정보를 이용하는 경우 사전이나 언어 모델을 이용하여 기존 인식기의 오류를 정정할 수 있다. 이 방법은 단어나 문장 등을 대상으로 인식을 수행하는 인식기에 적용이 가능하다. 글자의 특징을 이용하는 후처리 방법은 자주 혼동되는 유사쌍을 구분할 수 있는 구분기를 사용함으로써 오류를 정정하게 된다. 이 방법은 단어와 문장뿐 아니라 낱자를 대상으로 인식을 수행하는 인식기에도 적용이 가능하다 .........

문서 분석 및 인식 : 고려대 Computer Vision & Pattern Recognition lab : Research : 문서 분석과 자연영상에서의 문자열 추출은 문서 및 영상을 이해하기 위한 가장 기초적이고 중요한 문제이다. 문자 인식은 이미 많은 상용화된 제품들이 많이 있는 반면에 복잡한 문서나 자연 영상(Scene Image)등을 분석하고 인식하는 일은 아직 쉽게 풀리지 않는 어려운 문제이다. 여러가지 환경에서 문자를 찾아내고 분석하여, 이미 많은 연구가 되어있는 문자 인식기(OCR) 모듈을 부착함으로써 여러가지 응용에 사용될수 있다

문서인식 (Optical Character Recognition : OCR) :  Perceptcom : 아르미 :  OCR 시스템이란 말 그대로 책, 잡지, 신문 등의 기존 인쇄 자료들을 사람이 직접 입력하지 않고 스캐너를 통해 이미지 형태로 읽어 들여 데이터의 내용을 분석, 그림영역과 글자영역으로 구분한 후 글자 영역의 문자들을 일반 문서편집기에서 수정, 편집이 가능한 텍스트(Text)의 형태로 변환하여 주는 자동입력 시스템을 말합니다.

PCAI : Optical Character Recognition

요새 공부하던것..
공부하는것..
재미있는것..?

정렬은 자료 구조와 알고리즘을 배우면서 가장 재미있는 부분임이 틀림없습니다. 문제 자체도 무척 실용적이면서도 정말 다양한, 기발함 그 자체인 알고리즘이 존재하고, 이들은 마치 스타 크래프트 유닛처럼 다양한 요소와 자신만의 장단점이 있습니다. 어떤 알고리즘을 쓰느냐에 따라 결과(소요 시간)도 천차만별이 됩니다.

이런 것들을 직접 코딩하면서 죽음의 삽질-_-도 하고 고민도 많이 했습니다. 자, 그럼 정렬 알고리즘들에 대한 간략한 설명과 함께 소스 나갑니다~

거품 정렬
바로 옆 원소끼리의 비교· 대입만 죽어라고 하는 무식한 노가다 알고리즘. 비교도 많고 대입도 많은 상당히 비효율적인 알고리즘이지요. 그나마 대입 여부를 플래그로 저장하면, 루프를 다 돌기 전에 정렬 작업을 끝낼 수는 있습니다. 이 알고리즘의 동작 모습을 그래픽 (x, y)->(x, 배열의 x째 원소)로 시연해 보면 대각선 부위에서 점들이 거품처럼 부글부글 움직이는 모습을 볼 수 있습니다.

선택 정렬
가장 큰 값부터 차례대로 리스트의 끝으로 옮겨서 정렬하는 방법으로, 실제 상황에서 가장 코딩하기 쉽고 직관적인 알고리즘입니다. 수행 시간이 데이터 상태의 영향을 잘 받지 않고, 데이터의 대입 횟수가 적은 게 특징입니다.

삽입 정렬
삽입 정렬과 거품 정렬을 비교해 보면, O(n^2)이라고 다 같은 O(n^2) 알고리즘은 아니라는 걸 알 수 있습니다. 평균적인 성능이 O(n^2) 알고리즘들 중에서 뛰어난 축에 들기 때문에, 이 정렬은 다른 정렬 알고리즘의 일부로도 자주 인용됩니다. 이 방법은 데이터의 상태, 데이터 한 개의 크기에 따라 성능 편차가 심한 편입니다.

쉘 정렬
삽입 정렬을 응용한 것 뿐인데 삽입 정렬과는 비교할 수 없을 정도로, O(n log n) 알고리즘에 버금가는 성능을 자랑하는 알고리즘입니다. 부가적인 메모리도 전혀 필요없죠. 비용 대 성능이 가장 뛰어난 알고리즘임이 틀림없습니다. 시간 복잡도도 O(n^2)나 O(n log n)처럼 정확하게 계산하기 힘든 신비로운(?) 알고리즘이기도 합니다.

퀵 정렬
가장 유명하고, 정렬 알고리즘의 표준이다시피 한 방법입니다. 이 알고리즘을 보면 정말 사기-_-라는 생각이 듭니다. 실제로 코딩을 해 보면, 퀵 정렬이 코드가 가장 긴데, 실행 시간은 퀵 정렬이 다른 알고리즘들보다 기막힐 정도로 짧습니다. 중간값이라는 뭔가 적당한(모호한-_-) 값을 선택해야 하고, 최악의 경우 시간 복잡도가 O(n^2)에 메모리 복잡도가 O(n)이 될 가능성까지 있는 알고리즘이 어쩜 이럴 수 있는지... 퀵 정렬만치 자료 상태에 민감한 알고리즘이 또 있을까 하는 생각이 듭니다.

하지만, 중간값을 기준으로 데이터를 반으로 갈라 놓고, 양측에 대해서 재귀적으로 정렬을 또 수행한다는 발상은 깔끔하고 멋집니다. 이런 걸 분할 정복법이라고 하지요. 이게 '퀵 정렬'이 아니었으면 '이분 검색'을 따라 '이분 정렬'이라는 이름이 붙었을 것입니다.

퀵 정렬은 본디 재귀적으로 정의되지만, 사용자 정의 스택을 구현해서 비재귀적으로 만들 수도 있습니다. 또한, 원소 개수가 한 자리 수로 떨어졌을 때는 또 재귀호출을 하는 게 아니라 삽입 정렬을 해서 능률을 극대화하기도 합니다.

병합 정렬
O(n log n)인 정렬 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법입니다. 퀵 정렬이 큰 리스트를 반씩 쪼갠다면, 이 방법은 이미 정렬이 된 리스트를 하나 둘씩 합쳐서 작업을 수행합니다. 이 알고리즘은 소요 시간이 데이터 상태에 별 영향을 받지 않고, 시간 복잡도가 O(n log n)인 알고리즘 중에 유일하게 안정성이 있다는 데 의미를 둘 수 있습니다. O(n^2) 알고리즘들은 모두 안정성이 있지만.. 쿨럭~

병합 정렬의 큰 결점은 데이터 전체 크기만한 메모리가 더 필요하다는 점입니다. 아주 현학적인 방법으로 한 배열 안에서 병합을 구현하는 방법도 있긴 하지만, 밀고 당기고 하는 과정으로 인해 속도가 크게 떨어지기 때문에, 메모리를 아끼려면 차라리 아래에 나오는 힙 정렬을 쓰는 게 더 낫습니다.

무조건 2의 배수씩 리스트를 합치는 게 병합 정렬의 기본 원리지만, 리스트에서 오름차순인 부분만 골라내서 지능적으로 병합을 하는 방법도 생각할 수 있습니다. 또한 퀵 정렬과 비슷한 원리로 재귀판을 만들 수도 있지요.

힙 정렬
이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘입니다. 이 알고리즘을 뜯어 보면 절로 감탄이 나옵니다. 처음에는 나무 아래에서 위(뿌리)로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꿉니다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려가지요.

시간 복잡도가 O(n log n)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 힙 정렬의 큰 장점이지만, 하지만 수행 속도가 동급 O(n log n) 알고리즘들에 비해서는 약간(아주...) 낮은 편입니다.

기수 정렬
기발함 그 자체입니다. 네 자리 수가 있으면, 백 자리, 십 자리, 일 자리 순으로 차례차례 정렬을 한다는 게 기본 전략입니다. 저는 이 알고리즘을 이해하고 나서도, "그렇게 해서 어떻게 실제로 정렬이 되는데?" 이걸 이해하는 데 한참 시간이 걸려야 했습니다.

이 정렬법은 비교 연산을 하지 않으며, 무엇보다도 시간 복잡도가 O(n)입니다. 물론 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하지요. 기수 정렬은 정렬 방법의 특수성 때문에 부동소숫점처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 매우 특이하고 멋진 알고리즘임은 틀림없습니다.

[CODE] #include <stdio.h> #include <time.h> #include <stdlib.h> #include <string.h> class CTimeRecorder { time_t& m_rWriteTo, m_dwBegin; public: CTimeRecorder(time_t& rTo): m_rWriteTo(rTo), m_dwBegin(clock()) { } ~CTimeRecorder() { m_rWriteTo=clock()-m_dwBegin; } }; template<typename T> void Swap(T& a, T& b) { T c; c=a; a=b; b=c; } template<typename T> class CSortCollection { T *m_pData; int m_nCount; time_t m_dwElapsed; public: //Construction CSortCollection(T *pArr, int nCnt): m_pData(pArr), m_nCount(nCnt) { } void Init(T *pArr, int nCnt) { m_pData=pArr, m_nCount=nCnt; } //Operation void BubbleSort(); void SelectionSort(); void InsertionSort(); void ShellSort(); void QuickSort(); void MergeSort(); void HeapSort(); void RadixSort(); //Elapsed time time_t GetElapsedTime() const { return m_dwElapsed; } int Verify(); }; template<typename T> int CSortCollection<T>::Verify() { int i; for(i=0;i<m_nCount-1;i++) if(m_pData[i]>m_pData[i+1]) return i; return -1; } template<typename T> void CSortCollection<T>::BubbleSort() { int i,j, flag=1; CTimeRecorder rec(m_dwElapsed); for(i=0;i<m_nCount && flag;i++) for(j=flag=0;j<m_nCount-i-1;j++) if(m_pData[j]>m_pData[j+1]) { flag=1; Swap(m_pData[j], m_pData[j+1]); } } template<typename T> void CSortCollection<T>::SelectionSort() { int i,j,k; CTimeRecorder rec(m_dwElapsed); for(i=0;i<m_nCount-1;i++) { k=i; for(j=i+1;j<m_nCount;j++) if(m_pData[k]>m_pData[j]) k=j; Swap(m_pData[k], m_pData[i]); } } template<typename T> void CSortCollection<T>::InsertionSort() { int i,j; T r; CTimeRecorder rec(m_dwElapsed); for(i=1;i<m_nCount;i++) { for(j=i-1, r=m_pData[i];j>=0 && m_pData[j]>r;j--) m_pData[j+1]=m_pData[j]; m_pData[j+1]=r; } } template<typename T> void CSortCollection<T>::ShellSort() { int i,j,k,l; T r; CTimeRecorder rec(m_dwElapsed); for(i=1;i<m_nCount;k=i, i=i*3+1); do { for(l=0;l<k;l++) for(i=l+k;i<m_nCount;i+=k) { for(j=i-k, r=m_pData[i];j>=l && m_pData[j]>r;j-=k) m_pData[j+k]=m_pData[j]; m_pData[j+k]=r; } k=(k-1)/3; } while(k>=1); } template<typename T> void CSortCollection<T>::QuickSort() { CTimeRecorder rec(m_dwElapsed); //sorting boundary, pivot index, and traveling pointers for partition step int lo, hi, mid, loguy, higuy; //stack for saving sub-array to be processed int lostk[40], histk[40], stkptr=0; lo=0; hi=m_nCount-1; //initialize limits while(1) { mid=lo+( ((hi-lo)+1) /2); //find middle element Swap(m_pData[mid], m_pData[lo]); //swap it to beginning of array /* Would it be better to use insertion sort, when hi-lo is very small? for(loguy=lo+1; loguy<=hi; loguy++) { for(higuy=loguy-1, r=m_pData[loguy]; higuy>=lo && m_pData[higuy]>r; higuy--) m_pData[higuy+1]=m_pData[higuy]; m_pData[higuy+1]=r; } */ loguy=lo; higuy=hi+1; while(1) { do loguy++; while (loguy<=hi && m_pData[loguy]<=m_pData[lo]); do higuy--; while (higuy>lo && m_pData[higuy]>=m_pData[lo]); if(higuy<loguy) break; Swap(m_pData[loguy], m_pData[higuy]); } Swap(m_pData[lo], m_pData[higuy]); //put partition element in place if( higuy-1-lo >= hi-loguy ) { if(lo+1<higuy) { //save big recursion for later lostk[stkptr]=lo; histk[stkptr]=higuy-1; ++stkptr; } if(loguy<hi) { lo=loguy; continue; } //do small recursion } else { if(loguy<hi) { //save big recursion for later lostk[stkptr]=loguy; histk[stkptr]=hi; ++stkptr; } if(lo+1<higuy) { hi=higuy-1; continue; } //do small recursion } --stkptr; //pop subarray from stack if(stkptr>=0) { lo=lostk[stkptr]; hi=histk[stkptr]; } else break; //all subarrays done--sorting finished. } } template<typename T> void CSortCollection<T>::HeapSort() { CTimeRecorder rec(m_dwElapsed); int i,j; T *dt=m_pData-1, root; //dt is a 1-based index for m_pData //construct the heap. for(i=m_nCount/2;i>=1;i--) { root=dt[i]; for(j=2*i;j<=m_nCount;j<<=1) { if(j<m_nCount && dt[j]<dt[j+1]) j++; if(root>=dt[j]) break; dt[j/2]=dt[j]; } dt[j/2]=root; } //Perform sorting wow~ for(i=m_nCount;i>0;) { Swap(dt[1], dt[i]); i--; root=dt[1]; for(j=2;j<=i;j<<=1) { if(j<i && dt[j]<dt[j+1]) j++; if(root>=dt[j]) break; dt[j/2]=dt[j]; } dt[j/2]=root; } } template<typename T> void CSortCollection<T>::MergeSort() { int i,j,a,b,c,d; CTimeRecorder rec(m_dwElapsed); T *pTmp=new T[m_nCount], *orig=m_pData, *dest=pTmp; for(i=1;i<m_nCount;i<<=1) { for(j=0;j<m_nCount;j+=(i<<1)) { //for each fragment, d=j+(i<<1); if(d>m_nCount) d=m_nCount; if(j+i>=m_nCount) { //Copy the remaining elems for(a=j;a<m_nCount;a++) dest[a]=orig[a]; break; } for(a=c=j,b=j+i; c<d; c++) if((orig[a]<=orig[b] && a<j+i) || b==d) dest[c]=orig[a], a++; else dest[c]=orig[b], b++; } Swap(orig, dest); } if(orig!=m_pData) memcpy(m_pData, orig, sizeof(T)*m_nCount); delete []pTmp; } #define BITOF(i,b) ((unsigned char *)orig)[i*sizeof(T)+b] //#define BITOF(i,b) ((orig[i])>>(b*8))&0xff template<typename T> void CSortCollection<T>::RadixSort() { CTimeRecorder rec(m_dwElapsed); int b,i, count[256], index[256]; T *pTmp=new T[m_nCount], *orig=m_pData, *dest=pTmp; for(b=0;b<sizeof(T);b++) { memset(count, 0, sizeof(count)); for(i=0;i<m_nCount;i++) count[ BITOF(i,b) ]++; index[0]=0; for(i=1;i<256;i++) index[i]=index[i-1]+count[i-1]; for(i=0;i<m_nCount;i++) dest[index[BITOF(i,b)]++]=orig[i]; Swap(orig, dest); } if(orig!=m_pData) memcpy(m_pData, orig, sizeof(T)*m_nCount); delete []pTmp; } #undef BITOF #define N 1000000 int main(int argc, char* argv[]) { srand(time(0)); int *arr=new int[N], *ar2=new int[N], i,j; for(i=0;i<N;i++) arr[i]= rand()|(rand()<<16); CSortCollection<int> sor(ar2, N); for(i=3;i<8;i++) { memcpy(ar2, arr, sizeof(int)*N); for(j=0;j<10;j++) printf("%d ", ar2[j]); puts(""); switch(i) { case 0: sor.BubbleSort(); printf("BubbleSort: "); break; case 1: sor.SelectionSort(); printf("SelectionSort: "); break; case 2: sor.InsertionSort(); printf("InsertionSort: "); break; case 3: sor.HeapSort(); printf("HeapSort: "); break; case 4: sor.QuickSort(); printf("QuickSort: "); break; case 5: sor.MergeSort(); printf("MergeSort: "); break; case 6: sor.ShellSort(); printf("ShellSort: "); break; case 7: sor.RadixSort(); printf("RadixSort: "); break; } j=sor.Verify(); if(j!=-1) printf("Error: %d %d ", j, arr[j]); printf("%.3g sec ",sor.GetElapsedTime()/(double)CLOCKS_PER_SEC); for(j=0;j<10;j++) printf("%d ", ar2[j]); puts(" "); } delete []arr; delete []ar2; return 0; }[/CODE]

실행 결과 (1)
32비트 정수 100만 개를 정렬한 결과와, 그 소요 시간입니다. O(n^2)인 알고리즘들은 정렬이 끝날 때까지 도저히 기다릴 수 없어서 일부러 테스트를 하지 않았습니다.

1707157587 317341677 662390333 1176788126 378630338 159730414 512518995 1082726135 929839362 1624122230
HeapSort: 1.13 sec
187 748 1097 3231 5311 6829 7012 7180 8351 8470

1707157587 317341677 662390333 1176788126 378630338 159730414 512518995 1082726135 929839362 1624122230
QuickSort: 0.551 sec
187 748 1097 3231 5311 6829 7012 7180 8351 8470

1707157587 317341677 662390333 1176788126 378630338 159730414 512518995 1082726135 929839362 1624122230
MergeSort: 0.962 sec
187 748 1097 3231 5311 6829 7012 7180 8351 8470

1707157587 317341677 662390333 1176788126 378630338 159730414 512518995 1082726135 929839362 1624122230
ShellSort: 1.59 sec
187 748 1097 3231 5311 6829 7012 7180 8351 8470

1707157587 317341677 662390333 1176788126 378630338 159730414 512518995 1082726135 929839362 1624122230
RadixSort: 0.26 sec
187 748 1097 3231 5311 6829 7012 7180 8351 8470


실행 결과 (2)
32비트 정수 3만 개를 정렬한 결과와, 그 소요 시간입니다.

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
BubbleSort: 7.82 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
SelectionSort: 3.11 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
InsertionSort: 1.42 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
HeapSort: 0.01 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
QuickSort: 0.01 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
MergeSort: 0.02 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
ShellSort: 0.04 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

1763461794 1133465913 202967127 1135746381 1504003220 1905358894 1992839703 1334061861 1454975500 966069090
RadixSort: 0 sec
96019 155288 163134 217965 275100 337903 355310 399329 596835 618801

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. 한달에 한번쯤은 나 혼자 외출을 한다.
(특별한 할 일이 없는 외출에서 의외로 나의 자신감을 만날수도 있으니까.)

30. 마지막으로 가장 중요한 한가지!! 잠을 충분히 잔다.


- 몇가지는 평소에도 하는데 초공감 ㅋㅋㅋ -

관리자 글의 비밀번호를 알아내는 문제ㅋ

문제는 간단 명료합니다 과정은 조금 복잡하지만..

글이나 아무거나 올리셔도 됩니다.

남에게 피해만 안주면 됩니다. ^^

대부분 학습예제용? 혹은 엉성한? 게시판에 적용되는 문제입니다.


힌트를 드리자면 푸는 과정에서 살짝의 추측?이 필요해요.

하지만 생각해 본다면 보통 그 경우의 수가 5가지도 안되니까 확인해보면 알지요.

길게쓴다면 ******** 이겠고, 짧게는 **, ****, ***, ****** 등이 되겠죠.

뭐 이거야 센스니.. 이정도는 삽질도 아니죠 '-'

이외에 힌트는 따로 안드리겠습니다.

그러한 성격의 문제이기 때문입니다.

그러한 것을 풀자고 낸 문제이기 때문입니다


그리고 게시판의 제공자 '백찬호'님께 감사드려요. ^^


문제 : http://azki.org/cathole3/quest.php?q=9

랭크 : http://azki.org/cathole3/rank.php?t=q&q=9

코멘트 : http://azki.org/cathole3/rank.php?t=c&q=9

이 문제 대해 하실 말씀이 있으시면 밑에 답글 다세요. // 답이나 힌트는 올리지 마세요.

마비


시험친 다음 날
컴퓨터 소리 없이
아침에
혼자 눈을 뜨게 된거야

실감이 안나
마비노기 켜보니
길드원들은
우리 길드원들은

그대로
있는데 여기있는데
어떡해, 벌써 난 접었는데
이젠 지워야겠지
모두 지워야겠지
웃는 나의 캐릭을
행복한 에린 세계를

한 파일
마비 지울때마다
가슴이 아려와
나의 에린이 점점흐려져

에린 속
길마 불러도 보고
스샷 만져도 보고
너무 잔인한 일이야

마비 지우는 일


그대로
있는데 웃고있는데
에린 속
니가 웃고있는데
이땐 행복했나봐
이땐 몰랐었나봐
에린 좋았었는데
에린 좋았을텐데

한 장씩
스샷 지울 때 마다
가슴이 아려와
나의 에린이 점점 흐려져

에린 속
길마 불러도보고
스샷 만져도보고
너무 잔인한 일이야
마비 지우는 일

이젠 눈감고
난 지워
어차피 나는 망한 거잖아
이젠 눈감고
난 지워
마지막 스샷 한 장뿐

마지막
에린 속 세상 보여
너무 아름다워요

이제 다시는 볼수없음에
한번더
나오 불러도 보고
나오 만져도 보고
너무 잔인한 일이지

나는 마비 지웠어