자료구조+알고리즘/알고리즘 썸네일형 리스트형 [알고리즘] 플로이드-워셜 - javascript ﹅ 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 모든 노드에서 다른 모든 노드까지 가는 최소비용 start → mid → end 표[2차원 배열]를 만들어 중간 경유지에 따라 값을 계속 갱신시킨다. 시간복잡도 : O(V^3) 다익스트라 : 한 노드 → 다른 모든 노드, O(ElgV) 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 달리 "모든 노드 쌍" 에 대해 최단거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 💡 그래프 알고리즘에 대해 읽어볼 좋은 글 https://yozm.wishket.com/magazine/detail/2411/ ﹆ 작동 원리 1 → 4 로 바로 가는 방법은 존재하지 않지만, 중간 노드 mid 를 3으로 둔다면, 1 → .. 더보기 DP : Dynamic Programming (동적 계획법) #️⃣ DP : Dynamic Programming 이전의 값을 재활용하는 알고리즘 이전의 값을 활용해서 시간복잡도를 줄일 수 있다. 예시) - 1~10 숫자 중 각각 이전값들을 합한 값 구하기 문제 dp 에서는 점화식 을 구하는게 핵심이다 ! 이전값을 어떻게 활용하는지를 구하는 알고리즘 이기 때문에 예를들어 점화식 : An = An-₁ + An-₂ 더보기 [javascript] BFS 📶 그래프 탐색 어떤것들이 연속해서 이어질 때, 모두 확인하는 방법 이다. Graph : Vertex (정점) + Edge (이어지는 것) - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex 를 Queue 에 저장 - Queue 의 가장 먼저 것 뽑아서 반복 ⏱️ 시간복잡도 알고리즘이 얼마나 오래 걸리는지 / 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 나타낸다. BFS : O(V+E) BFS 의 기본원리 - 방문여부 확인 (재방문 금지) - Queue: BFS 실행 최단거리는 BFS(너비우선탐색) 로 푸는게 좋다. 탐색 스택, 방문 배열 생성 탐색을 시작하는 정점을 탐색스택에 쌓는다 탐색스택이 없어질때까지 아래 반복 - 스택 최상단에 있는 것을 없애고, 이를 탐색 - 탐색 시에 방문했는지 .. 더보기 DFS 와 BFS 개념정리 그래프를 탐색하기 위한 대표적인 알고리즘 - DFS , BFS (이해하려면 스택,큐,재귀함수를 알아야한다) 🁢 탐색 Search 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 🁢 자료구조 Data Structure 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 🁢 스택(Stack) 박스 쌓기에 비유 선입후출(First In Last Out) ▒ java ▒ * 자바에서 스택의 최상단 원소를 출력할때 peek() 메서드사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java util.*; public calss Main{ p.. 더보기 이전 1 다음
