알고리즘 썸네일형 리스트형 [알고리즘] 플로이드-워셜 - 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-₂ 더보기 [프로그래머스-level2] 게임 맵 최단거리 - javascript https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 최단거리를 구하는 거니 BFS 알고리즘을 사용해야 한다. 알고리즘 이해만 있다면 수월하게 풀 수 있는 난이도 문제. function solution(maps) { let answer = 1; let visited = maps //탐색을 마친 노드들 let needVisit = []; //탐색해야할 노드들 const n = maps.length; //세로 const m = maps[0].le.. 더보기 [javascript] BFS 📶 그래프 탐색 어떤것들이 연속해서 이어질 때, 모두 확인하는 방법 이다. Graph : Vertex (정점) + Edge (이어지는 것) - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex 를 Queue 에 저장 - Queue 의 가장 먼저 것 뽑아서 반복 ⏱️ 시간복잡도 알고리즘이 얼마나 오래 걸리는지 / 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 나타낸다. BFS : O(V+E) BFS 의 기본원리 - 방문여부 확인 (재방문 금지) - Queue: BFS 실행 최단거리는 BFS(너비우선탐색) 로 푸는게 좋다. 탐색 스택, 방문 배열 생성 탐색을 시작하는 정점을 탐색스택에 쌓는다 탐색스택이 없어질때까지 아래 반복 - 스택 최상단에 있는 것을 없애고, 이를 탐색 - 탐색 시에 방문했는지 .. 더보기 [LeetCode][java] #1 Two Sum https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one soluti.. 더보기 [1260][java][백준]DFS와BFS 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 풀이 테스트 케이스 대로 숫자를 입력받으면 어떤 그래프가 나오는지 보겠습니다. 테스트 케이스 상으로는 노드 1 부터 시작하게 됩니다. DFS: 1 - 2 - 4 - 3 BFS: 1 - 2 - 3 - 4 * 간선들의 연결이 되어 있는지 혹은 되지 않았는 것을 판단하는 것이 인접행렬을 이용하거나, 혹은 인접리스트를 이용하는 것이 좋습니다. 1) 인접 행렬 1번 꼭지점이 n번 꼭지점과 연결이 되어 있으면 1로 처리, 연결이 되어있지 않은 선은 0으로 처리 단점> 꼭지점의 갯수(Vertex)가 적을 때만 가능하다는 점. 갯수가 많아질수록 탐색 시간이 오래 걸림 2) 인접리스트 자신의 노드에서 갈 수 있는 노드를 가지고 있다고 생각하면 쉽습니.. 더보기 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 다음
