104%

이 문제는 알고리즘 수업시간때 배웠던 최소 신장 트리를 구하는 알고리즘 2개(프림,크루스칼)중 하나를 이용해서 푸는 문제이다. 나는 크루스칼 알고리즘으로 풀었다. 크루스칼알고리즘의 시간 복잡도는 엣지의 개수가 E일때 O(ElogE)라고 한다. 왜냐면 엣지를 처음에 가중치가 낮은 순서대로 오름차순으로 정렬하는데, 이 정렬이 최소신장트리를 구하는 알고리즘에서 제일 오래걸리는 연산이기 때문이다. 이 문제를 풀기위해서는 분리-집합이라는 개념도 알아야 한다. 유튜브에 아주 좋은 강의(우리 교수보다 훨씬 잘가르치는듯)가 있으니 꼭 이걸 듣고나서 문제를 풀어 보길 바란다. 듣고나면 왜 코드가 이렇게 짜여졌는지 이해할수 있게 된다. https://www.youtube.com/watch?v=i4ZDgJS0_yMhttps..

업캐스팅이란 부모 클래스의 자료형으로 자식클래스를 가리키는 것이다. 예를 들어 Person이라는 부모 클래스와 이 클래스를 상속받는 Student,Chile,Adult라는 3개의 자식 클래스가 존재한다고 해보자. 이때 Person* p = new Student(); 와 같이 부모 클래스의 포인터로 자식클래스를 가리키는 현상이다. 이렇게 되면 부모클래스 자료형 p로는 Student에 존재하는 public 멤버 중에서 Person의 멤버만 접근이 가능하다. 다운 캐스팅이란 업캐스팅된 p의 자료형을 다시 자식 클래스의 자료형으로 바꿔주는 작업이다. 이때는 명시적으로 형변환을 해줘야 한다. Student* s = (Student)p; //명시적 형 변환 이렇게 될 경우 Student 객체를 Student형 포인..

재귀를 활용한 좋은 문제인것 같다. 정사각형을 정해진 순서대로 방문해야 하고 , 어떤 특정 점을 방문했을시 그 점이 몇번만에 방문된건지 출력하면 되는문제. 지금 현재 재귀 함수가 커버하는 사각형 영역을 식별하기 위해서 시작점(x,y)와 그 정사각형의 길이가 필요하다. 8*8에서 방문 순서를 보면처음에 8*8 정사각형의 Z 그다음 4*4 정사각형의 Z 4개 그다음 2*2 정사각형 16개 1*1 정사각형 64개 이런식으로 재귀호출 해야한다. DFS문제를 많이 풀다보니까 재귀호출에 대한 이해가 조금은 깊어진것 같다. 근데 단순히 주어진 순서대로 방문만 하는 경우 시간초과가 뜬다. 왜냐하면 정사각형이 최대 15*15의=225의 크기를 가질수 있으므로 엄청나게 많은 재귀 호출을 하게 될수 있다. 그렇기 때문에 현..

블록을 블록체인 내에서 유일하게 식별할수 있게 블록해쉬라는게 존재한다고 했었다. 이 블록해쉬값은 위 그림에서 핑크색으로 표시된 값이다.한마디로 말해서 블록체인 내에서 그 블록이 갖는 아이디라고도 볼 수 있으며, 이 블록해쉬값은 블록헤더를 요약한 어떤 해쉬값이다.블록 헤더에 포함된 6가지 정보를 묶어서 해쉬에 넣으면 블록 해쉬값이 나오게 되고 이 블록 해쉬값은 이 블록의 아이디가 된다. 그렇기 때문에 이 6가지 정보중 어떤 하나라도 변경되게 되면 블록 해쉬값이 달라지게 된다. 그 말 뜻은, 마음대로 블록 헤더에 있는 값을 바꿀수 없다는 의미이다. 왜냐면, 블록들은 서로 연결되어 있기 때문에 만약에 블록0의 내용을 누가 임의로 수정하게 될 경우 그 블록해쉬값이 달라지게 되고, 그렇게 되면 블록1의 Previ..

블록체인 네트워크 내에 A라는 노드가 현재 5BTC를 가지고 있는데 B,C노드에게 각각 5BTC를 전송하려고 하는 상황을 가정해보자. 원래 현실세계에서는 이런 일이 불가능한 일이다. 잔액이 5BTC인데 총 10BTC를 송금하려고 하는 상황이기 때문이다. 하지만 블록체인 내에서는 이 이중 지불 자체는 가능하다. 왜냐하면, 네트워크 내의 모든 노드들이 같은 블록체인을 갖고 있다. 이 뜻은, 모든 거래 내역이 저장된 똑같은 내용의 거래 장부를 모든 네트워크 내의 노드가 가지고 있다는 소리이다. 따라서 내가 캐나다에 있는 컴퓨터에서 이 블록체인 네트워크에 접속하게 될 경우 그 컴퓨터에서 B에게 5BTC를 보내고, 호주에 있는 컴퓨터에서 C에게 5BTC를 보내는 일이 가능하다. 왜냐면 캐나다에서 BTC를 송금한다..

앞에서 블록 체인은 거대한 분산 공개 장부라고 했다. 이 분산 공개 장부는 여러 개의 노드에 복사되어 있으며, 여러 개의 노드는 p2p로 연결되어 블록 체인 네트워크를 형성한다. 그리고 하나의 거래 정보가 발생하면 이 거래 정보는 블록 체인 네트워크에 분산되어 있는 수많은 노드에 전파되어야 한다.다음 그림과 같이 사용자 F가 지갑 앱에서 C에게 수수료 0.001BTC와 함께 1.6BTC를 보내면, 지갑 앱은 블록 체인 네트워크 상의 노드 A에 거래 정보를 전송한다.거래 정보를 받은 노드 A는 먼저 해당 거래의 유효성을 검증한 후에 그 거래를 아직 블록 생성 작업이 시작되지 않은 후보 블록에 추가하고, 인접한 다른 노드에 그 거래 정보를 전파한다.거래 정보를 전파받은 노드 B도 마찬가지 방식으로 블록 체인..

어떤 블록을 생성하기 위한 난이도가 백만이라고 해보자. Brute force 방식으로 nonce 값을 계속 조정해가면서 백만보다 낮은 숫자를 찾는 과정이 마이닝(채굴)과정이다. brute force방식이므로 빠르게 뺑뻉이 연산을 돌릴수 있는 하드웨어가 필요하고 엄청난 전기세가 필요하므로 요즘 전기세나 땅값이 싼 중국에 작업장을 차려놓고 마이닝하는 업체들이 많아지고 있는것이다. 만약에 예를들어서, nonce값이 10일때 해쉬함수에 넣어서 나온 해쉬값이 백만보다 낮은 경우 채굴에 성공한 것이고, 그런 경우 블록에 이 넌스값(블록을 생성하기 위해 찾아낸 어떤 해답이라고 볼수 있음)을 박고, 넌스값이 포함된 블록 헤더를 해쉬한 블록해쉬값을 적어서 네트워크에 전파시키는것이다(너네들 이 블록을 각자 블록체인에 추가..