CS/오토마타
[오토마타] 1. 기본적인 수학적인 지식
오토마타를 공부할 때는 집합, 그래프, 증명 기법과 관련된 기본적인 이산 수학 지식이 필요하다.관련된 수학 지식을 가볍게 정리하는 것으로 정리를 시작해본다. (정리 예정.. 사실 정리하다가 브라우저가 갑자기 꺼져서 날아감 ㅠㅠ)
분류 전체보기
CS/블록체인
[블록체인] 6. Proof-of-Work (Consensus Protocol & Native Currency)
비잔틴 장군 문제 (Byzantine Generals Problem)비잔틴 장군 문제는 분산 시스템을 공부할 때 나오는 유명한 문제로, 1980년에 발표된 람포트라는 컴퓨터 과학자의 논문에서 처음 소개되었다. 그림과 같이 여러 장군들이 하나의 성을 점령하기 위해 일제히 공격을 하려고 한다.그리고 각각의 장군들은 메신저를 보내 메세지를 전달하는 방식으로 통신해야 한다.(현대로 치면 네트워크를 통해서 메세지를 전달하는 것과 같다. 속도는 훨씬 느리겠지만..) 그런데 이 장군들 사이에 스파이가 있다고 해보자.안 그래도 실시간으로 동시에 공격하려면 적절하게 의견을 합의해야하는데, 스파이까지 고려하면서 스파이가 아닌 장군들이 같은 의견을 공유하는 것은 쉽지 않을 것이다.비잔틴 장군 문제는 스파이를 제외하고 정직한..
CS/기초데이터베이스
[데이터베이스] 4. Key Constraints, Participation Constraints
이번 글에서는 두 엔티티가 맺는 관계에 걸 수 있는 다양한 제약조건에 대해 정리해본다. Key Constraints키 제약조건은 다른 엔티티와의 관계에 참여함에 있어서 최대 하나의 엔티티와만 관계를 맺을 수 있음을 나타내는 제약조건이다.즉, 지금 현재 엔티티의 키가 다른 엔티티의 키와 관계를 맺을 때 하나의 엔티티하고만 관계를 맺을 수 있다는 것이다.키 제약조건은 관계를 그을 때 화살표로 나타냄으로써 명시할 수 있다. 그림과 같은 관게를 보자.그림은 직원이 부서를 관리하는 관계를 나타내고 있다.이때 부서는 Manage 라는 관계에 대해 키 제약조건이 걸려있다. 이는 부서가 Manage 관계에 참여함에 있어서 최대 1개의 엔티티하고만 Manage 관계를 맺는다는 것을 의미한다.자연어로 표현한다면, 부서..
CS/블록체인
[블록체인] 5. 트랜잭션 포맷
비트코인의 트랜잭션은 하나 이상의 input 과 하나 이상의 output 으로 구성되어있다.비트코인 인풋은 이전 트랜잭션의 아웃풋으로부터 비트코인을 가져온다는 의미이다. 전통적인 은행 시스템에서 돈을 보내는 과정을 생각해보자.내가 국민은행 계좌에 10만원을 갖고 있을 때, 친구의 카카오뱅크 계좌로 5만원을 보낸다고 하면,나는 국민은행 계좌에 로그인해서 국민은행 서버에게 카카오뱅크 계좌로 5만원을 보내라는 트랜잭션을 지시하면 된다.그러면 은행 서버는 이 트랜잭션을 지시하는 사람이 정말 그 계좌의 주인이 맞는지 확인할 것이다. (otp 등 인증수단)그리고 이 확인 절차가 통과되었을 때, 계좌의 잔액을 확인한 뒤, 잔액이 충분하다면 돈이 실제로 이동한다. 전통적인 은행 시스템에서 돈을 보낼 때는, 오로지 현재..
CS/블록체인
[블록체인] 4. 디지털 서명과 비트코인 주소
디지털 서명비트코인에서는 비대칭키 암호화를 이용해 디지털 서명을 남긴다.비대칭키는 공개키와 비밀키라는 2가지 키를 사용한다.이 두가지 키는 랜넘 넘버로부터 만들 수 있다. (우리는 암호학을 공부하는 게 아니므로 구체적인 방법은 넘어가자)이때 비대칭키 암호화 방식은 지난 글에서도 정리한 적 있듯이, 두 가지 용도로 사용될 수 있다. 첫 번째는 공개키로 메세지를 암호화 한 뒤, 비밀키로 이를 해독하는 것이다.만약 앨리스가 밥에게 밥만 알아볼 수 있는 내용으로 암호문을 보내고자 한다면, 밥이 제공하는 공개키로 메세지를 암호화해서 밥에게 보내면 된다. 그 메세지는 밥이 가진 비밀키로만 해독할 수 있기 때문이다. 두 번째는 비밀키로 데이터에 서명을 남긴 뒤, 공개키로 이를 검증하는 것이다.비트코인에서는 이 용..
CS/블록체인
[블록체인] 3. 블록체인의 구조와 해시 함수
이제부터 비트코인과 블록체인의 기술적인 내용을 다루려고 한다.블록체인은 이름 그대로 여러 블록들이 서로서로 고리를 물고 체인처럼 연결된 구조를 하고 있다.이 구조로 어떻게 탈중앙화된 화폐를 만들 수 있을까? 우선 비트코인에는 '트랜잭션' 이라는 개념이 존재한다.이 트랜잭션은 비트코인을 사용해서 발생하는 모든 거래 정보를 나타낸다.Alice가 Bob에게 1비트코인을 지불하고 상품을 받는 거래를 한다고 한다면,'엘리스가 밥에게 1비트코인을 지불한다' 라는 행위가 트랜잭션이 되는 것이다. 이때 비트코인에서 발생하는 모든 트랜잭션에는 '서명'이 필요하다.비트코인은 Permissionless 블록체인이라 누구나 접근할 수 있는 데이터베이스기 때문에,이 트랜잭션이 '내가' 발생시킨 트랜잭션임을 확실하게 서명을 통해..
CS/블록체인
[블록체인] 2. 블록체인의 활용
블록체인의 활용블록체인은 서브프라임 모기지 사태가 발단이 되어, 금융과 관련된 여러가지 문제를 기술로 해결하려는 시도에서 등장한 산물이다.따라서 블록체인은 그 활용 분야도 금융 분야에서 많이 활용된다. 1. Payment System비트코인의 등장 배경은 결제 시스템을 중앙화된 은행과 정부 기관에 의존하지 않는 것이 등장 배경이었다.따라서 결제 시스템에서 대표적으로 활용될 수 있다.블록체인을 통해서 일종의 입출금 장부를 모두가 공유하고 서로 서로 검증하여 신뢰를 얻는 것이다. 2. Venture Capital크라우드 펀딩과 같이 돈을 모으는 데에도 활용할 수 있다.블록체인은 기술 특성상 내부에 '코드' 를 집어 넣을 수도 있다. (스마트 컨트랙트)이때 내가 투자받은 금액에 대해서 좋은 성과를 낼 때마다 ..
CS/기초데이터베이스
[데이터베이스] 3. ER-Model (Entity, Relationship, Key)
데이터베이스 설계데이터베이스를 설계하는 과정은 크게 3단계가 있다. 1. 요구사항 분석 (requirement analysis)정말 장인 급으로 프로그래밍을 잘하지 않는 이상, 우리는 설계를 잘 할 수 있어야 한다.설계를 잘하려면 먼저 고객이 자연어로 말하는 요구사항을 잘 분석해서 이를 토대로 데이터베이스를 설계할 수 있어야 한다. 2. 개념적 데이터베이스 설계 (conceptual database design)고객의 요구사항을 분석했다면, 그 결과를 토대로 먼저 개념적으로 데이터베이스를 설계한다.이때 UML, ERD 등을 사용하여 데이터베이스를 설계할 수 있다. 3. 논리적 데이터베이스 설계 (logical database design)데이터베이스 설계가 끝났다면, 실제로 사용할 데이터베이스를 선택하고..
CS/기초데이터베이스
[데이터베이스] 2. 트랜잭션
트랜잭션트랜잭션(transaction)은 원자성이 있는(atomic, 쪼개지지 않는) 데이터베이스 내 일련의 동작들을 말한다.데이터베이스 내 동작들이라고 한다면, 당연히 데이터의 읽고 쓰기 과정을 말할 것이다. 예를 들어, 어떤 공동 계좌가 하나 있다고 생각을 해보자.이 계좌에는 1만원의 돈이 들어있다.그리고 '공동' 계좌이기 때문에, 계좌에서 돈을 넣고 빼는 행위는 여러 사용자에 의해서 병행으로 발생할 수 있다. 만약 내가 이 계좌에서 1000원을 출금을 할 때 필요한 과정을 생각해보면 다음과 같이 생각할 수 있다. 1. 데이터베이스에 접근인가를 받아 접근한다. (은행 계좌라면 본인 인증은 필수 일 것이다.)2. 계좌의 잔액을 조회한다. (10000원 read)3. 만약 계좌의 잔액이 1000원보다 많..
알고리즘 (PS)/BOJ
[백준] 13549 - 숨바꼭질 3 (BFS 풀이)
최단 경로 스터디 자료를 만들다가 BFS로 최단 경로를 찾는 연습문제로 숨바꼭질이 생각나서 다시 풀어봤다.그런데 단순하게 BFS로 풀릴 줄 알았는데 맞왜틀을 해서 충격을 받았다.. (심지어 과거의 나는 1트만에 풀었었다..) 과거에 풀었던 풀이는 우선순위 큐를 이용한 다익스트라 풀이였다.이 풀이는 정말 다익스트라의 최단 경로 알고리즘을 곧이 곧대로 사용하는 것이니 틀릴 여지가 거의 없다. 그런데 BFS로 이 문제를 푸는 경우에는 여러가지를 고려해야 했다.from collections import dequen, k = map(int, input().split())visit = [False] * 200001d = deque()d.append((n, 0))visit[n] = Truewhile d: now..
