IT
-
[JAVA] 동적 계획법(Dynamic Programming)IT/Algorithm 2024. 5. 22. 10:28
Dynamic Programming(DP, 동적 계획법)1. 개요DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경쓰지 않아도 된다.큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다.2. DP를 쓰는 이유일반적인 재귀(Native Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있..
-
[JAVA] 다익스트라(Dijkstra) 알고리즘IT/Algorithm 2024. 5. 22. 10:23
다익스트라(Dijkstra) 알고리즘다익스트라 알고리즘이란BFS와 DP를 활용한 최단경로 탐색 알고리즘이다다이나믹프로그래밍인 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다.다익스트라 알고리즘의 특징그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단경로를 알려준다.그래프의 간선(Edge)마다 가중치가 존재할 때 사용한다. 이 점이 BFS를 활용한 최단 경로 구하기와 다른 점이다.간선의 음의 가중치는 존재하지 않는다. 음의 가중치가 하나라도 있으면 다익스트라를 사용할 수 없다.음의 가중치가 존재하지 않기 때문에 현실세계에 사용하기 적합한 알고리즘이다.(ex. GPS, 네비게이션)출발노드, 도착노드로 구성된 이차원 배열 활용 구현..
-
[JAVA] 깊이 우선 탐색 (DFS, Depth-First Search)IT/Algorithm 2024. 5. 16. 08:44
깊이 우선 탐색 (DFS, Depth-First Search)깊이 우선 탐색이란루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완번하게 탐색하는 방법미로를 탐색할 때 한 방향으로 갈 수 있을 떄까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.즉, 넓게(wide) 탐색하기전에 깊게(deep) 탐색하는 것이다.사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 조금 더 간단하다.단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.깊이 우선 탐색(DFS)의 특징자기 자신을..
-
[JAVA] 너비 우선 탐색 (BFS, Breadth-First Search)IT/Algorithm 2024. 5. 16. 08:39
너비 우선 탐색 (BFS, Breadth-First Search)너비 우선 탐색이란루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.사용하는 경우: 두 노드 사이의 최단경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는경우깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS..