본문 바로가기

알고리즘4

5.최단거리 구하기 문제 문제풀이 - 모든 노드 중 연결된 최단거리를 가진 노드를 찾아서 - 노드 v에 인접한 노드 w에 대해 다음 조건이 성립하면 w에 대한 최단 거리를 업데이트 한다. (즉, 원래 w로 가던 거리보다 v를 거쳐가는 거리가 더 가까우면 w로 가는 거리는 v를 거쳐가는 것으로 최단 거리를 수정) Yw = Yv + Cvw if Yv +Cvw < Yw - MyGraph.java class MyGraph{ private int count; private int[][] vertexMatrix; private int[] distance; private boolean[] visited; private static int UNLIMIT = 999999999; public MyGraph(int count) { this.coun.. 2022. 6. 10.
3.정렬 알고리즘 평균 수행 시간이 O(n^2)인 알고리즘 - 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) - 각 요소가 다른 요소와 평균 한 번 이상씩 비교를 하여 정렬됨 Insertion Sort 구현해보기 - Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념이다. - 두 번째 요소부터 이전 요소들과 비교하면서 insert될 위치를 찾아가며 정렬하는 알고리즘 - InsertionSort.java public class InsertionSort { public static void insertionSort(int[] arr, int count) { int i = 0, j =0; int.. 2022. 6. 9.
2.정렬된 수에서 하나의 수의 위치 찾기 문제정의 - 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법 - 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐 - 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반을 감소될 수 있으므로 O(longN)의 수행으로 원하는 수를 찾을 수 있음 - 수의 예 : [12,25,31,48,54,66,70,83,95,108] - 83의 위치를 찾아보세요 - 88의 위치를 찾아보세요 해결방법 - 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐 수 있다. - 한번 비교할 때마다 1/2씩 범위가 좁혀진다. 코딩 - BinarySe.. 2022. 6. 9.
1.나열된 수에서 최솟값과 최댓값 구하기 문제정의 - 여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다. - 배열의 몇 번째에 있는지 순서를 찾는다. - 반복문을 한 번만 사용하여 문제를 해결한다. - 수의 예: [10,55,23,2,79,101,16,82,30,45] 해결하기 - 배열에 있는 수 중 맨 처음에 있는 값을 max와 min으로 가정하고, 배열의 마지막 숫자까지 비교하면서 더 큰 수나 더 작은 수가 나올때 max와 min의 값을 바꾸도록 한다. - 그때의 위치를 변수에 저장한다. 코딩 - MinMaxProblems.java public class MinMaxProblem { public static void main(String[] args) { int arr[] = {10,55,23,2,79,101,16.. 2022. 6. 9.

티스토리툴바