wood's: 11월 2016

11월 29, 2016

rdbuf() : 서로 다른 두 스트림을 연결

std::ios::rdbuf()

일부 derived stream class(stringstream or fstream 등)는 객체 생성 시에 associated 된 internal stream buffer를 가진다. rdbuf는 stream의 associated stream buffer를 변경하는 함수로, stream buffer 자체에는 아무련 영향을 주지 않는다.

cin/ifstream, 혹은 cout/ofstream 등, 서로 다른 두 stream을 한 스트림에서 다른 스트림으로 리디렉시키는데 사용한다. 예를 들어 어떤 프로그램에서 input을 console과 cin을 통해 입력받는데, input을 입력받는 코드 부분을 수정하지 않고 file stream을 통해서 입력을 받도록 프로그램을 수정하고 싶을 때 유용하게 사용할 수 있다.

(1) streambuf* rdbuf() const;
(2) streambuf* rdbuf(streambuf* sb);

(1) accessor. 현재 stream의 associated streambuf의 포인터를 리턴.

(2) mutator. 현재 stream의 associated streambuf를 sb로 바꾸고 stream의 error state flags를 초기화. 이전 associated streambuf의 포인터를 리턴.

예제

reference

rdbuf() |cplusplus.com

11월 25, 2016

SQL(Structured Query Language) 종류

SQL이란

RDBMS(Relational DataBase Management System)을 관리하기 위해 설계된 특수한 목적의 프로그래밍 언어로 데이터베이스로부터 정보를 얻거나 갱신하기 위한 표준 대화형 프로그래밍 언어. RDBMS에서 데이터베이스 스키마 생성과 수정, 자료 검색과 관리, 데이터베이스 객체 접근 권한 관리나 트랜잭션 관리 등을 위해 고안됨. DDL, DML, DCL 과 같이 세분화할 수 있음.

DDL(Data Definition Language)

SQL에서 RDBMS의 '구조'를 정의하는 언어 요소. 테이블 생성과 삭제, 변경 등을 담당.

CREATE
DROP
ALTER

DML(Data Manipulation Language)

SQL에서 '데이터 조작'을 위한 언어 요소. 데이터 검색, 등록, 삭제, 갱신을 담당.

INSERT INTO
SELECT .. FROM ..
DELETE FROM ..
UPDATE .. SET ..

DCL(Data Control Language)

SQL에서 데이터에 대한 액세스를 제어하기 위한 언어 요소. 권한의 부여, 박탈 등을 담당.

GRANT
REVOKE
SET TRANSACTION
BEGIN
COMMIT
ROLLBACK
SAVEPOINT
LOCK

Cursor

SELECT statment 실행 결과를 하나의 row 씩 처리하기 위해 서버 측의 result set과 row 획득 위치를 나타내는 개념을 의미. 주로 어플리케이션 등에서 SQL 검색을 실행 후 결과를 처리하기 위해 사용.

reference

SQL |wiki

SQL(Structured Query Language) 종류

SQL이란

DDL(Data Definition Language)

SQL에서 RDBMS의 '구조'를 정의하는 언어 요소. 테이블 생성과 삭제, 변경 등을 담당.

CREATE
DROP
ALTER

DML(Data Manipulation Language)

SQL에서 '데이터 조작'을 위한 언어 요소. 데이터 검색, 등록, 삭제, 갱신을 담당.

INSERT INTO
SELECT .. FROM ..
DELETE FROM ..
UPDATE .. SET ..

DCL(Data Control Language)

SQL에서 데이터에 대한 액세스를 제어하기 위한 언어 요소. 권한의 부여, 박탈 등을 담당.

GRANT
REVOKE
SET TRANSACTION
BEGIN
COMMIT
ROLLBACK
SAVEPOINT
LOCK

Cursor

reference

SQL |wiki

11월 21, 2016

2의 보수

보수(complement)란?

각 자리의 숫자의 합이 어느 일정한 수가 되게 하는 수.

1의 보수

binary 에서 원래 수를 반대로 뒤집은 것.

6: 00000110
6에 대한 1의 보수: 11111001

2의 보수

원래 값의 1의 보수를 취한 후 1을 더한 것으로 원래 값의 음수에 해당. 2의 보수는 binary에서 음수를 표현하는 과정에서 도입된 개념. 최상위 비트 하나를 음수를 표현하는 경우 +0(00000000)과 -0(11111111)의 두개의 0이 존재하는 문제가 발생하는데 2의 보수법으로 이런 문제를 피해갈 수 있음.

6: 00000110
-6 (6에 대한 2의 보수): 11111010

Binary subtraction

6 - 3 = 6 + (-3)

00000110 - 00000011 = 00000110 + 11111101 = 00000011

reference

11월 17, 2016

Random Access Iterator

http://www.cplusplus.com/reference/iterator/RandomAccessIterator/

Random-access Iterator?

자신이 가르키고 있는 element과 연관되어 있는 임의의 position에 접근하여 포인터와 같은 functionality 를 제공할 수 있는 iterator. 모든 Random-access iterator 는 bidirectional iterator이며, 어떤 element에도 constant time으로 접근할 수 있음.

Funtionalities of Random-access Iterator

Bidirectional Iterator 가 제공하는 모든 기능
Arithmetic operator ex) it1+n, n+it1, it1-n, it1-it2
Inequality relation operator ex) it1<it2, it2>it1, it1<=it2, it1>=it2
Compound assignment operator ex) it1+=n, it1-=n
Offset dereference operator ex) it1[n]

reference

Bidirectional Iterator

http://www.cplusplus.com/reference/iterator/RandomAccessIterator/

Bidirectional Iterator

유효한 범위의 sequance of element에서 begin, end 양방향의 element에 모두 access 가능한 iterator. 모든 Bidirectional iterator 는 Forward Iterator.

Funtionalities of Bidirectional Iterator

Default/copy/copy-assignment constructible ex) X it1; , X it2(it1); , it2 = it1;
In/Equality operator ex) it1==it2, it1!=it2
Dereference as R-value ex) *it1, it1->m
Dereference as L-value ex) *it1 = t
Increment ex) ++it1, it1++
Decrement ex) --it1, it1--
L-value are swappable ex) swap(it1, it2)

X는 Bidirectional iterator type, m은 가르키는 멤버, t는 iterator가 가르키는 타입의 object.

reference

11월 13, 2016

Monte-Carlo 알고리즘과 MCTS(Monte-Carlo Tree Search)

Monte-Carlo 알고리즘

난수를 사용하여 함수의 값을 확률적으로 계산하는 알고리즘을 부르는 용어. 계산하려는 값이 닫힌 값으로 표현되지 않거나 복잡한 경우, 이를 근사적으로 계산하기 위해 사용된다. Monte-Carlo 알고리즘을 적용해 원의 넓이를 구하는 경우, 원과 원에 내접하는 정사각형을 그리고 정사각형 안에 많은 수의 점을 찍어 점이 원의 내부에 찍힌 확률을 계산하면 원의 넓이를 근사적으로 구할 수 있다. Monte-Carlo 알고리즘은 임의 시행의 횟수를 증가시킬 수록 정확도가 증가한다.

Monte-Carlo Tree Search(MCTS)란?

MCTS는 최선의 선택(optimal decision)을 찾는 방법이다. MCTS는 의사 결정을 위한 체험적 탐색 알고리즘으로 수식을 만들어 해를 찾기가 쉽지 않을 때 주로 사용되는데, 예를 들어 게임에서 최선의 수를 찾기 위한 방법으로 활용할 수 있다. MCTS를 게임에 적용한다면, 게임에서 두는 각각의 수가 노드이고 게임의 전체 과정은 각 수의 연속인 트리로 표현된다. 각 노드에는 승률이 기록되어 있으며, 게임에서 최선의 수를 찾는 과정은 가장 승률이 높은 노드를 찾아가는 것으로 근사될 수 있다. MCTS는 각 노드 별 승률을 계산하고 승률이 높은 노드를 찾아가는 과정이라 할 수 있다.

트리 탐색의 문제점은 자식 노드가 많아지면 탐색에 시간이 굉장히 많이 걸린다는 점이다. 자유도가 높은 게임의 경우 자식 노드(다음에 둘 수 있는 수)가 굉장히 많아져 모든 결과를 살펴보고 노드 별 승률을 계산하는 것이 거의 불가능하다. MCTS는 전체 가능성을 모두 탐색하지 않고 다수의 random simulation을 통해 게임 결과를 구하여 이를 노드의 승률에 적용하는 알고리즘으로, 자유도가 높은 게임에서도 높은 효율성을 보여준다. MCTS 알고리즘은 Selection, Expansion, Simulation, Back propagation 네 가지 단계로 이루어진다.

Selection (선택): 루트 R에서 시작하여 연속되는 자식 노드를 따라 내려가 노드L을 선택한다.
Expansion (확장): 노드L에서 게임이 종료되지 않은 경우, 새로운 자식 노드C를 생성하거나 기존의 자식 노드 중 하나를 노드C로 선정한다.
Simulation (시뮬레이션): 노드C를 대상으로 random playout을 수행한다
Back propagation (역전파): playout의 결과를 노드 C에서 루트 R까지 업데이트한다.