1,2,3,4,5를 저장한 STL Set은 메모리에 다음과 같은 형태로 저장되어있다. 이처럼 STL Set은 BST(Binary Search Tree)를 이용해 정보를 저장한다. 여기서 중요한 점은 다음과 같다. 1) find, insert, delete의 경우 모두 O(log n)의 time complexity를 갖는다. (이때 insert와 delete의 경우 트리 자체를 새로 생성해야 하는 상황이 발생할 수도 있다.) 2) Set은 데이터를 정렬된 형태로 출력할 수 있는데, 이는 트리 구조를 가지는 Set의 특성 상 데이터 출력시 트리 순회를 통해서 순서를 정렬해서 출력할 수 있기 때문이다.
다음과 같은 클래스가 있다고 가정해보자. #include #include class Coor { public: int x; int y; public: Coor(int x, int y) : x(x), y(y) { std::cout
1, 2, 3, 4 를 저장한 v라는 이름의 STL 벡터가 있다고 가정했을 때, 이 벡터는 메모리 상에서 다음과 같은 구조를 가진다. 여기서 중요한 점은 다음과 같다. 1) 벡터는 정보를 메모리 상에서 연결된 형태로 일렬로 저장한다. 때문에 벡터는 Random Access의 Time Complexity가 O(1)이다. 또 이 일렬로 순서대로 저장한다는 점 때문에, 벡터에서 n번째 위치에 요소를 추가/제거하려면 O(n)이 소요된다. 2) 벡터가 차지하는 공간(capacity)과 그 속에 저장되어있는 요소의 갯수(size)는 다르다. 벡터의 요소의 갯수(size)가 벡터가 보유한 공간(capacity)을 넘어서면 메모리의 다른 공간으로 요소 전체를 복사시키고, 원본은 삭제한다. 이 과정을 reallocati..
1. Adjacency Matrix 그래프의 각 노드(혹은 vertex)들을 x축, y축에 나열하고 x,y의 교점에 두 노드의 연결 여부를 표시한다. 0 1 2 3 4 0 0 1 0 0 1 1 1 0 1 1 1 2 0 1 0 1 0 3 0 1 1 0 1 4 1 1 0 1 0 장점 a, b의 연결 여부를 확인할 때 O(1) 밖에 걸리지 않는다. a, b의 연결 여부를 변경할 때 O(1) 밖에 걸리지 않는다. 단점 O(V^2)의 공간을 차지한다 (V = Vertex) 노드를 추가 혹은 제거할 때 O(V^2)만큼 소요된다. 2. Adjacency List 그래프의 각 노드별로 그 노드와 연결되어있는 다른 노드들의 정보가 담긴 리스트를 만들고, 이 리스트들을 하나로 모은다. *노드 목록 구현은 리스트/다이나믹 ..
문제 문자열이 주어졌을 때 같은 알파벳이 두 번 이상 사용되지 않는 가장 긴 Substring을 구하시오. 더보기 Substring이란? 우선 Substring이란, 해당 String을 슬라이싱해서 나올 수 있는 String을 뜻한다. 즉, "Apple"의 Substring은 A, p, p, l, e, Ap, pp, pl, le, App, ppl, ple, Appl, pple, Apple 이렇게 총 1+2+3+4+5 = 15개이다. 즉 길이가 N인 String에서 나올 수 있는 Substring의 갯수는 N * (N+1) /2 개이다. Table이란? Key, Value로 쌍을 이뤄 데이터를 저장하는 자료구조. Key값을 통한 Random Access에 O(1)의 시간이 소요된다. 두 가지 풀이법 접근1..
> "게임의 첫 10분은 그 뒤 이어지는 10시간만큼이나 중요하다" 라는 말이 있습니다. 네, 그냥 제가 만들어 낸 말입니다. 하지만 이는 꽤 사실에 가까운 말이기도 합니다. 사람의 첫 인상이 중요하듯이, 게임의 첫 인상은 게임 내적으로 굉장히 중요한 역할을 맡습니다. 더구나 그 게임이 앵그리버드 같은 캐주얼한 게임이 아니라, 플레이어가 게임 속 세계에 몰입해야 하는 종류의 게임이면 더더욱 그렇습니다. 오늘 제가 소개해드릴 게임도 그런 종류의 게임입니다. 그리고 이 게임은, 비디오 게임의 역사에서도 손꼽힐 정도의 그야말로 "게임 도입부의 교과서" 같은 완벽한 도입부를 보여줍니다. 제가 소개할 게임은 바로 바이오쇼크 입니다. 더보기 사실 바이오쇼크는 도입부 뿐만 아니라 게임 전체적으로 뛰어난 퀄리티를 보여..
로그라이크의 아버지, 로그(Rogue) 이 게임의 제목은 , 한국어로는 정도가 되겠습니다. 로그는 그 제목처럼 플레이어가 도적이 되어 던전 곳곳을 탐험하는 게임입니다. 플레이어의 목표는 던전 최하층에 있는 "옌도의 아뮬렛"이라는 아이템을 지상으로 가져오는 것이며, 이 과정에서 플레이어는 수많은 몬스터들과 마주하게 됩니다. 오늘날의 관점에서 보면 로그는 그다지 특별할 게 없는 게임일지도 모릅니다. 그러나 로그는 둠, 테트리스와 어깨를 나란히 할 만큼 게임사에 큰 족적을 남긴 게임이고, RPG 장르에도 막대한 영향을 끼친 게임입니다. 로그는 현대적인 시점에서 보았을 때 부족한 부분이 많은 게임입니다. 로그의 그래픽은 아스키 코드(ASCII)로 이루어져 있고, UI는 오직 숫자와 문자들로만 제작되어 있습니다...
Geophyte (지오파이트) 장르: 정통 로그라이크 개발 기간: 2020. 04. 08. ~ 2021.11.05. (업데이트 잠정 중단) 알파 릴리즈: 2021. 10. 04. 개발 엔진: 없음. tcod 라이브러리 기반 자체제작 프레임워크 사용중 개발 언어: Python 3 (관련 글) 사용 라이브러리: tcod (libtcod와 SDL의 python wrapper), numpy, PyAudio 개발 목적: 취미 무료 다운로드: https://gamesm1th.itch.io/geophyte Geophyte by gamesm1th An Open-source Traditional Roguelike gamesm1th.itch.io 소스 코드: https://github.com/hagukin/Geophyte..
Last Hero와 Final Hero는 제가 초등학교 2~4학년 정도였을 때 RPG MAKER XP로 제작한 쯔꾸르 게임입니다. 두 작품 모두 끝까지 완성하지는 못했지만, 2시간 이상의 플레이 타임 정도 분량은 제작했던 걸로 기억합니다. Last Hero는 제가 초등학교 때 만든 공책 게임(공책에 그림 등을 그려 진행하는 게임)을 PC로 옮겨보려는 시도에서 탄생한 게임이고, 제가 생애 처음으로 만든 PC게임입니다. Final Hero는 Last Hero에 기능과 스토리를 추가해서 만든 게임으로 세계에 흩어진 몇 개의 스톤을 모아 악마를 봉인하는 게 주된 내용입니다. (지금 생각해보면 어벤져스의 플롯과 상당히 유사하네요) Final Hero에는 간단한 이펙트와 AI, 그리고 전투 시스템이 마련되어 있습니..
2009년은 제가 초등학교 2학년일 때네요. 당시에는 공책게임이라는 게 인터넷에서 유행했었는데, 공책에다 그림을 그리고 글을 써서 PC 게임처럼 만들어 노는 형태의 게임이었습니다. 저도 그때 공책게임 네이버 카페에 가입해서 다른 사람들이 만든 공책게임들을 구경도 하고, 또 제가 직접 만들어서 친구들과 쉬는 시간마다 같이 게임을 하곤 했습니다. (지금 생각하면 제가 GM의 역할을 한 셈이네요) 제가 만든 첫번째 공책 게임이 "Legend RPG -the Last Hero-" 라는 게임인데, 어떤 의미로는 이 게임이 제가 태어나서 처음으로 제작한 게임으로 볼 수 있겠네요. 이 게임을 바탕으로 만든 게 Last Hero라는 쯔꾸르 게임이고, 그 게임이 제가 처음으로 만든 비디오 게임이 되겠습니다. 그 후에 일..
게임 제목: Treadmill (쳇바퀴) 장르: 미스터리 퍼즐 / 쯔꾸르 개발 일자: 2020. 03. 06. ~ 03. 11. 개발 소요시간: 5일 (약 40시간) 개발 엔진: RPG MAKER VX Ace 개발 언어: 없음 개발 목적: 게임잼 게임 링크: Treadmill.zip drive.google.com 게임 소개: 트레드밀(Treadmill)은 2020년 3월 경에 게임잼에 참가해 1인 제작한 게임입니다. 딱 5일이라는 데드라인이 걸려있었지만, 개발 기간에 비해 꽤 만족스러운 결과물이 나온 것 같습니다. 게임을 플레이할 시간이 없으신 분들을 위해 아래에 게임 전체 줄거리를 간략하게 적어두었습니다. 게임에 대해 궁금하신거 있으시면 아무 때나 댓글이나 이메일로 알려주세요! 더보기 트레드밀(Trea..
