7 .15

백준 단계별 풀이 
10. 기하: 직사각형과 삼각형
11. 시간복잡도
12. 브루트포스
13. 정렬

# int 범위.
4byte = 32bit
2^32 만큼 표현가능.
-2,147,483,648 ~ 2,147,483,647
약 21억
(자바 unsigned int 없음)
속 편히 long으로 선언하자.

# long 범위
8byte = 64bit
2^64 만큼 표현 가능
-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
약 9해


# big(O) 표기법
https://ko.wikipedia.org/wiki/점근_표기법


# nextLine() 에러
nextInt() 후 개행문자(enter)가 버퍼에 남아있음.
그 다음 어떤 변수 값을 nextLine()으로 받아온다면.
그 전에 그냥 nextLine()을 하나 넣어서 비워준다.


# 버블 정렬, Bubble Sort
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다

for(int i = 0; i < n - 1; i++){
	for(int j = 0; j < n - i;; j++{
    	if(arr[j] > arr[j+1]){
        	swap(arr, j, j+1);
        }
    }
}

장점
 - 추가적 메모리 소비가 작다. (제자리 정렬)
 - 구현이 매우 쉽다.
 - 안정정렬이 가능하다.
단점
 - 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.
 
시간복잡도 O(n^2).
그러나 각 라운드에서 교환이 일어나지 않는다면
정렬된 배열이라는 뜻이므로 탈출 시키면 O(n).


# 선택 정렬, Selection Sort
현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘.
비교정렬. 제자리 정렬. 불안정 정렬.

for(int i=0;i<n-1;i++){
	int min_index = i;
    for(int j = i + 1; j < size; j++){
    	if(a[j] < a[min_index]){
        	min_index = j;
    }
    
    swap(a, min_index, i);
}

장점
 - 추가적인 메모리 소비가 적다.

단점
 - 시간복잡도가 O(n^2)이다.
 - 안정 정렬이 아니다. (같은 수가 있을 때 명확하지 않다.)