본문 바로가기

Algorithm14

깊이 우선 탐색 DFS 알고리즘 - 그래프 탐색 깊이 우선 탐색(DFS)으로 그래프를 탐색해보자. 그래프 탐색 하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다. 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다. 깊이 우선 탐색 DFS DFS는 탐색에서 깊은 것을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색 (BFS)는 큐(queue)가 사용되지만, 깊이 우선 탐색 (DFS)는 스택(stack)이 사용된다. 사실 컴퓨터는 함수 호출을 스택의 원리를 사용하기 때문에, 재귀를 사용하면 DFS를 구현할 수 있다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 모든 경우의 수를 보기 좋다! BFS보다는 속도가 느리다. 어떤 노드를 방문했는지 검사하.. 2021. 9. 11.
다익스트라 Dijkstra 알고리즘 정리할 예정 출처 : https://blog.naver.com/ndb796/221234424646 2021. 9. 9.
플로이드 와샬 Floyd Warshall 알고리즘 다이스트라(Dijkstra) : 하나의 점에서 출발했을 때 다른 모든 정점으로의 최단 경로(최소비용)를 구하는 알고리즘. 플로이드 와샬 : 모든 정점에서 모든 정점으로의 최단 경로(최소비용)를 구하고 싶을 때 사용한다. 거쳐가는 정점을 기준으로 최단 거리를 구하는 것 문제를 직접 풀어보며 알아보자. N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때, 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하라. ✔️ 입력 - n : 도시의 수 (N 정점 5 일 때 최소비용을 고려하면 자동으로 정점 3을 거치게 된다는 것이다. 이를 javascript 코드로 구현하면 다음과 같다. function solution(n, edges) { let answer =.. 2021. 9. 9.
프로그래머스 | Level3. 징검다리 건너기 (이분탐색) ✅ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 📌 접근 방법 이분탐색 stones 배열에 있는 원소들의 값은 1이상 200,000,000 이하의 자연수다. 따라서 니니즈 친구들이 최대 200,000,000명이 건널 수 있다. 정답은 1~200,000,000 사이에 존재 하므로, 이분탐색으로 1~200,000,000 사이를 탐색하며 정답이 되는지 확인한다. 아래 코드에서 cntNum 함수는 현재 mid값이 정답이 될 수 있는지 확인하는 함수다. 동작을 설명하자면, stones에 저장되어있는 값에서 mid.. 2021. 8. 27.

티스토리툴바