누적 합(Prefix sum)계산 양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘이다. 1. 기본 원리1) 1차원 배열1차원 배열에서 i번째부터 j번째 인덱스까지 k를 더한 것을 기록하려면, 새로운 배열의 i번째 인덱스에 k를 더하고 j+1번째 인덱스에 k를 빼면 된다.새로운 배열의 크기는 기존 배열 크기보다 하나 이상 크게 만든다. 예를 들어 크기가 5인 배열에서 0번째부터 2번째 인덱스까지 N을 빼고 싶다면 다음과 같이 누적 합 배열을 만든다.{ -N, 0, 0, N, 0, 0 } 위 새로운 배열을 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다.  추가로 1번째부터 2번째 인덱스까지 M을 더하고 싶다면 누적 합 배열에 값을 추가한다.{ -N, -M, 0, N, M, 0 }..

8장 NoSQL 기초 앞서 알아본 데이터베이스는 관계형 데이터베이스이다. 관계형 데이터베이스는 테이블과 외래 키 등을 사용하고 다양한 종류의 질의 구문으로 원하는 정보를 다각적으로 빠르게 추출할 수 있다. 또 데이터 일관성을 중요하게 생각한다. 데이터베이스 중 또 다른 하나인 NoSQL는 관계형 데이터베이스에서 전통적으로 중시하던 몇 가지를 포기하는 대신 다른 측면의 장점을 가진다. 1. 관계형 데이터베이스와 NoSQL 관계형 데이터베이스는 오랜 역사를 지니고 있지만, 특정 상황에서 몇 가지 부족한 점이 있다. 예를 들어 로그 데이터를 한 테이블에 기록할 때 불편할 수 있다. 로그 데이터가 누적되어 테이블에 약 1억 개의 레코드가 쌓였을 때 유지 보수를 위해 필드 하나를 더 추가해야 하는 상황이 오면, ..

중간에서 만나기(Meet In The Middle) 알고리즘 문제를 풀 때 완전 탐색으로 탐색하는 경우, 탐색의 범위가 커질수록 경우의 수와 연산량이 기하급수적으로 늘어나는 것을 볼 수가 있다. 이때 중간에서 만나기 방식을 사용하면, 시간 복잡도를 제곱근만큼 줄일 수 있다. 중간에서 만나기 방식은 앞쪽과 뒤쪽에서 절반씩 접근하여 중간에서 탐색한 결과가 만나게 하는 탐색 기술을 의미한다. 즉, 중간에서 만난 연산의 결과를 합쳐 전체 결과를 뽑아내는 것이다. 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사..

7장 데이터베이스 기초 1. 플레이어의 정보 저장 싱글 플레이 게임을 만들 때는 보통 플레이어의 로컬 컴퓨터 안에 저장한다. 그러나 멀티 플레이 게임을 만들 때도 싱글 플레이와 같이 로컬 컴퓨터 안에 저장한다면, 다음과 같은 문제가 발생할 수 있다. 플레이어가 컴퓨터를 변경하면, 자신이 하던 플레이 정보를 이어서 할 수가 없다. 플레이어가 해킹을 할 줄 안다면, 플레이 정보를 조작할 수 있다. 따라서 온라인 게임에서는 플레이어 정보를 클라이언트가 아닌 서버에만 저장한다. 클라이언트는 로그인 후 플레이어 정보를 서버에서 받아 사용한다. 플레이어 정보를 서버에 저장하는 방법에는 크게 파일, 데이터베이스가 있다. 상용으로 서비스되는 게임들은 대부분 데이터베이스를 이용해 플레이어 정보를 저장한다. 플레이어 각각..

6장 게임 네트워크 엔진 프라우드넷 1. 게임 서버, 네트워크 엔진 게임 서버와 멀티플레이어 처리를 개발할 때 네트워킹 처리를 위해 보통 소켓 API를 이용한다. 그러나 소켓 API만 이용하면 다음과 같은 번거로움이 발생할 수 있다. 운영체제마다 소켓 API를 사용하는 방식에 차이가 있다. 소켓 API에서 제공하지 않는 기능은 직접 만들어야 한다. 그래서 이러한 문제를 개선하기 위해 네트워크 엔진을 사용하기도 한다. 2. 개발 환경과 기본 모듈 네트워크 엔진 중 하나인 프라우드넷은... 상업용 소프트웨어로 개인이나 특정 조건의 인디 개발사에서는 무료로 사용할 수 있다. 클라이언트-서버 간 네트워킹과 클라이언트 간 직접 네트워킹을 단순하게 사용할 수 있게 하며 네트워크 암호화, 암축, 흐름 제어 등 기능을..

5장 게임 네트워킹 1. UML UML은 단순히 플로차트 그 이상의 역할을 한다. 데이터 정의와 프로세스 정의가 편해지고 프로그램 구조 명세를 표현하는 대표적 수단이다. 1) UML 시퀀스 다이어그램 UML 시퀀스 다이어그램은 객체와 메시지를 사용하고 객체 간 메시징 흐름을 일목요연하게 표현할 수 있다. 객체는 상호 작용의 주체(클라이언트, 서버)로 네모 상자에 해당된다. 메시지는 상호 작용의 내용으로 가로 화살표에 해당된다. 2) 액티비티 다이어그램 시퀀스 다이어그램은 주고받은 메시지를 어떻게 처리하는지 자세하게 표현하기엔 한계가 있다. 그래서 시퀀스 다이어그램에 플로차트를 함께 사용한다면, 보다 자세하게 프로그램의 실행 방식을 그림으로 묘사할 수 있게 된다. 이것이 액티비티 다이어그램이다. 실런더 도..