문제) 입력 받은 n개까지의 소수의 개수를 구하시오. (1은 소수 X)

응용) 소수의 합을 구하시오, 소수를 전부 출력하시오

소수의 개수를 구하는 방식은 간단하며 여러개의 방법이 있다. 

처음에는 안에 있는 for문을 for(int j = 2; j <= i; j++)로 사용하여 if(i % j == 0)일 경우, Count를 해주어서 구하였었다.

하지만 이와 같은 방법은 개수를 구할 수는 있었지만 모든 값들을 다 계산하여야 하기에 효율성이 떨어진다고 생각하여 더욱 효율적인 방법이 있을지 고민을 해보았다.

그 결과 아래와 같이 수정하였다. (Math.sqrt()는 루트 값을 구하는 함수)

(학생 때 수학 좀 열심히 공부할걸....)

public int solution(int n) {
      int answer = 0;
      
      for(int i = 2; i <= n; i++) {
          boolean isPrime = true;
          for(int j = 2; j <= Math.sqrt(i); j++) {
              if(i % j == 0) {
                  isPrime = false;
                  break;
              }
          }
          
          if(isPrime) {
              answer++;
          }
      }
      
      return answer;
 }

보간 탐색이란?

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

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

보간 탐색의 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 횟수를 줄이는 것이 정렬시간을 줄이는 역할.

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