배열

알고리즘-시간 복잡도 : 빅-오(O) 표기법

• 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n(최고차 항)에 대한 항만을 표시
• 계수를 생략하여 표시

• 요소 수가 증가함에 따라 각기 다른 시간복잡도의 알고리즘은 아래와 같은 연산 수를 보인다.

• 시간 복잡도별 실제 실행 시간 비교

• N이
  • 13:N!
  • 20:2^N
  • 10000:N^2 가능
  • 100000~1000000:NlogN으로 잡아야됨.

# 대원칙: 의사코드에 정해진 문법/규칙은 없으며,
  본인이 쉽고 편하게 쓰고 알아볼 수 있을 정도면 된다. 


# 먼저 함수, 매개변수의 정의를 쓴다.
countSum : 1부터 n까지의 합을 계산
 - n: 임의의 양의 정수 n

# 함수
  중괄호? 
  function 키워드 ~ end function?
  
1. 중괄호 포함
countSum (n) {
	// 함수 내용
}

2. function 키워드 사용
function countSum (n)
	// 함수 내용
end function

3. 중괄호 생략
countSum(n)
    // 함수 내용
  
# 할당
  a <- 10
  b ← 5
  (그렇지만 a = 10 이렇게 써도 된다.)

# 같다
  a = b
  (그렇지만 a == b 이렇게 써도 된다.)
  
# return문은 남겨둠
# 변수의 타입은 보통 생략
# 세미콜론은 생략해도 되고 안해도 됨
# 배열의 인덱스: 0부터 시작할 때도 있고, 1부터 시작할 때도 있음
# * 연산자는 *로 써도 되고 그냥 일반 수학식(x)으로 써도 되고 생략해도 됨!

countSum : 1부터 n까지의 합을 계산
 - n: 임의의 양의 정수 n
 
countSum(n) {
	sum ← 0
	for(i ← 1; i <= n; i++){
		sum ← sum + 1
	}
	return sum
}


countSum2(n){
	sum ← n(n+1)/2
	return sum
}


countSum3(n){
	return n(n+1)/2
}

package test01;

public class Test3_빅오표기법 {
	public static void main(String[] args) {
		// 1. 입력의 개수 n개가 주어질 때 연산량의 개수를 센다.
		// 다음 코드의 연산의 개수는?
		int N = 10;
		for(int i=0; i<N; i++) {
			System.out.println(i);
		}
		//3N
		//시간 복잡도 : O(n)

		
		
		// 2. 최고차항(가장 증가속도가 빠른 항)만을 계수 없이 나타낸다.
		for(int i=0; i<N; i++) {
			int sum = 0;
			for(int j=0; j<N; j++) {
				sum += j + i;
			}
			System.out.println(sum);
		}
		//N^2+2N
		//시간 복잡도 : O(n^2)
		
		
		// 3. 빅오 표기법은 최악의 경우를 가정한다.
		//  - 최악의 경우란? 연산량이 가장 많은 경우, 시간이 가장 오래걸리는 경우
		//  - ex) 다음 배열에서 특정한 수를 찾는 알고리즘의 시간 복잡도는?
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		int target_num = 8;
		for(int i=0; i<arr.length; i++) {
			if (arr[i] == target_num)
				break;
		}
		
		//최선의 경우(가장 우호적인 경우) : 1,2->O(1) ->(오메가표시)(1)
		//평균적인 경우 : 5,6 ->O(n/2) ->O(n) -> (세타표시)(n)
		//최악의 경우 : 9, 10->O(n)
		
		
	}
}

배열

package test2;

public class test1 {
	public static void main(String[] args) {
		//1차원 배열 연습
		
		int[] nums = {1,2,3,4,5,6};
		
		//1. 정방향 순회-전통적 for문
		for(int i=0; i<nums.length; i++) {
			System.out.println(nums[i]);
		}
		
		//for each문
		for(int num:nums) {
			System.out.println(num);
		}
		
		//2. 역방향 순회-전통적 for문
		for (int i = nums.length-1; i >=0 ; i--) {
			System.out.println(nums[i]);
		}
		
		//인덱스 컨트롤
		//i는 정방향이지만 출력은 역방향
		int N=nums.length;
		for (int i = 0; i < N; i++) {
			System.out.println(nums[N-1-i]);
		}
		
	}
}

정렬

• 버블 정렬(O(n^2))
• 선택 정렬(O(n^2))
• 삽입 정렬(O(n^2))
• 카운팅 정렬(O(n+k))
• 병합 정렬(O(nlog(n))
• 퀵 정렬(O(n^2))

버블 정렬

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식(기본적으로 오름차순)

• 한 단계가 끝나면(1 pass) 가장 큰 원소가 마지막 자리로 정렬된다.(마지막 pass에서는 숫자 2개가 정렬)
• 배열의 크기가 n개->pass는 최대 n-1번

BubbleSort(A)
	A:주어진 배열
	n:A.length, 배열의 길이
	
	for(i=0; i<n-1; i++) // n-1번 반복
		for(j=0; j<n-2-i; j++) //각 패스에서 비교
			if(A[j]>A[j+1] then
				swap([A[j],A[j+1])

package test03;

import java.util.Arrays;

public class test2버블정렬 {
	public static void main(String[] args) {
		int[] arr= {5,4,3,2,1};
		int n=arr.length;
		
		System.out.println("시작 전: "+Arrays.toString(arr));
		for (int i = 0; i < n-1; i++) {
			for (int j = 0; j < n-1-i; j++) {
				if (arr[j]>arr[j+1]) {
					int temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
			System.out.printf("%d번째 패스 결과: %s\n", i+1, Arrays.toString(arr));
		}
		System.out.println("버블 정렬된 후: "+Arrays.toString(arr));
	}
}
//
시작 전: [5, 4, 3, 2, 1]
1번째 패스 결과: [4, 3, 2, 1, 5]
2번째 패스 결과: [3, 2, 1, 4, 5]
3번째 패스 결과: [2, 1, 3, 4, 5]
4번째 패스 결과: [1, 2, 3, 4, 5]
버블 정렬된 후: [1, 2, 3, 4, 5]