운동하는 개발자

3번 정렬 알고리즘 평균 수행 시간이 O(n^2)인 알고리즘 ● 버블 정렬, 삽입 정렬, 선택 정렬 ● 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬 됨 Insertion Sort (삽입정렬)구현 ● Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념이다. ● 두 번째 요소 부터 이전 요소들과 비교하면서 insert될 위치를 찾아가며 정렬하는 알고리즘 package ch03; public class InsertionSort { public static void insertionSort(int[] arr, int count) { int i = 0, j = 0; int temp = 0; for(i = 1; i < count; i++..

문제 정의 ● 여러 개의 수가 정렬된 수서로 있을 때 특정한 수를 찾는 방법 ● 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐 ● 수가 정렬된 상태에서는 이진 탐색을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음 ● 수의 예 : [12, 25. 31, 48, 54, 66, 70, 83, 95, 108] ● 83의 위치 찾기 ● 88의 위치 찾기 문제 해결방법 ● 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐 수 있다. ● 한번 비교 할때 마다 1/2씩 범위가 좁혀진다. 배열애 포함된 숫자를 입력했을 때의 코드..

오늘은 그래프 탐색에 속하는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)에 대해서 공부하였다. 우선 그래프를 만드는 방법을 matrix(매트릭스)로 표현을 해보겠다. package ch04.graph; public class UndirectedGraph{ private int count; //노드 수 private int[][] vertexMatrix; // matrix로 그래프 표시 public UndirectedGraph(int count){ this.count = count; vertexMatrix = new int[count][count]; } public void addEdges(int from, int to, int weight){ vertexMatrix[from][to] = weigh..

나열된 수에서 최솟값과 최대값 구하기 문제정의 ● 여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다. ● 배열의 몇 번째에 있는지 순서를 찾는다. ● 반복문을 한번만 사용하여 문제를 해결한다. ● 수의 예로는 [10, 55, 23, 2, 79, 101, 16, 82, 30, 45]이다. 문제해결 방법 ● 배열에 있는 수 중 맨 처음에 있는 값을 max와 min으로 가정하고 배열의 마지막 숫자까지 비교하면서 더 큰 수나 더 작은 수가 나올때 max와 min의 값을 바꾸도록 한다. ● 그 때의 위치를 변수에 저장한다. 문제풀이 코드 package ch01; public class MinMaxProblem { public static void main(String[] args) { ..