Alogorithm6 [JAVA] 카데인 알고리즘(Kadane's Algorithm) 카데인 알고리즘이란?카데인 알고리즘은 연속 부분 배열의 최대 합을 구하는 효율적인 방법으로, 컴퓨터 과학과 알고리즘 문제 해결에서 자주 사용됩니다. 이 알고리즘은 O(n) 시간 복잡도를 가지며, 동적 계획법(Dynamic Programming) 접근법을 사용합니다.카데인 알고리즘의 원리카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색합니다. 알고리즘은 두 가지 값을 유지합니다.현재까지의 최대 합 (max_so_far) : 지금까지 발견한 최대 부분 배열의 합현재 위치에서 끝나는 최대 합 (max_ending_here) : 현재 위치에서 끝나는 부분 배열 중 최대 합알고리즘 단계1. max_so_far와 max_ending_here를 배열의 첫 번째 요소로 초기화합.. 2024. 8. 14. [JAVA] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘다익스트라 알고리즘이란BFS와 DP를 활용한 최단경로 탐색 알고리즘이다다이나믹프로그래밍인 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다.다익스트라 알고리즘의 특징그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단경로를 알려준다.그래프의 간선(Edge)마다 가중치가 존재할 때 사용한다. 이 점이 BFS를 활용한 최단 경로 구하기와 다른 점이다.간선의 음의 가중치는 존재하지 않는다. 음의 가중치가 하나라도 있으면 다익스트라를 사용할 수 없다.음의 가중치가 존재하지 않기 때문에 현실세계에 사용하기 적합한 알고리즘이다.(ex. GPS, 네비게이션)출발노드, 도착노드로 구성된 이차원 배열 활용 구현.. 2024. 7. 2. [JAVA] 동적 계획법(Dynamic Programming) Dynamic Programming(DP, 동적 계획법)1. 개요DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경쓰지 않아도 된다.큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다.2. DP를 쓰는 이유일반적인 재귀(Native Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있.. 2024. 5. 31. [JAVA] 깊이 우선 탐색 (DFS, Depth-First Search) 깊이 우선 탐색 (DFS, Depth-First Search)깊이 우선 탐색이란루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완번하게 탐색하는 방법미로를 탐색할 때 한 방향으로 갈 수 있을 떄까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.즉, 넓게(wide) 탐색하기전에 깊게(deep) 탐색하는 것이다.사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 조금 더 간단하다.단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.깊이 우선 탐색(DFS)의 특징자기 자신을.. 2024. 5. 16. 이전 1 2 다음
