전체 글 15

최단 경로 알고리즘(다익스트라)

최단 경로란? 가장 짧은 거리를 찾는 알고리즘 그래프가 주어졌을 때 특정 노드에서 다른 노드까지의 최단 거리를 구할 때 사용 경로 계산 방식에는 3가지 종류가 존재 1. One-To-One : 한 지점에서 다른 특정 지점까지의 최단경로 2. One-To-All : 한 지점에서 다른 모든 지점까지의 최단경로 3. All -To -All : 모든 지점에서 모든 지점까지의 최단경로 다익스트라 알고리즘 - 위의 경로 계산 방식 중 2번째 One-To-All의 대표적인 방법 - 음의 간선이 없을 때 정상적으로 작동 - 매 상황에서 가장 비용이 적은 노드를 선택(그리디 알고리즘으로 분류) 동작 과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단거리 노드 선택 4. 해당 노..

알고리즘 2023.06.09

이진탐색(Binary Search)

순차 탐색이란? 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 가장 앞에 있는 원소부터 하나씩 탐색 - 최악의 경우 시간 복잡도는 O(N) def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i+1 이진탐색이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 배열은 정렬이 되어 있어야 함 - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복 비교하여 원하는 데이터를 탐색 - 재귀 함수를 이용하는 방법과 반복문을 이용하는 방법 두가지가 존재 # 재귀 함수 def binary_search(array, target, ..

알고리즘 2023.06.04

정렬

정렬이란? 섞여 있는 데이터를 순서대로 나열하는 것 대표적인 정렬의 종류 O(n²)의 시간 복잡도 - 버블 정렬(Bubble Sort) - 선택 정렬(Selection Sort) - 삽입 정렬(Insertion Sort) O(n log n)의 시간 복잡도 - 병합 정렬(Merge Sort) - 퀵 정렬(Quick Sort) ※ 시간 복잡도 위로 갈수록 간단하고, 아래로 갈수록 복잡해진다. - O(1)과 같은 상수(constant) 형태 - O(log n)과 같은 로그(logarithmic) 형태 - O(n)과 같은 선형 - O(n log n) 과 같은 선형로그 형태 - O(n^c), O(n³)과 같은 다차(polynomial) 형태 - O(c^n), O(3^n)과 같은 지수(exponential) 형태 ..

알고리즘 2023.05.25

DFS, BFS

DFS와 BFS는 그래프를 탐색하는 방법이다 그럼 그래프란?? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 순서대로 모든 정점들을 한 번씩 방문하는 것 node : 위치를 뜻함, 정점 edge : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 뜻함, Link or Branch 무방향 그래프 : 방향이 없는 그래프로 간선을 통해 노드는 양방향으로 갈 수 있음 방향 그래프 : 간선에 방향이 있는 그래프로 방향이 가르키는 곳으로만 갈 수 있음 가중치 그래프(네트워크) : 간선에 비용 또는 가중치가 할당된 그래프 싸이클 : 단순 경로의 시작 노드와 종로 노드가 동일한 경우 비순환 그래프 : 싸이클이 없는 ..

알고리즘 2023.05.25

비트코인 Taproot

비트코인 NFT인 오디널즈는 비트코인 Taproot 업그레이드로 인해 가능하게 되었다. 그럼 Taproot 는 무엇일까? Taproot 탭루트(Taproot)는 일반적으로 식물의 가장 깊고 강한 부분을 뜻한다. 땅 속까지 자라서 여러 방향으로 뻗어 나가기 때문에 제거하기 어렵다. 크립토에서 탭루트는 암호 화폐 뒤에 있는 철학과 기술 전체를 바꾸는 것을 목표로 하는 차세대 비트코인 업그레이드를 말한다. Taproot 업그레이드는 네트워크에 대한 더 높은 수준의 개인 정보 보호, 보안 및 확장성을 의미할 뿐만 아니라 향후 개발을 위한 새로운 가능성의 문도 연다. 또한 Taproot는 블록높이 709,632에서 2021년 11월 14일에 자동으로 활성화 되었으며 소프트 포크로 진행되었다. 블록체인 포크는 단순..

블록체인 2023.02.14

비트코인 NFT: 오디널즈

오늘은 오랜만에 블로그 제목에 맞게(?) 블록체인 관련 글을 작성하고자 한다. 최근 비트코인에서도 NFT를 할 수 있게해주는 오디널즈 프로토콜이 공개되었다. 명칭은 NFT라고 부르지는 않고 Inscriptions라고 부른다 오디널즈는 비트코인 코어 컨트리뷰터(contributor)인 카세이 로다모가 개발하였다. 오디널즈 프로토콜은 비트코인 네트워크에서 이루어진 확장성 관련 2가지 업그레이드를 활용해 개발되었다. 1. 세그윗(SegWit): 비트코인 네트워크에서 서명을 거래 데이터와 분리함으로써 블록 공간을 늘림(2017년) 2. 탭루트(Taproot): 효율성과 프라이버시 강화에 초점(2021년) 기존 NFT의 경우 블록체인 네트워크 온체인상에 저장되는 방식이 아닌 원본 데이터는 확장성과 비용을 이유로 ..

블록체인 2023.02.12

홀로그램 우주 - 열역학 제2법칙

오늘은 어렵지만 저번에 영상으로 봤던 홀로그램 우주에 대해 글을 쓰고자한다. 처음에 제목만 봤을 때는 그냥 말도 안되는 소리라고 생각했다. 하지만 다 보고 충격을 먹었던 경험이 있다. 그럼 우선 홀로그램이란 무엇일까? 홀로그램은 2차원 평면에 3차원의 입체를 표현하는 기술 몇몇 과학자들은 우주가 홀로그램이다라는 주장을 했다 우리가 보는 사물, 신체 등과 같은 정보들은 지구에서 멀리 떨어져있는 우주의 경계면에 저장돼 있고 저장된 정보를 바탕으로 홀로그램을 쏘아서 우리의 세계에 투영 된다는 이론이다 음...? 그냥 공상과학 같기도한데... 그런데 놀라운점은 스티븐 호킹을 비롯한 여럿 과학자들이 블랙홀을 연구하다가 논리적으로 증명했다 우선 홀로그램 우주론을 알기 위해선 블랙홀의 특성을 알아야한다. 여기서부터 ..

과학 2023.02.11

언어모델

요즘 ChatGPT 정말 핫하다 그래서 블록체인이 아니지만 덕배도 공부를 해봤다 우선 ChatGPT가 뭘까? ChatGPT는 언어 모델이다 그것도 엄청나게 똑똑한 얼마나 똑똑하냐면! 미국 변호사, 미국 의사 면허 등등 통과하는 수준이다(나보다 똑똑한데?) 그럼 언어 모델은 뭘까? 언어 모델은 단어를 자동완성 하는 것 이다. 예를 들어 대한민x => 대한민"국" 블록x인 => 블록"체"인 와 같이 이 단어 뒤에는 이 단어가 오는 것이다 라는 모델을 정립하는 것이다. 하지만 블록체인일수도 있고 블록죄인일수도 있지않나? 라고 생각할 수 있다 이런경우는 "확률 모델" 이라고 한다. 블록 다음 99% 확률로 체인이 나오고 1% 확률로 죄인이 나오는 모델이 확률모델이라고 한다. 덕배도 ChatGPT에 질문을 해보았..

인공지능 2023.02.10