머가필요해

이런 타이틀을 왜 이제야 알았을까~

나와 같은 라떼 아저씨/아줌마들에게 정말 가성비 좋은 게임이다 !!!

게임이 하나가 아닌 엄청 많은 게임이 포함되어 있는 합본이다 !!!

이런 이런.... "뽀글뽀글" .... "BUBBLE BOBBLE" 이다 !!!

엄청 잘 정리되어있다.

당연히 게임 조작법을 너무나 친절하게 알려주고 있다.

난이도를 포함해서 게임 자체에 대한 설정도 원하는대로 할 수 있다.

"Game Description" 메뉴를 통해 배경 스토리도 알 수 있다.

"Hints and Tips" 메뉴를 들어가면 ...

CHEATS 내역까지도 설명을 해준다.

게임 디자이너의 인터뷰 영상까지 있다 !!!!

실제 인터뷰 영상을 보여준다 !!!

아~ 추억이 방울 방울~

뉴질랜드 스토리 !!!

오락실에서 했던 그 게임 그대로다 !!!

눈물이 찔끔 나올 정도로.... 추억이 떠오른다 !!!

지금 시점에서 PS2 게임 자체의 그래픽을 보면 아쉬움이 가득인데,

이 게임들의 그래픽은 더더욱 아쉬울 수도 있지만, 추억 하나로 모든게 극복이 된다.

TAITO에서 만든 명작들이 포함된 게임인데, 어떤 것들이 있냐면 ...

1978 SPACE INVADERS 스페이스 인베이더
1979 SPACE INVADERS PART 2 스페이스 인베이더 파트2
1980 PHEONIX 피닉스
1981 COLONY 7 콜로니 7
1982 ELECTRIC YO-YO 일렉트릭 요요
1982 JUNGLE HUNT 정글 헌트
1982 ZOO KEEPER 주키퍼
1983 ELEVATOR ACTION 엘레베이터 액션
1984 GREAT SWORDSMAN 그레이트 소드맨
1985 RETURN OF THE INVADERS 리턴 오브 더 인베이더
1986 BUBBLE BOBBLE 버블 보블 (뽀글뽀글)
1986 GLADIATOR 글래디에이터 (황금성)
1986 TOKIO 토키오
1987 EXZISUS 이그지저스
1987 PLUMP POP 플럼 팝
1987 RAINBOW ISLANDS 레인보우 아일랜드
1987 RASTAN 라스턴
1987 SUPER QIX 슈퍼 퀵스
1987 OPERATION WOLF 오퍼레이션 울프
1988 OPERATION THUNDERBOLT 오퍼레이션 썬더볼트
1988 THE NEW ZEALAND STORY 뉴질랜드 스토리
1989 BATTLE SHARK 배틀 샤크
1989 CONTINENTAL CIRCUS 컨티넨털 서커스
1989 PLOTTING 플로팅
1989 VOLFIED 볼피드
1990 SPACE GUN 스페이스 건
1990 THE NINJA KIDS 닌자 키즈
1990 THUNDERFOX 썬더 폭스
1993 TUBE IT 튜브 잇

이 게임들을 한 번씩만 해본다고 해도.... 정말 가성비 타이틀이다 !!!

오락실 게임 특성상 타이밍 이슈가 있기에

에뮬레이터로 진행하려면 문제가 없을까!? 우려를 했지만 전혀 문제가 없었다.

하지만, 이건 정말.... 거실로 뛰어가 PS2 전원을 키고 고고씽~~~~!!!!!

등짝 스매싱을 하려다가 .... 같이 추억을 곱씹고 있는 우리집 대장님!!!! ^^

이번에 살펴볼 Sorting algorithm은 앞에서 공부한 것들과 궤를 달리한다.

지금까지 공부한 것은 비교(comparison) 기반의 정렬이었지만

이번에는 counting 방식으로 정렬을 하는 계수 정렬(Counting sort)이다.

① basic counting sort

  - 비교 행위 없이 입력값 하나씩 읽어가며 개수만 세는 것으로 정렬이 된다.

② extra memory

  - 개수를 세기 위한 C(count array)가 추가로 필요하다. (= in place 알고리즘이 아니다!)

③ No stable

  - 입력값의 순서가 유지되는 것을 "stable 하다"고 한다.

  - 위 그림에서 3개의 "3" 입력값에 대해서 살펴보면,

    . (빨간색) index 값으로 표현해보면 '3-3', '6-3', '8-3'이라고 할 수 있다. 각 '3'은 다른 '3'이다.

    . 이 때, 출력값(output array)에서 '5-3', '6-3', '7-3'이 있는데,

    . 입력값의 순서가 유지된 것이라고 할 수 있을까?

  - Counting sort는 stable 할 수 없는 algorithm 이다.

④ Stabled(Advanced) Counting Sort

  - Counting sort 를 Stable 하도록 만들 수 있다.

  - Encoding ..... 기존 count array를 기반으로 누적값을 저장하는 C' array를 만들어줘야 한다.

  - Decoding ..... 누적값을 갖고 있는 C' array와 입력값(A array)를 가지고 출력값(B array)를 만들어준다.

    . 입력값의 제일 끝에서 부터 역으로 하나씩 처리하는 방식이다.

    . 하나 더 해보면, 다음과 같다.

    . 그 다음 "3" 값을 주의 깊게 봐야 한다.

      왜냐하면, 처음에 했던 "3"과 이번에 해야하는 "3"은 다른 "3"이기 때문이다.

    . 뭔가 신기하게 보일 수도 있긴 하지만... 그래서 뭐?

    . 입력값(A array)의 3의 순서에 따라 출력값(B array)의 순서가 정해진다. → Stable 하다 !!!

⑤ Pseudo code

  - 왠지 복잡해보이지만, 복잡하지 않은 코드이다.

  - 변수 (메모리) 모습을 그려보면 다음과 같다.

  - 여기에서 k는 입력값의 종류(개수)를 의미한다.

  - 코드를 분석해보면 다음과 같다.

⑥ Running Time

  - 실행 시간은 선형이다.

  - 정리해보면 다음과 같다.

그 이름에 걸맞게 입력값을 하나씩 세기만 하면 되는 시간인 것이다 !!!

즉, 앞에서 살펴본 "Lower bounds for (comparison) sort" 제약에 해당하지 않는다 !!!

[ 공부 순서 ]

① Comparison sorts

② Lower bounds for (comparison) sorting

③ Decision-tree model

지금까지 공부한 Sorting 방식은 전부 비교(comparison)라는 행위를 이용하고 있다.

그런데, 이러한 Comparison sorting에 있어서 worst-case인 경우

최소한 "n log n" 번 비교를 해야한다는 것에 대한 증명 과정을 살펴보고자 한다.

① Comparison sorts

  - 정렬(Sorting)을 하기 위해서 크기 비교(comparison)만을 수행하는 알고리즘

  - 종류 : Insertion / Merge / Selection / Heap / Quick

② Lower bounds for (comparison) sorting

  - 모든 comparison sort는 worst case 상황에서 최소한  Ω(n log n) 번의 비교를 요구한다.

  → 이후 내용은 본 명제를 증명하는 과정

③ Decision-tree model

  - 모든 입력은 동일한 값이 없다고 가정

  - 비교(comparison)는 ＜, ＞, ≤, ≥ 4종류가 있지만, ai ≤ aj 하나로 모두 처리 가능

    ( ai ≤ aj 비교를 수행하게 되면 True or False 결과. 그러므로  ai ≤ aj 한 번만 수행하면 됨)

  - comparison sort는 decision-tree로 표현(설명) 가능

    . full binary tree

    . leaf는 입력 값들의 순열(permutation)

    . internal node는 어떤 값을 비교하는 지를 표현

  - 입력값 크기가 3인 insertion sort는 다음과 같은 decision-tree model로 표현

  - 예시를 하나 돌려보면 다음과 같다.

  - leaf 개수는 어떻게 계산할 수 있을까?

    . 입력값의 개수가 n 일 때, n!

    . 위 예시의 경우, n = 3 이기 때문에 3! = 6

  - Left / Right subtrees

    . 특정 node를 기준으로 왼쪽은 ai ≤ aj 값들만 존재, 오른쪽은 ai ＞ aj 값들만 존재

    . 밑의 node들도 모두 동일한 결과

  ★ the worst-case number of comparisons = the height of its decision-tree

    - h : height

    - n : number of element

    - n! : number of leaves

음.... 일단 내용은 파악했는데,

그래서 어쩌라고? ^^

다음에 살펴볼 counting 방식의 정렬(sorting)은 이와 다르다 !!!

연차를 내고 집에서 쉬다가 문득 떠오른 생각

"아~ 갑자기 게임하고 싶다 !!!"

하지만, 거실엔 여왕님이 두 눈 시퍼렇게 뜨고 지켜보고 있기에 PS2를 직접 켤 수는 없고,

조용히 내 방에서 에뮬레이터로 돌려 본다.

PS2 가지고 와서 그냥 모니터에다가 연결할까?! 

인트로가 나오는데,

어?! 애니메이션이 나오네!?

타이틀 화면만 봐도 뭔가 수상한 느낌이 팍! 팍!

버전이 5인데 .... 왠 미국 국기 그림이 ?

황야 ... 서부 시대인가 ??

그런데, 사무라이 ???

일단 처음부터 시작을 하자 !!!

"제미니 선라이즈"  ???

어?! 대화창이 .... 이거 분위기가 ...

내가 싫어하는 게임 스타일일 것 같은 불길한 느낌이 ...

어??????

이거 메카물인거야 ????????

3D 캐릭터 ...

로봇, 사무라이, 황야, 마법까지 ????

전투 방식은 실시간 타격이다.

말 타고 다니며 칼질 하다가 점프도 하고 ... 심지어 말도 공격할 줄 안다.

3D 방향을 맞춰야 해서 좀 귀찮기는 한데,

R 버튼으로 시점을 바로 맞춰줘서 그냥 저냥 재미있게 할만하다.

돈 벌어서 능력치도 올리고, 장비도 마련해야 한다.

잉?!

난 여유롭게 게임하고 싶은데, 시간도 측정하네 ?!

한글 게임이라 계속 하고 싶기는 한데...

뭔가 이것 저것 다 섞여 버린 근본 없는 게임인 것 같은데,

그냥 생각 없이 해보기에는 괜찮은 것 같다.

- 미국의 황야

- 사무라이

- 메카트로닉스

- 턴 방식 대화

- 실시간 전투

- 3D & 2D

- 노래

사쿠라대전 게임의 외전이라서 그런 것일 수도...

AI / ML 공부를 하면 무조건(?) 사용하게 되는 "주피터 노트북(Jupyter Notebook)"

pandas, numpy, scikit-learn 등 착실하게 공부를 해야하는 것은 맞지만

모든 것들을 외워서 사용하기에는 어려움이 많고, 또 일일이 타이핑을 하는 것이 효율적이지도 않다.

그래서 Jupyter Notebook을 사용하면서 도움을 주는 기능들에 대해서 하나씩 알아보자.

① 자동 완성(auto complete) : Tab

  - IDE를 사용하거나 리눅스 커맨드 창에서 bash 또는 zsh 등을 사용할 때, 가장 많이 사용하는 tab !!!

  - 그런데, Jupyter Notebook에서 아래와 같이 타이핑을 하다가 tab을 눌러도 .... 아무런 반응이 없다.

  - import를 먼저 실행해서 "pd"가 뭔지 알려줘야 자동완성 기능을 사용할 수 있게 된다.

② 툴팁 (Tool Tip) : Shift + Tab 

  - 함수의 파라미터(parameter)들이 뭐가 있는지 확인하고 싶다면? Shift-Tab을 눌러주면 된다 !!!

③ 툴팁 (Tool Tip) : ?

  - pop-up으로 뜨는 툴팁이 조금 불편하다면, "?"를 이용해도 된다.

  - 함수명 뒤에 "?"를 타이핑하고, 실행을 시키면 밑에 출력이 된다.

④ Display parameter : set_config

  - scikit-learn의 model을 사용하다보면 parameter들을 확인해보고 싶을 때가 있다.

  - model에서 명시적으로 입력한 parameter 값만 확인이 되는데,

  - 현재 default로 지정된 parameter 값을 포함해서 전체 내역을 확인하고 싶을 때가 있다

  - scikit-learn 환경설정을 통해서 해결할 수 있다.

  - 이제 어떤 parameter로 해당 모델이 실행되는지 눈으로 확인할 수 있다 !!!

⑤ 도움말 (Help) : help

  - 자고로 도움말은 help !!!

  - 예쁘게 출력되진 않지만, 많은 정보를 보여준다.

게임 관련해서는 거의 포스팅하지 않았었는데...

연휴가 길어지다보니 게임 관련해서도 포스팅하는 일이 벌어지고 있다 ^^

라떼를 찾는 나이를 많이 먹어버린 아저씨이다보니 오래된 게임들을 애정하고 있고

그 중 가장 애정하는 것은 SFC (슈퍼 패미콤) 이다.

하지만, 애정만으로는 그래픽의 아쉬움을 달랠 수가 없기에

최근에는 PS2 (플레이스테이션2) 게임을 아주 애정하고 있다 !!!

이런 history를 갖고 있기에

SFC 시절에 좋아했던 게임을 PS2로 만나면 더더욱 애정할 수 밖에 없다.

"로맨싱 사가 (Romacing SaGa)"를 SFC 시절에 즐길 때에도 그 음악이 뭔가 매력적이었는데,

PS2로 리메이크 되면서 뭔가 음악과 아주 친화적인 제목인

"로맨싱 사가 - 민스트럴 송 (Romacing SaGa - Minstrel Song)"라는 이름으로 출시 되었다.

게임 시작하자마자 음유시인 처럼 생긴 서부 총잡이(?)가 기타를 치면서 노래를 부르는 인트로 영상이 나온다.

"Minstrel" 이라는 단어 자체가 "음유시인"이라는 뜻이다 !!!

이 게임은 "사가 (SaGa)" 시리즈의 하나라고 한다.

그러면 '사가'는 어떤 의미일까?

한글 '사가'와 같은 의미이지 않을까 싶다 ^^

SFC (슈퍼 패미콤)에서 Romancing Sage는 1 / 2 / 3 가 나왔었고,

그 중 1992년도에 출시된 1에 해당하는 것이 2005년도에 PS2로 리메이크 되면서

"로맨싱 사가 - 민스트럴 송 (Romacing SaGa - Minstrel Song)"으로 나온 것인데,

일어판은 첫 화면에 "민스트럴 송 (Minstrel Song)"이라는 부제목이 같이 나오는데,

영문판(북미판)에서는 희한하게 사라졌다.

8명의 주인공 중에 한 명을 선택해서 진행하는 방식인데,

어떤 주인공을 선택하느냐에 따라 다른 스토리로 진행이 되는데

선형적이지 않고 비선형적으로 진행이 되는 오픈월드 방식이라서 게임 진행이 쉽지 않다.

게임 자체가 그다지 친절하지 않다.

여러 나라의 많은 도시가 보인다. 왠지 두렵다 ^^

내가 선택한 '클라우디아'는 황녀이지만, 신변 보호를 위해 저 할머니가 숲에서 기르고 있다.

전투 방식은 턴제 인데... 전투 횟수에 따른 제약이 존재한다.

레벨업을 위해 무식하게 전투를 많이 하게 되면 ... 시나리오 진행을 할 때 뭔가 스킵되거나 하기도 하고 ...

그렇다고 전투를 피해 다니면 레벨업을 못해 지나가던 보스에게 한 대 얻어맞고 죽어버리고 ...

게임 진행 시간 제약이 있는 이벤트도 있고 ...

공략집 없이 진행하기에는 쉽지 않은 게임이다.

다들 VGL 공략집과 함께 하라는 조언을 해주는 게임이다.

하지만, 뭐 그냥 혼자서 묵묵히 진행할 수는 있을 것 같다.

뭐 꼭 Good Ending을 봐야 하나 ?! ㅋㅋㅋ

PS2 게임기로 하다가 눈치가 보여서 (아무리 명절이라지만 ... 거실 TV에서 게임을 하고 있자니 ...)

에뮬레이터로 실행했는데, 잘 된다.

뭔가 힐링이 되는 게임을 하고 싶은 상황이기에, 살짝 맛만 보고 껐다 ^^

전투 제한이나 시간 제한 있는 게임은 심장이 너무 두근거려서....

늙은이 건강에 해로워....

어느덧 6주차까지 왔다. 혼공 완주 !!!

스스로에게 칭찬해줘야지 !!! 쓰담~ 쓰담~

▶ 내용 요약

06-1 객체지향 API로 그래프 꾸미기

- pyplot 방식과 객체지향 API 방식

- 그래프에 한글 출력하기

  . 한글 폰트가 필요하기 때문에, 나눔폰트를 설치해야 한다.

  . 예제에서는 구글 코랩에 대해서만 설명되어 있지만, 일반적인 Ubuntu 환경에서도 적용된다.

  . 사용할 수 있는 폰트 목록을 확인해볼 수도 있다.

  . 사용할 폰트를 지정할 수도 있고, 크기도 정할 수 있다.

  . 잘 되는지 확인해보자.

- 출판사별 발행 도서 개수 산점도 그리기

  . 교재와는 다르게, 내가 이용하는 도서관의 데이터로 진행해봤다.

  . 모든 데이터가 아닌 Top 30 출판사를 뽑아서 사용한다.

  . 산점도를 그리면 된다!

  . Marker 크기를 확인하거나 설정을 할 수도 있다.

  . 그냥 점이 아니라 크기에 따라 의미를 부여해보자. (대출건수)

- 맷플롯립의 다양한 기능으로 그래프 개선하기

06-2 맷플롯립의 고급 기능 배우기

- 실습준비하기

  . 한글 폰트 설치 및 도서관 CSV 파일 읽어오기 (앞에서 진행했던 내용 활용)

- 하나의 피겨에 여러 개의 선 그래프 그리기

  . 대출건수 크기가 유사한 출판사 2개를 선택해서 그려보자

  . 레전드를 표현하거나 모든 출판사 정보를 그려보거나 해보자.

  . 피봇 테이블을 이용해서 데이터를 만들어서 stackplot으로 그려보자.

- 하나의 피겨에 여러 개의 막대 그래프 그리기

  . 나란히 나오도록 할 수도 있다.

  . 2개의 bar 그래프를 합쳐서 그리는 2가지 방법이 있다.

  . 데이터 값 누적한 것을 그려보기 위해서 데이터를 먼저 확인해보자

  . cumsum()을 이용해서 누적 데이터를 만들 수 있다.

- 원 그래프 그리기

  . 10개 출판사를 뽑아서 pie를 그리면 된다.

  . startangle 및 여러 옵션들을 줘서 멋진 원 그래프를 만들 수 있다.

- 여러 종류의 그래프가 있는 서브플롯 그리기

  . 앞에서 살펴본 것들의 종합판이다!

  . 한 방에 모두 그려진다!!!

- 판다스로 여러 개의 그래프 그리기

  . DataFrame에서 바로 그래프를 그릴 수도 있다.

▶ 기본 미션

p.344의 손코(맷플롯립의 컬러맵으로 산점도 그리기)를 코랩에서 그래프 출력하고 화면 캡쳐하기

→ 코랩이 아닌 로컬 환경에서 실행해봤다 ^^

▶ 선택 미션

p.356~359의 스택 영역 그래프를 그리는 과정을 정리하기

① 기본 데이터 준비

  - 작업 준비 과정이다.

② 그래프로 표현할 데이터 만들기

  - Top30 출판사 기준으로 "출판사 / 발행년도 / 대출건수"를 추출하고,

  - "출판사 / 발행년도" 기준으로 그룹핑을 하면서, 대출건수는 sum()을 했다.

  - 전체적으로 reset_index()까지 해줬다.

③ pivot_table()

  - 발행년도를 X축으로 하고, 출판사를 Y축으로 하고, 대출건수를 데이터로 하는 테이블을 만든다.

④ get_level_values()

  - pivot_table()을 사용했다보니, column이 다단으로 구성되어 있다.

  - 이런 경우 원하는 레벨의 값만 추출하기 위해 get_level_values()를 사용했다.

⑤ stackplot()

  - 이제 그래프를 그리면 된다.

우와~~~ 다했다!!!!

기사 작위를 갖고 계시는 '토니 호어'로 불리우시는 분이 1961년에 발표한 정말 정말 유명한 알고리즘이다.

이름 그대로 제일 빠른 정렬 알고리즘이 뭐야? 라고 하면 누구나 외치는 "퀵 정렬" !!!

(참고로 '토니 호어'님은 아직도 시니어 연구원으로 계신다고 한다. 무려 90세의 나이임에도 .... @.@)

[ 공부 목차 ]

① Partition

② Balanced partitioning vs Unbalanced partitioning

③ Randomized-Partition

④ Quick-Sort

① Partition (vanilla Partition)

  - 'Quick Sort'에 있어서 가장 중요한 개념이 바로 partition 이다.

  - 기준값(Pivot element) 보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하여 나누는 것을 의미한다.

  - 가장 기본이 되는 partition 방법은 제일 오른쪽 값을 pivot으로 해서 하나씩 비교하는 것이다.

  - 제일 오른쪽 값을 기준으로 제일 왼쪽부터 하나씩 비교해서 작은값 그룹과 큰값 그룹을 만들어 간다.

  - 그런데, "1"값을 만났을 때 작은값 그룹에 묶을 때가 문제가 된다.

  - 이럴 때에는 큰값의 제일 왼쪽에 위치한 것과 swap을 하면 된다. (i값 위치의 변화도 살펴봐야 한다)

  - 이렇게 하다보면 끝까지 진행을 하게 될텐데, 마지막에 위치한 pivot 값은 어떻게 해야할까?

  - 역시 마찬가지로 큰값의 제일 왼쪽값과 swap 하면 된다.

  - 이 과정을 pseudo code로 살펴보면 다음과 같다.

  - Running Time을 계산해보면 다음과 같다.

② Balanced partitioning vs Unbalanced partitioning

  - partitioning을 할 때에 좌우 균형이 잘 맞춰져서 나뉘어지면 좋겠지만,

  - 그렇지 않고 한 쪽에 치우칠 수도 있다.

  - 균형이 맞지 않는 극단적인 경우를 보면 다음과 같다.

  - Running Time은 다음과 같이 구할 수 있다.

  - 즉, 최악의 상황에서는 n제곱, 보통은 n로그n 이라고 정리하면 되겠다.

  - 그러면, 최악의 상황을 막을 방법은 없을까!?

③ Randomized-Partition

  - 최악의 상황이 발생하는 것은 pivot 값을 무조건 제일 끝값을 택하기 때문에 발생을 한다.

  - 그러면, pivot 값을 random하게 선택을 하게 되면 최악의 상황이 벌어질 가능성을 낮출 수 있다.

  - random하게 값을 뽑아서, 그것을 제일 오른쪽(끝) 값과 swap을 한 다음에 partition을 하면 되는 것이다.

  - 그런데, radom 호출 하는 것 자체가 over-head가 될 수도 있다. radom 자체가 비용이 크기 때문이다.

  - 그래서, (첫값 + 가운데값 + 끝값) 3개 중에 중간값을 선택하는 방법도 있긴 하다.

④ Quick-Sort

  - 지금까지 우리는 Partition을 공부했다. 이를 이용해서 Sort는 어떻게 할 수 있을까!?

  - 일단 partition을 한 다음, 왼쪽/오른쪽 각각 QuickSort를 하면 된다.

  - 그렇다 !!! Divide-and-Conquer 알고리즘이다.

  - Quick-Sort의 Running Time은 어떻게 될까?

  - 메모리 사용은?! 위치를 가르칠 변수 정도면 충분하다. 즉, 입력 데이터의 크기에 영향을 받지 않는다.

지금까지 여러 Sorting algorithm을 알아봤는데, 성능 비교 등을 해보면 좋을텐데...^^

다음 기회로~~~