우리는 채팅창에서 대화를 주고 받으면서 동시에 채팅창에 사진을 올려 공유할 수도 있다. 이처럼 동시에 여러 작업을 할 수 있는 것은 무엇 때문일까? 바로 쓰레드 덕분이다.

그렇다면 쓰레드란 무엇일까? 이제 알아보도록 하자.

쓰레드란?

· 프로세스 내에서 자원을 이용하여 작업을 수행하는 것.

· 별도의 호출 스택(call stack)이 있다는 것을 의미.

멀티 쓰레딩

· 하나의 프로세스 내에서 여러 쓰레드가 동시에 작업을 수행하는 것.

· 실제로는 한 개의 CPU가 한 번에 한 가지의 작업만 할 수 있기 때문에 아주 짧은 시간 동안 여러 작업을 번갈아 가며 수행함으로써 여러 작업이 동시에 수행되는 것처럼 보이게 하는 것.

멀티 쓰레딩의 장점

· CPU의 사용률을 향상 시킴.

· 자원을 보다 효율적으로 사용할 수 있음.

· 사용자에 대한 응답성이 향상됨.

· 작업이 분리되어 코드가 간결해짐.

※ 프로세스의 성능이 쓰레드의 개수에 비례하지는 않음.

멀티 쓰레딩의 단점

잘못하면 교착상태(Deadlock)의 빠질 수 있음.

※ 교착상태란 두 쓰레드가 자원을 점유한 상태에서 서로 다른 쓰레드가 점유한 자원을 사용하려고 기다리느라 실행이 멈춰있는 상태.

쓰레드 구현하는 방법

· Thread 클래스를 상속 받는 방법

· Runnable 인터페이스를 구현하는 방법

Thread 클래스를 상속 받는 방법

public class MyThread extends Thread{
	@Override
	public void run() {
		// Thread 클래스의 run()을 오버라이딩
	}
}

public class MyThreadTest {
	public static void main(String[] args) {
		MyThread th = new MyThread();
		th.start();
	}
}

Runnable 인터페이스를 구현하는 방법

public class MyThread implements Runnable {
	@Override
	public void run() {
		// Runnable 인터페이스의 추상메서드인 run()을 구현
	}
}

public class MyThreadTest {
	public static void main(String[] args) {
		Runnable r = new MyThread();
		Thread th = new Thread(r);
		th.start();
	}
}

※ Runnable 객체와 Thread 객체의 관계는 작업과 일꾼 사이의 관계와 같음. Runnable 객체에 Thread에서 실행시킬 작업이 들어있음.

※ 쓰레드를 실행시킬 때 왜 run()이 아닌 start()일까? run()을 호출하는 것은 쓰레드를 실행시키는 것이 아니라 단순히 클래스에 속한 메서드를 호출하는 것이다. 따라서 쓰레드의 작업을 실행하는데는 start()를 사용한다.

[참고] 자바의 정석

[참고] Head First 자바

구글 API, 페이스북 API 등 개발을 하기 위해서 문서를 읽다보면 API라는 용어를 자주 보게 되는데 과연 api란 무슨 뜻일까???

API란?

· Application Programming Interface의 약어.

· 프로그램 또는 애플리케이션이 운영 체제에 어떤 처리를 위해서 호출할 수 있는 서브루틴 또는 함수의 집합.

· 애플리케이션과 컴퓨터의 매개 역할을 하기 때문에 인터페이스라는 명이 붙음.

· 소스 코드 수준에서 정의되는 인터페이스.

· 사양(Specification)만을 정의하기 때문에 구현(Implementation)물과는 독립적임.

API와 라이브러리의 차이점

· 라이브러리는 실제로 동작할 수 있는 단편화된 프로그램.

[참고] https://namu.wiki/w/API

[참고] http://terms.naver.com/entry.nhn?docId=783385&cid=42111&categoryId=42111

보간 탐색이란?

· 정렬이 이미 되어 있는 리스트에서 탐색키가 존재할 위치를 예측하여 탐색하는 방법. (사전에서 'ㄱ'으로 시작되는 단어가 앞에 있을 거라고 생각하고 앞 부분을 찾는 것과 같은 원리)

· 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색함. (이진 탐색의 업그레이드 버전?)

보간 탐색의 index값 구하는 공식

이진 탐색에서 mid값 구하는 공식과는 다름.

보간 탐색의 장점

· 많은 데이터가 비교적 균등하게 분포되어 있을 경우 보간 탐색은 이진 탐색보다 더 효율적일 수 있음.

시간 복잡도

보간 탐색 코드(Java)

public int interpolationSearch(int[] arr, int key, int low, int high) {
	int index = 0;
	
	while(low < high) {
		if(key < arr[low] || key > arr[high]) {
			return -1;
		} 
			
		index = low + (key - arr[low]) * ((high - low)) / (arr[high] - arr[low]);
			
		if(key == arr[index]) {
			return index;
		} else if(key < arr[index]) {
			high = index - 1;
		} else {
			low = index + 1;
		}
	}
		
	return -1;
}

이진 탐색이란?

· 정렬된 리스트의 중앙에 있는 키 값을 조사하여 찾고자하는 레코드가 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 좁혀가는 방법.

· 반드시 정렬된 리스트여야 하며 고정된 데이터에 적합하다. 따라서 데이터의 삽입이나 삭제가 빈번할 시에는 적잡하지 않다.

이진 탐색의 비교 횟수

시간 복잡도

이진 탐색 코드 (Java)

public void binarySearch(int[] array, int num) {
	int left = 0;
	int right = array.length - 1;
	int mid = 0;
		
	while(left <= right) {
		mid = (left + right) / 2;
			
		if(num == array[mid]) {
			System.out.println("찾으시는 숫자 " + num + "을 찾았습니다. " + (mid + 1) + "번째에 있었습니다.");
			break;
		} else if(num < array[mid]) {
			right = mid - 1;
			mid = (left + right) / 2;
		} else {
			left = mid + 1;
			mid = (left + right) / 2;
		}
	}
}

순차 탐색이란?

· 정렬되지 않은 레코드를 처음부터 마지막까지 하나씩 검사하여 원하는 레코드를 찾아가는 방법.

· 단 방향으로 탐색하기 때문에 선형 탐색이라고 함.

순차 탐색의 장점

· 별도의 데이터 조작이 없으므로 구현이 쉬움

순차 탐색의 단점

· 비 효율적인 방법

순차 탐색의 평균 비교횟수

시간복잡도

· 탐색이 성공할 경우 비교 횟수 :

· 탐색이 실패할 경우 비교 횟수 :

따라서

순차 탐색 코드 (Java)

public int sequentialSearch(int[] arr, int key) {
	for(int i = 0; i < arr.length; i++) {
		if(arr[i] == i) {
			return i;
		}
	}
		
	return -1;
}

탐색이란?

· 배열, 트리, 그래프, 파일, 데이터베이스, 인터넷 등에 저장되어 있는 많은 자료 중에서 필요한 자료를 찾는 것.

· 레코드의 집합에서 특정한 레코드를 찾아내는 작업. (레코드들은 보통 키라고 불리는 특정 필드에 의해 식별)

탐색의 종류

· 순차 탐색, 색인 순차 탐색, 이진 탐색, 보간 탐색, 블록 탐색, 피보나치 탐색 등 그 종류가 다양함.

탐색의 성능 향상

· 무작위의 상태보다는 어느 정도 분류가 되어 있는 상태이거나 정렬된 상태일 경우 탐색이 더 용이.

선택 정렬(Selection Sort)이란?

전체 리스트를 왼쪽 리스트와 오른쪽 리스트로 구분한 뒤, 오른쪽 리스트에서 가장 작은 레코드를 꺼내어 왼쪽 리스트의 오른쪽 끝에 넣는 방법.

이때, 왼쪽의 리스트는 정렬된 리스트이고 오른쪽 리스트는 정렬할 리스트로 가정한다.

(7, 3, 9, 4, 1, 6)을 삽입 정렬로 정렬한 순서

선택 정렬의 장점

이동 연산이 (n - 1)번만 필요하므로 큰 레코드의 정렬에 유리.

선택 정렬의 비교횟수

삽입 정렬은 레코드의 수가 n일 경우 (n-1)번의 삽입을 필요로 하며, 매ㅓㄴ 삽입할 때마다 정렬된 리스트의 레코드를 비교해서 삽입될 위치를 찾아야 한다.

이때 필요한 평균 비교횟수는 이미 정렬된 왼쪽 리스트의 크기의 반으로 가정할 수 있으며, 그 크기는 1, 2, 3, ..., (n-2), (n-1)과 같이 증가한다.

선택정렬의 이동횟수

레코드의 수가 n일 경우 최소값을 (n - 1)번 선택해야 한다. 따라서 이동 횟수는 (n - 1)이다.

시간복잡도

선택정렬 코드 (Java)

public int[] sort() {
        int temp = 0;
	for(int i = 0; i < array.length - 1; i++) {
		min = i;
		for(int j = i + 1; j < array.length; j++) {
			if(array[j] < array[min]) {
				min = j;
			}
		}
			
		temp = array[i];
		array[i] = array[min];
		array[min] = temp;
	}
	
	return array;
}

회문(Palindrome)이란?

단어나 구 또는 문장 등에서 앞으로 읽으나 뒤로 읽으나 같은 것을 말한다.

예를 들어서 "구로구"와 같은 단어나 "다들잠들다"와 같은 문장이 있다.

회문(Palindrome) 판별 소스 (Java)

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = 0;
		String[] strArry;
		num = sc.nextInt();
		
		strArry = new String[num];
		
		for(int i = 0; i < num; i++) {
			strArry[i] = sc.next();
		}
		
		for(int s = 0; s < num; s++) {
			int count = 0;
			
			System.out.print("#" + (s+1) + " ");
			
			for(int i = 0; i < strArry[s].length() - 2; i++) {
				for(int j = i + 2; j < strArry[s].length(); j++) {
					Palindrome p = new Palindrome(strArry[s].substring(i, j + 1));
					if(p.isPalindrome()) {
						count++;
						System.out.print(strArry[s].substring(i, j + 1) + " ");
					}
				}
			}
			
			if(count != 0) {
				System.out.println(","+ count);
			} else {
				System.out.println(count);
			}
		}
		
		sc.close();
	}
}

class Palindrome {
	String str;
	
	public Palindrome(String str) {
		this.str = str;
	}
	
	public boolean isPalindrome() {
		boolean isTrue = true;
		
		for(int i = 0; i < str.length(); i++) {
			if(str.charAt(i) != str.charAt(str.length() - 1 - i)) {
				isTrue = false;
			}
		}
		
		return isTrue;
	}
}

원하는 개수만큼 문장을 입력한 후, 그 문장에서 회문이 몇 개 있는지 출력해주는 소스이다.

3글자 이상으로 이루어진 경우에만 회문으로 인정했다.

삽입 정렬이란?

전체 리스트를 왼쪽 리스트와 오른쪽 리스트로 구분한 뒤, 오른쪽 리스트에서 임의의 레코드를 꺼내어 왼쪽 리스트의 적합한 위치에 삽입하는 방법.

이때, 왼쪽의 리스트는 정렬된 리스트이고 오른쪽 리스트는 정렬할 리스트로 가정한다.

(7, 3, 9, 4, 1, 6)을 삽입 정렬로 정렬한 순서

삽입 정렬의 단점

삽입 정렬은 배열로 이루어진 리스트들의 중간에 새로운 레코드를 삽입하려면 삽입될 위치의 오른쪽에 있는 레코드들은 한 칸씩 오른쪽으로 밀어야 한다. 그러므로 레코드의 크기가 크다면 얼마나 많은 시간을 레코드의 이동에 소모해야하는지 상상해보자.

따라서 삽입 정렬은 레코드 양이 많고 레코드 크기가 클 경우에 적합하지 않다. 반면에 대부분의 레코드가 이미 정렬되어 있는 경우에 효율적이다.

삽입 정렬의 비교횟수

삽입 정렬은 레코드의 수가 n일 경우 (n-1)번의 삽입을 필요로 하며, 매ㅓㄴ 삽입할 때마다 정렬된 리스트의 레코드를 비교해서 삽입될 위치를 찾아야 한다.

이때 필요한 평균 비교횟수는 이미 정렬된 왼쪽 리스트의 크기의 반으로 가정할 수 있으며, 그 크기는 1, 2, 3, ..., (n-2), (n-1)과 같이 증가한다.

삽입정렬의 이동횟수

레코드의 이동횟수는 비교횟수와 같으므로 삽입정렬은 비교 및 이동 측면에서 번의 연산이 필요하므로이다.

시간복잡도

삽입정렬 코드 (Java)

public int[] sort() {
	int temp = 0;
		
	for(int i = 1; i < array.length; i++) {
		temp = array[i];
		for(int j = i - 1; j >= 0 && array[j] > temp; j--) {
			array[j + 1] = array[j];
			array[j] = temp;
		}
	}
		
	return array;
}

정렬이란?

· 크기 순서에 무관하게 나열된 데이터를 크기 순서대로 다시 나열하는 작업.

· 데이터를 탐색하는데 반드시 필요한 작업.

· 크기가 커지는 순서로 정렬 → 오름차순 정렬.

· 크기가 작아지는 순서로 정렬 → 내림차순 정렬.

정렬 알고리즘의 효율을 평가하는 기준

· 비교횟수

· 데이터의 이동횟수

· 사용되는 메모리의 양

내부 정렬이란?

레코드를 모두 메모리 안으로 읽어 들여 리스트를 정렬하는 것.

* 레코드 : 정렬해야 할 대상.

* 리스트 : 레코드의 집합.

내부 정렬 방법

· 기본 정렬 방법 : 삽입 정렬, 선택 정렬, 버블 정렬.

· 성능 개선 방법 : 퀵 정렬, 합병 정렬, 쉡 정렬, 힙 정렬, 기수 정렬. 

외부 정렬이란?

외부 기억장치에 있는 레코드의 집합인 파일을 대상으로 레코드를 정렬하는 것.

* 파일 : 외부(보조)기억장치에 저장되는 레코드의 집합.

내부 정렬과 외부 정렬의 비교

· 내부 정렬은 메모리 안에서 정렬이 이루어지기에 접근 속도가 빠른 반면 외부 정렬은 상대적으로 접근 속도가 매우 느림.

· 용량의 차이는 내부 정렬이 메모리를 사용하기에 외부 정렬보다 상대적으로 매우 적다.

· 내부 정렬에서 레코드들을 비교 및 이동하는데 걸리는 시간은 메모리 접근 빈도수에 비례, 외부 정렬에서는 블럭 위의 파일 접근 빈도수에 비례.

· 내부 정렬의 효율은 데이터의 비교나 이동횟수를 줄임으로써 향상, 외부 정렬은 파일 I/O 횟수를 줄이는 것이 정렬시간을 줄이는 역할.

[출처] 정렬 탐색 프로그래밍