ch8 알고리즘

02.이진탐색

Chapter8/8-02 · master · Youngju-Jang / Javacoursework · GitLab

 

• 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐
• 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음

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("찾는 수가 없습니다.");
	}
}

 

03. 정렬 알고리즘

Chapter8/8-03 · master · Youngju-Jang / Javacoursework · GitLab

평균 수행 시간이 O(n^2)인 알고리즘

• 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort)
• 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬 됨

Insertion Sort 구현해보기

• Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념이다.(손안의 카드)
• 두 번째 요소 부터 이전 요소들과 비교하면서 insert 될 위치를 찾아가며 정렬하는 알고리즘
• 코드 : 주소에

평균 수행 시간이 O(logN)인 알고리즘

• 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)
• 한번 수행될 때마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우
• 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요함
• 힙 정렬(Heap Sort): complete binary tree 
• heap: 배열많이씀, 0번인덱스는 안씀(빈칸. 나누기2 해야해서)
• min-heap insert :: parent위치 : 새로넣는 애의 인덱스의 1/2 >> parent가 더 크면 바꾸고 ~~ 반복
• insert & 재정렬하는 두개의 과정이 있음
• min or max (10)빼고나면(delete) >> 맨마지막 꺼(80)을 넣고 재정렬진행함

 

min-heap: 자기 child보다 자기가 무조건 작아야함

public class HeapSort {

	private int SIZE;
	private int heapArr[];
	
	public HeapSort()
	{
		SIZE = 0;
		heapArr = new int [50];
	}
	
	public void insertHeap(int input)
	{
		int i = ++SIZE;
		//while(( i != 1) && ( input > heapArr[i/2])){ //max heap
		while(( i != 1) && ( input < heapArr[i/2])){ //min heap
			heapArr[i] = heapArr[i/2];
			i = i/2;
		}
		heapArr[i] = input;
	}
	
	public int getHeapSize()
	{
		return SIZE;
	}
	
	public int deleteHeap()
	{
		int parent, child;
		int data, temp;
		data = heapArr[1]; 
		
		temp = heapArr[SIZE]; 
		SIZE -= 1; 
		parent =1; child = 2;
		
		while(child <= SIZE){
			//if((child < HEAP_SIZE) && (heapArr[child] < heapArr[child+1])){ //max heap
			if((child < SIZE) && (heapArr[child] > heapArr[child+1])){ //min heap
				child++;
			}
			//if(temp >= heapArr[child]) break; //max heap
			if(temp <= heapArr[child]) break;   //min heap
			heapArr[parent] = heapArr[child];
			parent = child;
			child *= 2;
		}
		
		heapArr[parent] = temp;
		return data;
	}
	
	public void printHeap(){
		//System.out.printf("\n Max Heap : ");
		System.out.printf("\n Min Heap : ");
		for(int i=1; i<=SIZE; i++)
			System.out.printf("[%d] ", heapArr[i]);
	}
	public static void main(String[] args) {
		HeapSort h = new HeapSort();
		h.insertHeap(80);
		h.insertHeap(50);
		h.insertHeap(70);
		h.insertHeap(10);
		h.insertHeap(60);
		h.insertHeap(20);
		
		h.printHeap();
	
		int n, data;
		n = h.getHeapSize();
		for(int i=1; i<=n; i++){    
			data = h.deleteHeap();  
			System.out.printf("\n 출력 : [%d]", data);
		}
	}
}

04. DFS(Depth - First Search)와 BFS(Breadth - First Search)