Algorithm65 [JAVA] 너비 우선 탐색 (BFS) 너비 우선 탐색은 시작 정점에 인접한 정점들을 모두 방문한 뒤에 이 정점들에 인접한 방문하지 않은 정점들을 모두 방문한다. 이 과정을 반복해 정점들을 시작 정점까지의 최단 경로의 길이 순서대로 방문한다. 만약 탐색이 종료된 후에 아직 방문하지 않은 정점들이 남아 있다면 그 정점들 중 한 정점에서 너비 우선 탐색을 시작한다. 너비 우선 탐색 알고리즘은 깊이 우선 탐색과 달리 재귀를 사용하여 작성할 수 없는 유형이다. 대신 너비 우선 탐색은 큐를 사용하여 쉽게 작성할 수 있다. 시간복잡도 - 인접 리스트: O(V+E) - 인접 행렬: O(V^2) 알고리즘 알고리즘 BFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 BFS(v.. 2021. 12. 14. [JAVA] 깊이 우선 탐색 (DFS) 깊이 우선 탐색은 한 그래프의 정점들을 유용한 순서로 방문하는 한 방법이다 주어진 그래프의 한 정점에서 탐색을 시작하여 그 정점을 방문했다고 표시하고, 그 정점에 인접한 정점들 중 방문 안한 정점을 임의로 선택하여 방문한다 선택된 정점에 대해 같은 탐색과정을 반복한다. 더 이상 방문하지않은 인접한 정점이 없으면 바로 전에 방문했던 정점으로 돌아간다. 탐색을 반복하다가 시작 정점으로 돌아간 후 그 시작 정점에 인접한 정점들 중 방문하지 않은 정점이 없으면 종료한다. 시간복잡도 - 인접 행렬: O(V^2) - 인접 리스트: O(V+E) 알고리즘 알고리즘 DFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다. 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 DFS(v)를 호출.. 2021. 12. 12. [JAVA] 삽입 정렬(Insertion Sort) 삽입 정렬은 배열을 정렬된 부분과 정렬이 안 된 부분으로 나눈다. i 번째를 정렬하기 전에 A[0 .. i - 1] 이 정렬되어 있다는 사실을 이용한다. i 번째 반복에서 정렬이 안 된 부분의 첫 번째 요소 A[i]를 정렬된 부분 A[0 .. i - 1]에 삽입할 위치를 찾은 후 A[i]를 그 위치에 삽입시켜 A[0 .. i]를 정렬시킨다. 시간복잡도 O(N^2) 알고리즘 InsertionSort(A[0 .. n-1]) for (i = 1; i = 0 and A[j] > insertElement) { A[j+1] = A[j] j = j - 1 } A[j+1] = insertElement } JAVA public.. 2021. 12. 7. [JAVA] 선택 정렬(Selection Sort) 선택 정렬은 이해하기 쉽지만 빠른 알고리즘은 아니다. 먼저 전체 배열에서 가장 작은 요소를 찾고 그 요소를 배열의 첫 번째 요소와 교환한다. 다음으로 배열 A의 두 번째 요소부터 마지막 요소까지 확인하여 가장 작은 요소를 찾은 후 그 요소를 두 번째 요소와 교환한다. 이 과정을 배열 전체가 정렬될 때까지 (n - 1)번 반복한다. 시간복잡도 O(N^2) 알고리즘 SelectionSort(A[0 .. n-1]) for (i = 0; i < n - 1; i++) { // 배열의 가장 작은 요소 찾기 min = i for (j = i; j < n; j++) if (A[j] < A[min]) min = j A[i]와 A[min] 교환 } JAVA public class SelectionSort { public .. 2021. 12. 6. [JAVA] 이진 탐색 (Binary Search) 크기가 n인 오름차순으로 정렬된 배열 A에 대한 탐색 1. x가 배열의 중간 요소와 같으면 찾았으니 끝낸다. 2. x가 배열의 중간 요소보다 작으면 앞쪽에 위치한 배열 반쪽에서 같은 방법으로 x를 찾는다. 3. x가 배열의 중간 요소보다 크면 뒤쪽에 위치한 배열 반쪽에서 같은 방법으로 x를 찾는다. 시간복잡도 O(logN) 알고리즘 BinarySearch(A[], first, last, x) if (first > last) return -1 else { mid = (first + last) / 2 if (x = A[mid]) return mid else if (x < A[mid]) return BinarySearch(A, first, mid - 1, x) else return BinarySearch(A,.. 2021. 12. 6. [JAVA] 자연수 n의 계승(factorial) 계산 자연수 n의 계승(factorial) 계산은 재귀 알고리즘으로 작성할 수 있다. 시간복잡도 O(N) 알고리즘 F(n) if (n = 0) return 1 else return F(n-1) * n JAVA public class ComputeFactorial { public static void main(String[] args) { int answer; int n = 10; answer = factorial(n); System.out.println(n + "의 계승 = " + answer); } public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } } 2021. 12. 6. 이전 1 2 3 4 ··· 11 다음