본질의 중요성

Static library

• 실행 파일 안에 라이브러리가 들어가는 것

Dynamic library

• 실행 파일에 라이브러리를 가지고 있지 않고, 라이브러리를 공유하는 것
  => 프로그램이 실행할 때(메모리 공간에 올라올 때) 링크를 건다.
• 라이브러리를 언제든지 교체하여 실행할 수 있다.
• 라이브러리가 필요할 때 가상 메모리에 매핑 시키는 형태로 동작

Ref.

https://www.youtube.com/watch?v=JK6U91t7mgY&t=73s

분할 정복법 (Divide and Conquer)

아래 3가지 단계를 거쳐서 어떤 문제를 해결하는 기법

Merge Sort와 Quick Sort에서 사용하는 기법

• 분할(Divide) : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복(Conquer) : 각각의 작은 문제를 순환적으로 해결
• 합병(Merge): 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

Merge Sort

Step 1) Divide - 데이터가 저장된 배열을 절반으로 나눔

Step 2) Recursively sort - 각각을 순환적으로 정렬

Step 3) Merge - 정렬된 두 개의 배열을 합쳐 전체를 정렬

Step 3인 Merge 과정 자세히 보기 

- 정렬된 두 배열을 Merge하는 과정

- 새로운 추가 배열 필요

- i(첫번째 list에서 가장 작은 값), j(두번째 list에서 가장 작은 값), k(추가 list에서 가장 작은 값) 변수 필요

1. A[i]와 A[j]를 비교하여 작은 값을 추가 배열에 추가

2. 작은 값에 속한 인덱스 올림. i++ or j++ , k++

3. i or j가 해당 배열의 인덱스보다 크다면 다른 배열의 값은 그대로 추가배열에 추가 해주면 됨!

소스

// 재귀 함수이므로 매개변수 명시화 필요
public void mergeSort(int[] arr, int p, int r) {		
	if (p < r) {
		int q = (p+r) / 2;		// 1. p와 r의 중간 지점 계산
		mergeSort(arr, p, q);	// 2. 전반부 정렬
		mergeSort(arr, q+1, r);	// 3. 후반부 정렬
		merge(arr, p, q, r);	// 4. 합병
	}
}

/* Merge Business Logic - 정렬되어 있는 두 배열 arr[p...q]와 arr[q+1...r]을 합하여 
 * 정렬된 하나의 배열 arr[p...r]을 만듦. 
 * arr[p... q] arr[q+1...r] => 정렬되어 있는 두 배열 
 * arr[p.................r] => 정렬된 하나의 배열을 만드는 작업 : Merge
 */
public void merge(int[] arr, int p, int q, int r) {
	int i=p, j=q+1, k=p;
	int[] temp = new int[arr.length];
	
	// 각각 i, j가 각 배열의 길이를 넘지 않는다면 비교하여 temp에 넣어주기 
	while(i <= q && j <= r) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			temp[k++] = arr[j++];
		} 
	}
	
	// 첫번째 배열에 있는 나머지 값들은 이미 정렬된 데이터들이므로 차례대로 temp 배열에 넣어주면 됨. 
	while (i <= q) {
		temp[k++] = arr[i++];
	}
	
	// 두번째 배열에 있는 나머지 값들은 이미 정렬된 데이터들이므로 차례대로 temp 배열에 넣어주면 됨. 		
	while(j <= r) {
		temp[k++] = arr[j++];
	}
	
	// index p부터 r까지 원래 배열에 값 넣기 
	for (int l = p; l <= r; l++) {
		arr[l] = temp[l];
	}
	
	print(arr);
}

시간복잡도 T(n) = O(nlogn)

if n = 1      -> 0

otherwise -> T(n/2) + T(n/2) + n = 2T(n/2) + n

Ref. https://www.youtube.com/watch?v=2YvFRAC8UTM

Insertion Sort(삽입 정렬) 란?

아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식

Insertion 단계

- item to insert 전의 데이터들은 정렬이 되있는 상태

- item to insert를 정렬 데이터들의 뒤부터 비교하는 것이 효율적! -> 배열에 저장되어있기 때문

public void insertSort(int[] arr) {
	if (arr.length == 0) {
		return;
	}
	
	System.out.print("[정렬할 원소] ");
	print(arr);
	
	for (int i=1; i<arr.length; i++) {		// 1
		for (int j=i-1; j>=0; j++) {
			int temp = arr[i];
			
			// 2
			if (arr[i] > arr[j]) {
				arr[j+1] = temp;
				break;
			}
			
			arr[j+1] = arr[j];		
		}
		

		System.out.print(i + "단계 : ");
		print(arr);
	}
}

실행시간

1번의 for 루프는 n-1번 반복

2번의 삽입은 최악의 경우 i-1번 비교

최악의 경우 시간복잡도:  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ

서로 이웃한 데이터들을 비교하여 가장 큰 데이터를 가장 뒤에 보내며 정렬하는 방식

가장 큰 값을 마지막으로 보내는 개념은 selection sort와 유사

public void bubbleSort(int[] arr) {
	if (arr.length == 0) {
		return;
	}
	
	System.out.print("[정렬할 원소] ");
	print(arr);
	
    	// 뒤에서부터 정렬하므로 last pointer는 정렬된 데이터 앞을 가리킴
	for (int last=arr.length-1; last>=0; last--) {	 // 1
		for (int i = 0; i <= last-1; i++) {	 // 2
			if (arr[i] > arr[i+1]) {
				swap(arr, i, i+1);	 // 3
			}
		}
		
		System.out.print(arr.length - last + "단계 : ");
		print(arr);
	}
}

실행시간

1번의 for 루프는 n-1번 반복

2번의 for 루프는 각각 n-1, n-2, ..., 2, 1번 반복

3번의 교환은 상수 시간 작업

시간복잡도:  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ

배열 중 가장 큰 원소를 오른쪽부터 채워가며 숫자를 정렬하는 방법

각 루프마다

- 최대 원소 찾기

- 최대 원소 <-> 맨 오른쪽 원소 교환

- 맨 오른쪽 원소 제외

public void selectionSort(int[] arr) {
	if (arr.length == 0 ) {
		return;
	}
	
    	System.out.print("[정렬할 원소] ");
	print(arr);
    
	int max;
	
	for (int last = arr.length-1; last>0; last--) { // 1
		max = last - 1;
		
		// 마지막을 제외한 나머지 element 중 가장 큰 수 찾기
		for (int k = last-1; k >= 0; k--) {		// 2
			if (arr[k] > arr[max]) {
				max = k;
			}
		}
		
		if (arr[max] > arr[last] ) {	
			swap(arr, max, last);		// 3
		}
		
		System.out.print(arr.length - last + "단계 : ");
		print(arr);
	}

}

실행 시간

1번의 for 루프 n-1 번 반복

2번에서 가장 큰 수를 찾기 위한 비교 횟수: n-1, n-2, ..., 2, 1

3번의 교환은 상수시간 작업

시간 복잡도: T(n) = (n-1)+(n-2)+...+2+1 = n(n-1)/2 = O(n^2)

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ

정의

• 객체(Object) 란? 
  물리적으로 존재하거나 추상적으로 생각할 수 있는 것 중에서 자신의 속성을 가지고 있고 다른 것을 식별 가능한 것.
• 객체 모델링? 
  현실 세계 객체의 속성과 동작을 추려내어 소프트웨어 객체의 필드와 메소드로 정의하는 과정
• 객체지향 프로그래밍? 
  부품에 해당하는 객체를 먼저 만들고, 이것들을 하나씩 조립해서 완성된 프로그램을 만드는 기법

Object Oriented Programming 특징

1. Inheritance (상속)

[1] extends (class 상속)
[2] implementation (interface / class 구현)

2. Polymorphism (다형성)

: 한 타입의 참조변수로 여러 타입의 객체를 참조할 수 있는 성질 (같은 타입이지만 실행 결과가 다양한 객체를 이용할 수 있는 성질)
[1] Overloading: 메소드 다중정의
[2] Overriding: 메소드 재정의

[3] Interface : one interface, multiple implementation
하나의 인터페이스를 사용하여 다양한 구현 방법 제공 - 하나의 클래스나 함수가 다양하게 동작

3. 캡슐화(Encapsulation)
1) information hiding: 객체의 필드, 메소드를 하나로 묶고, 실제 구현 내용을 감추는 것
2) access modifier(접근 제한자) 를 사용하여 노출 여부 결정

멀티 프로세스와 멀티 스레드는 '동시에 두 가지 이상의 루틴을 실행 할 수 있는 역할'을 하는 것은 동일하다.

그럼 어떠한 차이점이 있을까?

멀티 프로세스(Multi Process)

• 부모-자식 관계라고 해도 자신만의 메모리 영역을 가지게 된다.
• 환경변수와 프로세스 핸들 테이블이 상속 가능할 뿐 결국 독립적인 관계이다.
• fork를 통해 프로세스를 복사한다.
• 유닉스 계열에서 ps 명령어로 현재 수행되고 있는 프로세스를 확인할 수 있다.
• 프로세스 간의 통신을 하려면 IPC(Inter Process Communication; 세마포어, 큐, 공유메모리)를 통해야 한다.

멀티 스레드(Multi Thread)

• 하나의 프로세스가 다수 개의 작업을 각각 스레드를 이용하여 동시에 작동 시킬 수 있다.
• 스레드는 다음과 같은 공유 메모리를 가진다.

멀티 스레드는 멀티 프로세스에 비해 상당한 이점을 가진다

1. 컨텍스트 스위칭(Context Switching) 시에 공유 메모리 만큼의 시간(자원) 손실이 줄어든다.
   : 프로세스 간의 컨텍스트 스위칭시 단순히 CPU 레지스터 교체 뿐만이 아니라 RAM과 CPU사이의 캐쉬메모리에 대한 데이터 까지 초기화 되므로 상당한 부담이 발생한다.
2. Stack을 제외한 모든 메모리를 공유하기 때문에 global(전역), static(정적) 변수 그리고 new, malloc에 의한 모든 자료를 공유할 수가 있다.
   : 이는 프로세스간 통신(ex.pipe)과 같이 복잡한 과정을 거치지 않고 보다 효율적인 일처리가 가능하다는 것을 뜻한다. (핸들 테이블과 환경변수는 덤이다.)

결국 계산기와 메모장 처럼 서로 완전히 별개의 프로그램이라면 

독립적은 프로세스를 구성해야겠지만 서로 관련된 기능들은 멀티 스레드로 구현하는 것이 이득이다!

멀티 스레드의 효율성과 안정성 문제

여러 개의 스레드가 동일한 데이터 공간을 공유하면서 이들을 수정한다는 점에 필연적으로 생기는 문제이다.

멀티 프로세스의 방식의 프로그램에서 하나의 프로세스가 자신의 데이터 공간을 망가뜨린다면 그것은 해당 프로세스의 중단을 낳게 될 것이다. 하지만 멀티 스레드 방식의 프로그램에서는 하나의 스레드가 자신이 사용하던 데이터 공간을 망가뜨린다면 그 결과는 하나의 데이터 공간을 공유하는 모든 스레드를 작동불능 상태로 만들어 버릴 것이다.
이러한 문제에 대비하기 위해 Critical Section 기법이 존재한다.

Ref.

http://divineprocess.tistory.com/entry/Multi-Thread-구축

http://karlsenchoi.blogspot.kr/2011/02/blog-post_23.html

http://m.blog.naver.com/rja1104/220551216367