20220831

한 번에 끝내는 Java/Spring 웹 개발 마스터

1) 가장 큰 수와 가장 작은 수 찾기 문제

package ch01;

//여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다.
//배열의 몇 번째에 있는지 순서를 찾는다.
//반복문을 한번만 사용하여 문제를 해결한다.
//수의 예 : [10, 55, 23, 2, 79, 101, 16, 82, 30, 45]
		
public class MinMaxProblem {

	public static void main(String[] args) {
		
		int[] numbers = {10, 55, 23, 2, 79, 101, 16, 82, 30, 45};
		
		int min = numbers[0]; //가장 큰 수 
		int max = numbers[0]; //가장 작은 수
		int minpos = 0; // 큰 수의 위치
		int maxpos = 0; // 작은 수의 위치
		
		for(int i=0; i<numbers.length; i++) {
			
			if(min > numbers[i]) {
				min = numbers[i];
				minpos = i+1;
			}
			
			if(max < numbers[i]) {
				max = numbers[i];
				maxpos = i+1;
			}
		}
		
		System.out.println("가장 큰 수는 " + max + "이고, 위치는 " + maxpos);
		System.out.println("가장 작은 수는 " + min + "이고, 위치는 " + minpos);
	}
}

2) 특정한 수를 찾는 문제

package ch02;

//여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법
//단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐
//수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음
//수의 예 : [12, 25, 31, 48, 54, 66, 70, 83, 95, 108]
//83의 위치를 찾아보세요
//88의 위치를 찾아보세요

public class BinarySearchProblem {

	public static void main(String[] args) {

		int[] numbers = { 12, 25, 31, 48, 54, 66, 70, 83, 95, 108 };
		
		int target = 83;
		
		int left = 0;
		int right = numbers.length - 1;
		int mid = (left + right) / 2;
		
		int temp = numbers[mid];
		boolean find = false;
		
		while( left <= right ) {
			
			if(target == temp) {
				find = true;
				break;
			} else if( target < temp) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
			
			mid = (left + right) / 2;
			temp = numbers[mid];
		}
		
		if(find == true) 
		{
			mid++;
			System.out.println("찾는 수는 " + mid + "번째 있습니다.");
		}
		else System.out.println("찾는 수가 없습니다.");
	}
}

3) 정렬 알고리즘

package ch03;

// 정렬 알고리즘
//Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념이다.(손안의 카드)
//두 번째 요소 부터 이전 요소들과 비교하면서 insert 될 위치를 찾아가며 정렬하는 알고리즘
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++) {
			temp = arr[i];
			j = i;

			while ((j > 0) && arr[j - 1] > temp) {
				arr[j] = arr[j - 1];
				j = j - 1;
			}
			arr[j] = temp;

			System.out.println("반복 -" + i);
			printSort(arr, count);
		}

	}

	public static void printSort(int value[], int count) {

		int i = 0;

		for (i = 0; i < count; i++) {
			System.out.print(value[i] + "\t");
		}
		
		System.out.println();
	}

	public static void main(String[] args) {

		int[] arr = { 80, 50, 70, 10, 60, 20, 40, 30 };

		insertionSort(arr, 8);
	}
}

• 알고리즘과 관련된 다양한 문제들을 풀어보는 중이다.
• 대학교에서 알고리즘 수업을 들은 경험이 있어서, 이러한 부분은 이해하는데 크게 어렵지 않았던것 같다.