알고리즘5 [알고리즘] 최단 경로 알고리즘 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘으로 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 알고리즘다익스트라 알고리즘하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 알고리즘첫 정점부터 각 노드 간 거리를 저장하는 배열을 생성 (자기 자신 0, 나머지는 Inf), 우선 순위 큐에 자기 자신까지의 Edge(start, 0)를 넣음우선 순위 큐에서 노드를 꺼낸다. 처음에는 첫 정점이 꺼내지게 되고 처음과 인접해있는 노드 간의 거리를 계산하면서, 가장 짧은 거리를 위에서 생성한 배열과 비교해서 더 짧다면 갱신갱신이 되었다면 해당 노드의 정보(”도착지”, “거리”)를 우선 순위 큐에 넣음우선 순위 큐가 빌 때 까지 위 순서를 반복public static HashM.. 2024. 12. 29. [알고리즘] 그래프 그래프실제 세계의 현상이나 사물을 정점 또는 노드와 간선으로 표현한 것그래프 관련 용어노드 : 위치 → 정점(Vertex)라고도 함간선 : 위치 간의 관계를 표시한 선으로 정점을 연결한 선(Edge)인접 정점 : 간선으로 직접 연결된 정점정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수경로 길이 : 경로를 구성하기 위해 사용된 간선의 수단순 경로 : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로A-B-C-D 와 같은 경우를 뜻함A-B-C-A-D 와 같은 경우에는 중복된 정점이 있으므로 단순 경로가 X사이클 : 단순 경.. 2024. 12. 29. [알고리즘] 이진 탐색 (Binary Search) 이진 탐색(이분 탐색)탐색 범위를 계속하여 반으로 나누어가며 범위를 좁혀 값을 찾는 방식찾으려는 값이 리스트의 중간보다 크면 우측 리스트에서 재탐색작다면 좌측 리스트에서 탐색을 반복.따라서 이진 탐색은 리스트가 정렬되어있는 상태에서 탐색이 가능하다.public static boolean binarySearch(ArrayList dataList, Integer searchItem) { if (dataList.size() == 1 && searchItem == dataList.getFirst()) { return true; } if (dataList.size() == 1 && searchItem != dataList.getFirst()) { return false; } if (dataList.isEmpt.. 2024. 12. 29. [알고리즘] 정렬 버블 정렬두 인접한 데이터를 비교해서 앞의 데이터가 뒤의 데이터보다 크면 자리를 바꿈.public static ArrayList bubbleSort(ArrayList dataList) { for (int i = 0; i dataList.get(j + 1)) { Collections.swap(dataList, j, j + 1); swap = true; } } if (!swap) { break; } } return dataList;}시간 복잡도 : O(n^2), 완전정렬상태 : O(n)선택 정렬주어진 데이터 중에서 최소값을 찾은 후 해당 데이터를 맨 앞의 데이터.. 2024. 12. 29. [알고리즘] 동적 계획법, 분할정복 동적 계획법 (DP)입력 크기가 작은 부분 문제들을 해결하고, 해당 부분 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘이다.상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과를 이용해서 상위 문제를 풀어나감Memoization 기법을 사용해서 이전에 계산한 값을 저장, 재활용해서 실행 속도를 빠르게 한다.public static int fibonacci(int n) { Integer[] memoization = new Integer[n + 1]; memoization[0] = 0; memoization[1] = 1; for (int i = 2; i 분할 정복문제를 나눌 수 없을 때 까지 나누어서 각각을 풀고 .. 2024. 12. 28. 이전 1 다음