자바/알고리즘9

• [Java] 플로이드 워셜 (Floyd-Warshall) 알고리즘 [미완] 플로이드 워셜 1. 음수가중치가 있어도 된다. 하지만 음수 사이클이 존재하면 안된다. 2. 다익스트라 알고리즘은 "어떤하나의 정점"에서 부터 다른 모든 정점까지의 최소비용을 구하는 알고리즘이지만 플로이드 워셜은 "다른모든정점"에서 부터 "다른 모든정점"까지의 최소비용을 구할 수 있다. 3. 인접 행렬을 사용한다. (모든 정점에서 부터 다른 모든정점까지의 최소비용을 저장한다) 4. 시간복잡도는 O(v^3)이다. v는 정점 "다른모든정점"에서 부터 "다른 모든정점"까지의 최소비용 정보가 필요할때 사용하자. 플로이드 워셜 코드 + 예제 (백준 11404) public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader.. 자바/알고리즘 2023. 1. 10.

• 

  [Java] 벨만-포드 알고리즘 (Bellman-Ford) [미완] 그래프 최단거리를 구하는 알고리즘 1. 다익스트라 2. 벨만 포드 3. 플로이드 와샬 벨만 포드 알고리즘은 다익스트라 알고리즘처럼 그래프에서 한 노드에서 다른 모든 노드까지 가는 최소비용을 구할 수 있는 알고리즘이다. 다익스트라와의 차이점은 음수 가중치가 존재하는 경우에도 적용 할 수 있다. 벨만 포드 알고리즘의 시간복잡도는 O(VE)이다. (V: 정점, E: 간선) 다익스트라에서 시간복잡도는 O(VlogE)이므로 다익스트라가 더 빠르다. 다익스트라 알고리즘의 한계 다익스트라 알고리즘은 그리디알고리즘 + 다이나믹 프로그래밍이 합쳐진 알고리즘이다. 그리디 알고리즘 한계점 때문에 다익트스라 알고리즘은 음수 가중치를 가질 수 없다. 위 그림에서 1번 -> 3번 이동할때 최소비용을 구하게하면 다익스트라는 1->.. 자바/알고리즘 2023. 1. 8.

• 

  [Java] 다익스트라 알고리즘(Dijkstra Algorithm) + 예제 다익스트라 알고리즘 V = vertext(정점) , E = edge(간선) , adjNode = adjacentNode(인접노드) - 최단경로를 구하는 알고리즘 - 하나의 정점을 기준으로 다른 정점까지 가는 최단거리를 구한다. (출발지에서 다른 정점까지의 최단거리들을 구한다) - 음수 가중치가 없어야한다 - 인접 행렬로 표현된 그래프로 다익스트라 알고리즘을 구현시 시간 복잡도 O(V^2) - 우선순위 큐+리스트를 사용해서 다익스트라 알고리즘 구현시 시간복잡도 ( ElogV) 까지 낮출수 있다고 한다. - 탐욕법(그리디 알고리즘) 과 동적 계획법(다이나믹 프로그래밍)을 사용한다. -> 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 (그리디 알고리즘) -> 해당 노드로부터 갈 수 있는 노드들의.. 자바/알고리즘 2023. 1. 3.

• 

  [Java] DFS, BFS DFS(깊이 우선 탐색, Depth-First Search) 루트노드(혹은 다른 임의의 노드)에서 다음 분기(Branch)로 넘어가기 전에, 해당 분기(Branch)를 모두 탐색 하는 방법 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다. 특징 1. 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택으로 구현) ->조합에서 뽑고, 재귀적으로 호출하고, 뽑은거 취소하는것처럼 , 자기 자신을 호출함으로서 해당 수를 뽑은 경우의 모든경우를 탐색한다. 2.그래프탐색인 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. ( 검사하지않을경우 무한루프에 빠질수 있다.) ex) visited[index] = true , if(!visited[index]) -> 일반 조합에서 중복뽑기.. 자바/알고리즘 2022. 12. 20.

• 

  [Java] 그리디 알고리즘 (Greedy Algorithm) , 탐욕 알고리즘 그리디 알고리즘 Greedy(탐욕) 알고리즘은 매 번의 선택에서 가장 좋아보이는 선택을 하여 적절한 답을 찾아간다 예를 들어 다음과 같이 서울에서 부산을 가는 경로가 있다고 해보자. 서울-대전을 가는 경로중 가장 빠른 경로인 80분 걸리는 경로를 선택하고 대전-부산을 가는 경로중 가장 빠른 150분 걸리는 경로를 선택하여 총 230분이 걸리는 경로가 가장 빠른 경로일것이다. 이렇게 각 단계별로 최선의 선택지를 선택하는것이 그리디 알고리즘이다. 하지만 그리디 알고리즘은 항상 최적의 해를 도출해내는것이 아니다. 조건이 필요하다. 아래의 예시를 보자. 똑같이 부산을 목표로 가장 짧은 소요시간을 구해보자. 서울에서 원주로 가는 경로가 생긴 예시이다. 서울-대전 , 서울-원주를 보니 가장 적은 소요시간인 80분을.. 자바/알고리즘 2022. 12. 20.

• 

  [Java] 동적프로그래밍 , Dynamic Programming 동적프로그래밍 DP, 동적프로그래밍은 하나의 큰 문제를 여러개의 작은 문제로 나눠서 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는것으로 특정한 알고리즘이 아닌 하나의 문제해결법이라고 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 , 작은 문제의 답을 저장하고 저장한 답을 이용하여 점점 큰 문제를 해결하면서 저장 한다. 그렇게 원하는 값까지 도달한다. (기억하며 풀기라고 불리기도 한다.) DP를 쓰는이유 일반적인 재귀방식 또한 DP와 유사하다. 하지만 일반적인 재귀는 똑같은 작은 문제들을 여러번 계산하게 되서 비효율적이라는것이다. 예를 들어 피보나치 수열을 구하는 재귀의 동작방식을 살펴보자. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 처럼 진행되는 피보나치를 .. 자바/알고리즘 2022. 12. 14.

• [Java] 이분탐색 ,이진탐색 굉장히 효율적인 알고리즘으로, 이 알고리즘을 수행하기 위해서는 기본적으로 정렬이 되어있어야한다. 정렬된 자료구조 안에서 특정 값을 찾을때 절반씩 나누어 값을 찾는다는 것이 핵심적인 아이디어이다. 이분탐색은 탐색을 진행할 때마다 탐색 범위를 반으로 줄인다. 분할정복 알고리즘과 유사한데 이분탐색은 분할 정복 알고리즘의 한 예이다. 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다. 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이진 탐색이다. 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 .. 자바/알고리즘 2022. 12. 7.

• 

  [Java] 재귀 [미완] 자신을 정의할 때 자기 자신을 재 참조하는 방법을 재귀라고 한다. 이런식으로 func()라는 메소드를 정의할때 func 메소드안에 func을 호출하고 그 호출 한 func 안에 func을 참조하는, 이러한 방법이 재귀이다. 이렇게 함수안에 함수를 재 호출 하다보니 몇가지 고려해야할게 있다. 1. 재귀호출이 너무 반복적으로 많이되면 , 즉 재귀가 깊어지면 Stack OverFlow라는 에러가 발생한다. + 많이 호출되는 만큼 메모리에 스택되기 때문에 메모리를 엄청 차지한다. + 호출된 함수를 닫으면서 스택된 메모리에서 pop을 하기 때문에 수행시간도 느려진다. 결국 재귀호출을 하다가 메모리가 부족해지는 것과 성능이 저하되는것이 일상이기 때문에 이러한 이유로 재귀호출은 평상시에 알고리즘 자체가 재귀로 하면 .. 자바/알고리즘 2022. 12. 5.

• 

  순열,중복순열,조합,중복조합 정리 순열 (Permutation) -> 시간복잡도 O(n!) 서로 다른 N개에서 R개를 뽑아 정렬하는 경우의 수 서로다른 N개에서 R개를 뽑는것은 순열,중복순열,조합,중복조합 모두 같다. 하지만 순열은 "정렬"하는 경우의 수를 생각한다는것이 다른점이다. 두가지원소 1,2를 뽑아 [1,2]로 정렬하는 경우와1,2를 똑같이 뽑고 [2,1]로 정렬하는 경우가 서로다르다고 카운팅하는것이 순열이다. 이런 순열을 자바에서는 어떻게 구현할까 일단 순열은 기본적으로 재귀적인 방식으로 구현하는 완전탐색 방식이며 순열을 이용할때 주의사항 * 순열은 조합과 다르게 반복문 시작인덱스를 매개변수로 보내지않아도되고, 0으로 반복문을 시작하면 된다 (반복문 시작 인덱스가 0 이라는것은 ,순서가 다르게도 뽑겠다는뜻) * 조합과 다르게 .. 자바/알고리즘 2022. 10. 17.