본문 바로가기

분류 전체보기211

[강의노트] 그래프 순회 -2 (BFS) 그래푸 순회 - 2(BFS) 지난 포스트에서는 DFS에 다루어보았고, 이번에 배울것은 BFS 너비우선탐색이다. 마찬가지로 그래프 순회 기법이다. BFS - 너비우선탐색 너비우선탐색에서 가장 핵심적인 단어를 꼽자면 level 이라고 생각한다. 이 얘기는 뒤에 몇번 더 언급하겠다. BFS는 트리의 level 별로 순회를 한다. 즉 트리에서 루트노드를 기준으로 자식노드로 계속 내려가는 것을 깊이우선탐색이라고 한다면, 기준노드에서 형제노드를 우선적으로 탐색하는 것이 너비우선탐색이다. DFS와는 탐색의 방향성 측면에서 어떻게 보면 반대의 개념이라고도 생각할 수 있다. BFS를 확장해서 해결 가능한 문제를 살펴보자. 두개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾을 수 있다고 한다. 그래프 내 싸이클을 .. 2021. 11. 17.
[강의노트] 그래프 순회 - 1 (DFS와 싸이클찾기) 그래프 순회 - 1 그래프를 구현하는 문제에 대해서 지난 시간에 해결해보았다. 이번에 배울것은 그래프 순회이다. 깊이우선탐색과 너비우선탐색은 내가 알고리즘을 공부하기전에도 매우 자주 듣던 익숙한 단어이다. 그만큼 중요한 개념이니 꼼꼼하게 공부해두자. 그래프 순회 문제 상황을 그래프로 표현했으면, 그 데이터를 효과적으로 이용하기 위해서는 순회하는 과정이 꼭 필요하다. 그래프를 순회한다는 것은 정점과 간선을 순회한다는 것이므로, 이를 이뤄낼 수 있는 어떤 체계적인 절차가 필요하다. 대표적인 두가지 절차인 깊이우선탐색과 너비우선탐색을 배워보게 된다. 깊이우선탐색(DFS) 먼저 DFS에 대해서 알아보자. DFS 는 depth-first search 의 준말로 그래프를 순회하는 일반적인 기법이다. DFS순회로 가.. 2021. 11. 10.
테조스 관련 뉴스 보호되어 있는 글 입니다. 2021. 11. 9.
NFT란 무엇인가? https://twitter.com/punk6529/status/1451896453065023493 6529 on Twitter “1/ What is an NFT? Wait, what? Isn't this easy? I am not so sure. Let's take a look!” twitter.com 요즘 핫한 트렌드인 NFT에 대해서 너무도 명확하고 간결하게 설명해주는 글이다. 기록하기 위해서 남겨둔다. 1. 코인이 발행될 때 가지는 블록의 고유번호가 하나의 인증서가 된다. 2. 이미지가 NFT를 통해 거래되는 경우는 토큰에 URL(이미지가 들어있는)을 적어놓고 토큰을 거래하는 것이다. 3. 위와 같은 거래방식은 진품을 검증하는 과정이나 도용, 도난, 복제 등의 작업에서 현재의 방식과는 비교할 수 .. 2021. 11. 9.

티스토리툴바