-
Terra Smart Contracts
서론 이 글에서는 Terra Blockchain에서 Smart Contract를 어떻게 구현하는지 대해서 간단하게 다루어보려고 합니다. Terra 블록체인의 가장 대표적인 native 코인은 LUNA인데, 이는 coinmarketcap에서 1월 16일 현재 시가총액 9위 (약 $30B) 입니다. Terra Blockchain에서도 Ethereum과 마찬가지로 Smart Contract들을 올릴 수 있는데, 그 언어와 구조가 Ethereum의 Smart Contract들과 많이 다릅니다. 이 글에서는 Terra 블록체인 위에서의 금융적 흐름보다는 Smart Contract 구조와 구현에 대해서 더 집중하겠습니다. 글은 기본적으로 Terra Documentation에서 많이 가져왔으나, 조금 더 이해하기 쉽고 찾아볼 reference가 충분하도록 부가설명을...
-
Python 3의 String 라이브러리 둘러보기
개요 이전에 Python 3에서 문자열 내의 부분 문자열을 빠르게 찾기 위한 fastsearch 기법에 대한 글을 쓴 적이 있습니다. 그 글에서는 문자열 중에서도 특정 기능에 대한 심도 있는 분석을 해보았었는데, Python의 철학이 담긴 대단히 세밀한 디자인과 구현체를 볼 수 있었습니다. 하지만 그것만으로는 Python의 str이 가진 수많은 특징 중 극히 일부 단면만을 보인 듯한 느낌이 들었습니다. 그래서, 이번에는 좀더 str의 전체적인 모습을 두루 살펴볼 수 있도록 보다 큰 그림을 통해 Python 3의 str의 구조는 어떻게 되며, string...
-
알고리즘 문제 접근 과정 7
알고리즘 문제 접근 과정 7 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 방 청소 - COCI 2013/2014 Contest #5 6번 풀이 문제 상황이 단순하지 않아서, 어떻게 풀지 쉽게 감이 오지 않을 수 있습니다. 한 음료를 담을 수 있는 상자는 두 개뿐이지만, 음료를 어떻게든 옮겨서 담을...
-
XOR MST
XOR MST 다음과 같은 완전 그래프를 생각해 보자. 그래프의 정점은 $V$개이다. 각 정점에는 0 이상의 정수 가중치가 붙어 있다. 간선의 가중치는 간선이 잇고 있는 두 정점의 가중치의 XOR 값이다. # 는 이 그래프의 MST를 구하는 문제이다. 이 문제는 cs71107님의 XOR 관련 문제를 푸는 접근법들에도 나왔듯 자릿수가 큰 비트부터 내려가면서 일종의 그리디 알고리즘을 사용하게 된다. 가중치의 범위가 $2^{30}$이므로, 30번째 비트부터 생각해 보자. 어떤 정점의 가중치는 $2^{30}$ 미만일 것이고, 어떤 정점의 가중치는 $2^{30}$ 이상일 것이다. 가중치가 $2^{30}$...
-
Faster Exponential Algorithm for Permutation Pattern Matching
Introduction “스택 수열”이라는 간단한 문제를 생각해 봅시다. https://www.acmicpc.net/problem/1874 이 문제는 스택을 이용한 시뮬레이션으로 해결할 수 있습니다. 요약하면, $[n] := {1, \cdots, n}$의 순열 $\sigma _ {1}, \cdots, \sigma _ {n}$이 주어졌을 때, $1, \cdots, n$을 순서대로 스택에 push(+)했다가 pop(-)하여 $\sigma _ {1}, \cdots, \sigma _ {n}$을 만들 수 있는지를 판별하는 문제입니다. 반대로 $\sigma _ {1}, \cdots, \sigma _ {n}$을 push-pop하여 $1, \cdots, n$으로 정렬할 수 있는지를 묻기도 하는데요, 이 경우에 $\sigma$를 stack-sortable permutation이라고 합니다. “스택...