본문 바로가기

728x90

🖥 Computer Science/Algorithm16

[Algorithm] 너비우선탐색(BFS,Breadth-First-Search)란?(feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 트리를 탐색하는데 쓰이는 알고리즘인 너비우선탐색(BFS)에 대해서 알아보도록 하겠습니다. 바로 시작할게요~ BFS란? 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 큐를 사용해야만 레벨 순서대로 접근이 가능하다. - 위키 백과 - 쉽게 예제를 통해서 설명드릴게요! 아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다. 탐색하는 방법은 여러가지가 있겠지만 먼저 지구에 있는 나라를 왼쪽부터 어떤 도시들이 있는지 확인하고 넘어가는 방법은 DF.. 2021. 6. 27.

[Algorithm] 깊이 우선 탐색(DFS,Depth-First-Search)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 엄청 빈번하게 출제되고 알아두면 정말 유용한 DFS에 대해서 알아보도록 하겠습니다. 바로 시작할게요! DFS란? "깊이 우선 탐색은 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다." - 위키 백과 - 이게 뭔말이야....;;; 쉽게 예제를 통해서 설명드리겠습니다. 아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다. 어떤 사람은 "난 먼저 어떤 나라들이 있는지 부터 확인하고 그 나라 안에 있는.. 2021. 6. 5.

[Algorithm] 다익스트라(Dijkstra) 알고리즘이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 그래프 문제에서 아주 빈번하게 사용되는 다익스트라라는 알고리즘에 대해서 알아보겠습니다. 바로 시작할게요! 다익스트라란? 🤔 나무 위키에는 다음과 같이 정의되어있습니다. "음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다." 쉽게 말하면 한 정점에서 다른 정점으로 이동할 때 가장 빠른 길을 찾아주는 알고리즘이에요. 그래프 설명 다음과 같은 그래프가 있다고 가정하겠습니다. 시작 정점은 1로 목표 정점을 4로 두었을 때 가장 가까운 거리는 몇일까요? 1 - 5 - 4 로 가는 경우가 3 + 1 = 4로 가장 가까운 길이겠죠? 이렇게 간단히 보이는 경로는 눈으로 쉽게 찾을 수 있지만 복잡한 경로일수록 찾기가 어려워질 것입니다. 이.. 2021. 5. 22.

[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘이란? (feat.Swift) 안녕하세요 Foma🍍 입니다! 오늘은 그래프 문제에서 아주 빈번하게 사용되는 플로이드 와샬이라는 알고리즘에 대해서 알아보겠습니다. 바로 시작할게요! 플로이드 와샬이란? 🤔 위키 백과에는 다음과 같이 정의되어있습니다. "플로이드 와샬 알고리즘은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다." 쉽게 말하면 모든 최단 경로를 찾는 알고리즘이에요. 그래프 설명 아래와 같은 그래프가 있다고 가정할게요. (파란색 동그라미는 정점, 사이에 숫자는 거리입니다.) 만약 1번 정점에서 3번 정점으로 가려면 어떤 정점을 이용해야 가장 짧을까요? 정답을 알기 위해선 중간에 모든 정점을 거쳐서 간 다음 가장 짧은 거리를 구해야 할 것 입니다. 1번 -> 2번 -> 3번 3.. 2021. 5. 17.

이전 1 2 다음

728x90

티스토리툴바