728x90 알고리즘3 BFS 알고리즘이란? 너비 우선 탐색(BFS, Breadth-First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 이는 **그래프 탐색** (하나의 정점으로 시작하여 모든 정점을 한번씩 방문)에 속한다. BFS는 두 노드 사이의 **최단 경로** 및 **임의의 경로** 를 찾을때 사용하며 자료 구조 **큐(Queue)** 를 이용해 탐색을 한다. 유사 알고리즘 : Prim, Dijkstra 너비 우선 탐색(BFS) 예제 - Python 해당 예제는 같은 숫자끼리 땅따먹기로 인접한 같은 숫자끼리의 넓이를 구하는 예제이다. 바로 구현해보기 위한 예제이므로 코드가 지저분하다.. 구현 방식은 방문 여부, 큐(Queue)를 활용하였다. def solution(v): result = [0, 0, 0] .. 2021. 7. 8. 알고리즘 왜 필요할까? #알고리즘 #코딩 #노마드 코더 본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다. 알고리즘 왜 필요할까? 처음 코딩을 공부할때에는 데이터 구조와 알고리즘을 공부할 필요가 없다. 왜 그럴까? 이제 막 시작한 초보 개발자는 니즈가 없기 때문이다. 앱을 동작하는 것이 첫번째 목적이기 때문이다. 그럼 언제 필요할까? 소스코드에 버그는 없으나 앱이 느릴때 ( = 코드 최적화를 어디서부터 해야할지 모를때 ) 관리가 편하고, 다른사람들과 일하기 편하게 코드를 작성할때 초보 개발자가 첫번째 목적을 달성한 뒤에 그다음 단계가 바로 어떻게 더 빠르고 효율적이게 구현할 것인가 이다. 데이터 구조 vs 알고리즘 데이터 구조 프론트엔드 : 모두 데이터를 필요. json 데이터를 아름답게 표현 백엔드.. 2021. 7. 8. Dijkstra 알고리즘 목적 다익스트라 알고리즘을 이해하기 다익스트라 알고리즘을 Java로 구현하기 시작하는 말 티스토리 블로그로 이전하고 처음 포스팅하는 글입니다. 첫 게시글은 전 github.io 블로그에서 가장 클릭 수가 많았던 다익스트라 알고리즘을 옮기려고 한다. (검색어는 '다익스트라 2차원 배열') 다익스트라(dijkstra) 알고리즘 이란? 다익스트라 알고리즘은 최단경로를 탐색하는 알고리즘이다. 구현 방법으로 2차원 배열 또는 힙(Heap)을 이용하여 구현할 수 있으며 각각 O(N^2)와 O(ElogN) 시간복잡도를 가진다. 다익스트라 알고리즘은 음수 가중치를 가진 그래프에서는 사용할 수 없는 단점이 있는데 이때에는 벨만-포드 알고리즘을 사용해야 합니다. 원리 1. 모든 가중치를 무한으로 설정한다. 2. 방문하지 .. 2021. 6. 22. 이전 1 다음 728x90
