이것 저것 &

FOUNDERS X SAMSUNG Blockchain

founders 3기 1일차 교육과정을 받았습니다.
삼성전자 수원사업장에서 교육을 받았고, Hexlant의 유춘 멘토님, GXC의 엄지영 멘토님께서 블록체인 전반과 기술 개요에 대해 강연을 해주셨습니다. 삼성전자 사업장에서의 사진촬영이 엄격하게 금지되어 있어서 강연자료는 따로 촬영하지 못했습니다.

블록체인이란?

 블록체인은 관리 대상 데이터를 '블록'이라고 하는 소규모 데이터들이 P2P 방식을 기반으로 생성된 체인 형태의 연결고리 기반 분산 데이터 저장 환경에 저장하여 누구라도 임의로 수정할 수 없고 누구나 변경의 결과를 열람할 수 있는 분산 컴퓨팅 기술 기반의 원장 관리 기술입니다. (P2P는 쉽게 얘기하면 토렌트의 원리입니다. 서버에서 데이터를 받아오는 것 이 아닌 각 클라이언트에서 데이터를 전달해주는 형태입니다.)

(어려운 말.. 굵은 글씨만 읽으셔도 돼요..)

 이는 근본적으로 분산 데이터 저장기술의 한 형태로, 분산 노드의 운영자에 의한 임의 조작이 불가능하도록 고안되었습니다. 블록체인 기술은 비트코인을 비롯한 대부분의 암호화폐 거래에 사용됩니다. 암호화폐의 거래과정은 탈중앙화된 전자장부에 쓰이기 때문에 블록체인 소프트웨어를 실행하는 많은 사용자들의 각 컴퓨터에서 서버가 운영되어, 중앙에 존재하는 은행 없이 개인 간의 자유로운 거래가 가능합니다. 즉, 데이터를 분산처리하는 ‘탈중앙화’를 핵심으로 하는 기술입니다. 대표적인 예시로는 비트코인이 있습니다. 

 금융거래 시에 중개인의 역할은 절대적입니다. 돈을 주고받을 때 동기화 문제를 중개인이 해결해주는 형태이기 때문입니다. 이때 여러 가지 문제점이 있습니다. 정보에 대한 투명성이 부족하고, 악용될 여지가 있으며, 중앙에 데이터를 보관하기 때문에 보안에 취약합니다. 이러한 문제점을 해결하기 위해서 블록체인이 고안되었습니다.

 하지만 블록체인의 단점은 느리다는 것입니다. 트랜잭션들을 서로 공유하며 블록 단위로 장부의 업데이트 정보와 이전 블록 정보 등이 기록이 되는데 서로 모두 공유해야 하기 때문에 TSA가 굉장히 느린 편입니다. (10분을 기준으로 블록이 생성된다고 합니다.) 금전거래에서는 신속성이 요구됩니다. 예를 들어 VISA에서는 초당 약 1700건의 거래를 완료하지만, 블록체인 시스템은 초당 약 15건의 정보만을 처리할 수밖에 없다고 합니다.

 이러한 문제점 때문에 검증된 기업들만에게만 장부를 관리하게 한 블록체인도 생겼습니다. 

 우리는 예전부터 중앙 데이터관리에 익숙해져 있고, 그들이 우리의 정보를 악용하거나 유포한다면 법적으로 제재를 받을 것이기 때문에 당연하게 우리의 정보를 악용해서 사용하지 않는다고 믿고 있습니다. 하지만 블록체인을 원하는 사람들은 특정 기관에서 데이터를 독점하는 것에 대한 반발심을 가지고 있었습니다. 그들은 don't가 아닌 can't를 원했습니다. 우리의 정보를 악용하지 않는 것이 아니라, 아예 못해야 한다는 것입니다. 이러한 당위성을 가지고 현재 블록체인의 연구와 활용방안이 진행되고 있다고 합니다.

+ 추가정보

enterprise 블록체인이란?

 엔터프라이즈 시스템이란 은행, 대기업, 통신사 등 거대한 기업의 비즈니스를 돕기 위한 IT 인프라를 이야기합니다. 엔터프라이즈 시스템은 대용량의 데이터와 트랜잭션을 처리하는 고도의 기술 집약체입니다. 기업 입장에서는 이미 중앙기관에서의 통제와 서버 환경 구축의 완성도가 높기 때문에 위험부담 요소를 가지고 블록체인으로 모든 부분을 변경할 필요가 없습니다. 그렇기 때문에 중앙제어의 장점과 블록체인의 투명성을 고려한 절충안 형태의 블록체인들이 개발이 되고 있다고 합니다. 실제로 블록체인은 이러한 형태로 많이 사용되고 있다고 합니다.

 엄지영멘토님은 이러한 블록체인의 발전과정과 당위성을 이해하고 블록체인에 접근해야한다는 것을 강조하셨습니다. 

남은 교육과정들도 열심히 포스팅하겠습니다:)

출처: https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8

http://media.fastcampus.co.kr/knowledge/wtf_blockchain_bitcoin/

https://github.com/conr2d?tab=repositories

엄지영멘토님 github

카카오 코드 페스티벌  의 카카오 코드 페스티벌 2018 예선 A번 문제입니다. 

간단한 프로그래밍 문제입니다. 

#include <iostream>
using namespace std;
int t = 0, a = 0, b = 0, result = 0;
void festival1(int num) {
	if (num == 1)
		result += 5000000;
	else if (num <= 3)
		result += 3000000;
	else if (num <= 6)
		result += 2000000;
	else if (num <= 10)
		result += 500000;
	else if (num <= 15)
		result += 300000;
	else if (num <= 21)
		result += 100000;
}
void festival2(int num) {

	if (num == 1)
		result += 5120000;
	else if (num <= 3)
		result += 2560000;
	else if (num <= 7)
		result += 1280000;
	else if (num <= 15)
		result += 640000;
	else if (num <= 31)
		result += 320000;
}
int main() {
	cin >> t;

	while (t--) {
		result = 0;
		cin >> a >> b;
		if (a != 0)
			festival1(a);
		if (b != 0)
			festival2(b);
		cout << result << endl;
	}
	
}

전형적인 dp문제입니다.

반복문으로 arr배열을 탐색하면서 

자신보다 arr값이 작고 dp값이 가장큰 값에 자신의 arr값을 더한값이 dp값이 되는 점화식입니다. 

즉 , dp[i] = arr[i] + dp[maxed_index]의 형태가 됩니다.

전체코드입니다:)

#include <iostream>
using namespace std;

int n, result = 0;
int arr[1001] = { 0 };
int dp[1001] = { 0 };


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		int maxed = 0,maxed_index=0;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i] && maxed < dp[j] )
				maxed = dp[j], maxed_index = j;
		}
		dp[i] = arr[i] + dp[maxed_index];
		if (result < dp[i]) result = dp[i];
	}

	cout << result << endl;
}

쉬운 dp 문제입니다.

P(1)부터 P(11)까지 첫 11개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ... 

 dp[n] = dp[n-1] + dp[n-5] 라는 점화식을 찾을 수 있게 됩니다.

정답률이 30%대라는게 믿기지 않을 정도로 쉬워서 의아하며, 

ㅋㅋㅋㅋㅋㅋㅋㅋ

한번 틀렸습니다. 숫자가 증가함에 따라 기하급수적으로 수가 커지는거를 신경못썻습니다. 

int형은 4byte = 32bit = 2의 32승

즉 2,147,483,648x2 만큼의 수를 저장할 수 있습니다.

음수,0양수 모두를 포함해야하기 때문에 아래 표와 같은 범위의 수를 표현할 수 있게 됩니다.

수가 넘어갈때는 제일 아래의 음수값 - 2,147,483,648로 내려가 1씩 올라가며 출력을 하는 구조입니다.

저는 c++에서 long long 형을 사용하여 문제를 해결하였습니다. 

정답코드

#include <iostream>
using namespace std;

long long dp[101] = { 0 };
int t = 0, n;
int main() {
	dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2;
	for (int i = 5; i <= 100; i++)
		dp[i] = dp[i - 1] + dp[i - 5];

	cin >> t;

	while (t--) {
		cin >> n;
		cout << dp[n] << endl;
	}
}

실패코드를 먼저 보여드립니다.

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		cout << dp[i] << endl;
	}
	cout << dp[n] << endl;
}

반례가 있습니다.

12 = 3*2 + 1 + 1 + 1 = 4

12 = 2*2 + 2*2 + 2*2 = 3

명백하게 그리디적인 관점에서 문제를 해결나갈 수 없는 것을 보실 수 있습니다.

즉, 제곱값이 자신보다 작은 모든 제곱근들에서의 경우의 수를 비교해주어 결과값을 도출하여야 하는 문제입니다. 

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		for (int j = num-1; j >= 1; j--) {
			if( (1 + dp[i - j*j]) < dp[i] )
				dp[i] = 1 + dp[i - j*j];
		}
	}
	cout << dp[n] << endl;
}

전형적인 dp문제입니다.

점화식을 고려할때 머리로 연상되지 않습니다.

표를 그리며 차근차근 풀어나가보았습니다.  

예시입력에 경우
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)    [5] 1   1   2   2   3   4   5   6   7   8   10

1의 경우에는 모두 1가지 경우의수를 가지게 되고

2를 포함할 경우 2의 배수마다 경우가 한가지씩 증가하는 것을 확인 할 수 있었습니다.

즉, 2를 포함할 때 1의 경우+ DP[N-2] + 1 의 경우가 됨을 확인할 수 있습니다. 

5를 포함할 때에는 (1의경우가 포함된) 2의 경우 + DP[N-5] + 1 이 됨을 확인할 수 있었습니다. 

즉 점화식을 나타내면 

for (int i = 0; i < n; i++) {
		dp[i][0] = 1;
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num&& i>0) dp[i][j] = dp[i][j - num] + dp[i - 1][j];
			else if(i>0) dp[i][j] = dp[i - 1][j];
			else if (j >= num) dp[0][j] = dp[i][j - num];
		}

	}

네 메모리 초과입니다.. :) ㅋㅋㅋ

문제조건이 4MB였네요. 

int형은 4byte이고 n=100까지, k=10000까지이니 dp 2차원 배열은 4000,000byte= 4000kbyte = 4mbyte이므로 메모리 초과가 나는것입니다. 직관적으로 점화식이 변화하는것을 확인했기때문에 dp[101][10001] 를 dp[10001]로 줄여보겠습니다. 

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num] ;
		}
	}

전체코드입니다. 

#include <iostream>

using namespace std;

int dp[10001] = { 0 };
int n = 0, k = 0;
int arr[100] = { 0 };
int result = 0;

int main() {

	cin >> n >> k;
	
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num];
		}

	}
	cout << dp[k] << endl;
}