개발야옹

🌼 Dynamic Programming (다이나믹 프로그래밍/동적 계획법)🌼 다이나믹프로그래밍메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.DP의 구현은 일반적으로 두 가지가 있다.상향식(Bottom Up)하향식(Top Down)다이나믹 프로그래밍은 동적 계획법이라고도 부른다.프로그래밍 분야에서의 Dynamic?자료구조에서 동적 할당(Dynamic Allocation)은 '프로그래밍 실행되는 도중 필요한 메모리할당 기법'이다.반면, Dynamic Programming의 Dynamic은 별다른 의미 없이 사용한다.🌼 다이나믹프로그래밍의 조건다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 ..

🌼 이전 내용다익스트라 알고리즘 이론 및 구현 코드플로이드 워셜 알고리즘 이론 및 구현 코드🌼 최단 경로 알고리즘 기초 문제 풀이📄 전보: 문제 설명어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다.하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.어느날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도..

🌼 Floyd-Warshall Algorithm (플로이드 워셜 알고리즘)🌼 플로이드 워셜 알고리즘모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다.다만, 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다플로이드 워셜은 2차원 테이블에 최단거리 정보를 계산한다.플로이드 워셜은 2차원 테이블에 최단거리 정보를 계산한다.플로이드 워셜 알고리즘은 DP 유형에 속한다.각 단계마다 특정한 노드 K를 거쳐가는 경로를 확인한다.a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 좋은지 검사점화식Dab = min(Dab, Dak + Dkb)?..

🌼 Dijkstra Algorithm(다익스트라 알고리즘) 최단경로 알고리즘🌼 최단 경로 알고리즘최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.다양한 문제 상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현 🌼 다익스트라 최단 경로 알고리즘 개요특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작현실세계의 도로는 음의 간선으로 표현되지 않음다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.매 상황에서 가장 비용이 적은 노드를 선택해 임..