유랑하는 개발자

삽입 정렬(Insertion Sort)은 배열의 구간을 정한다음 원소를 비교하며 정렬을 하는 방식입니다.

1. 0 번째 인덱스의 원소와 1 번째 인덱스의 원소를 비교 합니다. (ex. 범위는 0-1 인덱스)

2. 1 번째 원소가 0 번째 원소보다 작으면 첫 번째 원소의 인덱스는 1 증가하고 두 번째 원소의 인덱스는 1 감소합니다.

3. 이런식으로 범위가 1씩 증가하며 원소를 비교한 뒤 큰 숫자의  인덱스를 1씩 늘려주고 작은 숫자의 인덱스를 숫자 만큼 감소 해주세요. 

아래는 위의 순서에 맞게 실행한 예제입니다.

- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.

아래는 삽입 정렬을 구현한 자바 예제입니다.

package algorithm;

import java.util.Arrays;

public class InsertionSort {

	public static void main(String[] args) {
		int[] a = { 3, 6, 0, 9, 1 };
		int[] sorted_a = insertionSort(a);
		System.out.println(Arrays.toString(sorted_a));
	}

	public static int[] insertionSort(int[] a) {
		int i, j;
		for (i = 0; i < a.length; i++) {
			int temp = a[i];
			int range = i-1;
			while (range >= 0 && a[range] > temp) {
				a[range+1] = a[range];
				range--;
			}
			a[range+1] = temp;
		}
		return a;
	}
}

버블 정렬은(Bubble Sort) 두 인접한 원소를 순차적으로 정렬하는 방법이고 2가지 순서가 있습니다.

1. 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를 ... N-1번째 원소와 N번째 원소를 비교 합니다.

2. 1회전이 끝나면 가장 큰 원소가 맨 마지막으로 이동하기 때문에 다음 회전에서의 마지막은 N-2 원소와 N-1 원소가 됩니다.

아래는 위의 순서에 맞게 실행한 예제입니다.

- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.

아래는 선택 정렬을 구현한 자바 예제입니다.

package algorithm;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int[] a = { 3, 6, 0, 9, 1 };
		int[] sorted_a = bubbleSort(a);

		System.out.print(Arrays.toString(a));
	}

	public static int[] bubbleSort(int[] a) {
		int i, j, temp;
		for (i = a.length - 1; i > 0; i--) {
			for (j = 0; j < i; j++) {
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}
		return a;
	}

}

선택 정렬(Selection Sort)는 제자리 정렬의 알고리즘이며 3가지 순서가 있습니다.

1. 주어진 배열 값들 중에서 최소값을 찾습니다.

2. 그 최소값을 실행 순서의 값과 교체를 합니다.

3. 그렇게 첫 번째, 두 번째...마지막 -1회 까지 1, 2번 과정을 진행 합니다.

아래는 위의 순서에 맞게 실행한 예제입니다.

- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.

아래는 선택 정렬을 구현한 자바 예제입니다.

package algorithm;

public class SelectionSort {

	public static void main(String[] args) {
		int[] a = { 3, 6, 0, 9, 1 };
		int[] sorted_a = selectionSort(a);
		System.out.print(Arrays.toString(a)
	}

	public static int[] selectionSort(int[] a) {
		int i, j;
		int temp;
		for (i = 0; i <= a.length - 1; i++) {
			for (j = 0; j <= a.length - 1; j++) {
				if (a[i] < a[j]) {
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
		}
		return a;
	}

}

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section012 - 소인수 분해하기

입력받은 수(B)를 소인수 분해 하기 위해서는,

2부터 B의 제곱근 까지 나누어 떨어지는가를 확인 해야 합니다.

결과 값에 출력된 결과를 보며 로직을 이해 하세요!

Section012.java

public class Section012 {

	public static void main(String[] args) {
		int[] A = new int[100];
		int B = 20;
		int C = 0; // 배열 내 소인수 저장 위치
		int D = 2; // 제수 저장 변수(피제수를 2부터 나눔)
		int E; // 입력 받은 수(B)의 제곱근이 저장될 변수
		int MOK = 0;
		int NMG = 0;
		int i;

		while (true) {
			E = (int) Math.sqrt(B); // B의 제곱근을 E에 저장
			System.out.println("입력 받은 수 = " + B + ", 제곱근 E=" + E);
			while (true) {
				System.out.println("제수 D=" + D + ", 제곱근 E=" + E);
				if (D > E) {	// 제수(D)가 피제수 제곱근(E) 보다 크면 소인수
					D = B;
					System.out.println("break:" + D);
					break;
				} else {
					MOK = B / D;
					NMG = B - MOK * D;
					System.out.println(B + "/" + D + " NMG=" + NMG);
					if (NMG != 0) {
						D = D + 1;
						continue;
					} else
						break;
				}
			}

			System.out.println("소수 = " + D);
			A[C] = D;
			C = C + 1;	// 배열의 위치 증가
			if (B == D) {
				System.out.println("End.....");
				for (i = 0; i < C; i++)
					System.out.print(A[i] + " ");
				System.out.println("");
				break;
			} else {
				B = MOK;
				continue;
			}
		}
	}
}

결과 값

입력 받은 수 = 20, 제곱근 E=4
제수 D=2, 제곱근 E=4
20/2 NMG=0
소수 = 2
입력 받은 수 = 10, 제곱근 E=3
제수 D=2, 제곱근 E=3
10/2 NMG=0
소수 = 2
입력 받은 수 = 5, 제곱근 E=2
제수 D=2, 제곱근 E=2
5/2 NMG=1
제수 D=3, 제곱근 E=2
break:5
소수 = 5
End.....
2 2 5 

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section011 - 약수 구하기 입니다.

입력 받은 수를 1부터 차례대로 나누어 나머지가 0이 되는 제수들이 바로 입력 받은 수의 약수 입니다.

23번과 24번 줄은 자바로 구현하기 위해

알고리즘 책과 순서가 서로 바뀌었습니다.

참고 해주세요!

Section011.java

public class Section011 {

	public static void main(String[] args) {
		int[] A = new int[100];
		int B = 10;
		int C = 0; // 제수가 저장될 변수
		int D = 0; // A배열의 위치를 지정하는 변수
		int i;
		int MOK, NMG;

		while (true) {
			C = C + 1;	// 제수를 B까지 변화시키기 위해 1씩 증가시킴
			if (C > B) {
				System.out.println("입력받은 숫자 : " + B);
				for (i = 0; i < D; i++)
					System.out.print(A[i] + " ");
				System.out.println("");
				break;
			} else {
				MOK = B / C;
				NMG = B - MOK * C;
				if (NMG == 0) {
					A[D] = C;
					D = D + 1;	// 약수의 개수를 셈
				}
			}
		}
	}

}

결과 값

입력받은 숫자 : 10
1 2 5 10 

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section008 - 소수의 합 구하기 입니다.

Section008.java

public class Test008 {

	public static void main(String[] args) {
		int A=7;
		
		int HAP=0;
		int K=2;
		int J;
		int CNT=0;
		
		while(true) {
			J = 2;
			while(true){
				System.out.println("K="+K+" J="+J);
				if( (K%J)==0 ) {
					if( K == J ) {	// 4를 찾는 경우, 4까지 온 경우
						System.out.println("소수:"+K);
						HAP = HAP + K;
						CNT = CNT + 1;
						break;
					}
					else
						break;	// 4를 찾는데, 2에서 나누어진 경우
				}
				else {
					J = J + 1;
				}
			}	// inner loop
			if( K < A ) {
				K = K + 1;
			}
			else {
				break;
			}
		}
/*		
		for(K=2; K <= A; K++) {
			for(J=2; J < K; J++) {
				System.out.println("K="+K+" J="+J);
				if( (K%J)==0 ) {
					break;
				}
			}
			if( J == K ) {
				System.out.println("소수:"+K);
				HAP = HAP + K;
				CNT = CNT + 1;
			}
		}
*/		
		System.out.println("소수갯수="+CNT+" 소수합:"+HAP);
	}

}

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section007 - 소수 판별 입니다.

Section007.java

public class Test007 {

	public static void main(String[] args) {
		int A=19;
		
		int J=2;
		int i=A-1;
		
		while(true) {
			if( J <= i ) {
				if( (A%J)==0 ) {
					System.out.println("소수 아님:"+A);	
					break;
				}
				else
					J=J+1;
			}
			else {
				System.out.println("소수:"+A);
				break;
			}
		}
/*
		for(J=2; J < A; J++) {
			if( (A%J)==0 ) {
				System.out.println("소수 아님:"+A);	
				break;
			}
		}
		if( J == A )
			System.out.println("소수:"+A);
*/
	}

}

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section006 - 피보나치 수열의 합입니다.

피보나치 수열은 첫 번째 + 두 번째 항으로 세 번째 항을 만들고,

두 번째 항 + 세 번째 항 = 네 번째 항

세 번째 항 + 네 번째 항 = 다섯 번째 항

... 이런 식으로 더해가는 수열입니다.

Section006.java

public class Section006 {

	public static void main(String[] args) {
		int A = 1;	// 첫 번째 항의 값
		int B = 1;	// 두 번째 항의 값
		int C;		// 세 번째 항의 값(A+B의 값)
		int hap = 2;	// 초기값은 2
		int cnt = 2;	// 항의 갯수
		
		for(int i=1; i<=20; i++) {
			C = A + B;
			hap = hap + C;
			cnt = cnt + 1;
			//System.out.println(A + "  &  " + B);
			A = B;
			B = C;
		}
		System.out.println("결과 값 : " + hap);
	}
}

결과 값

46367

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section005 - 2! + 3! + 4! +,.. 증가하는 수열 팩토리얼 의 합입니다.

Section005.java

public class Section005 {
	public static void main(String[] args) {
		int i = 1; // 증가 변수
		int j = 1; // i! 이 저장될 변수
		int sum = 1; // 합

		for (i = 2; i < 10; i++) {
			j = j * i;
			sum = sum + j;
			System.out.print(i + "! ");
		}
		System.out.println("");
		System.out.println(sum);
	}
}

결과 값

409113

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section004 - 1+2+4+7+11+16+22+... 증가하는 수열의 합입니다.

Section004.java

public class Section004 {

	public static void main(String[] args) {
		int i = 0;
		int j = 1;		// 수열 각 항이 저장될 변수
		int sum = 1;	// 수열 각 항이 누적될(합) 변수
		
		for(i=1; i<20; i++) {
			j = j+i;
			sum = sum + j;
			//System.out.println("i = " + i + " & j = " + j + " & sum = " + sum);
		}
		System.out.println(sum);
	}
}

결과 값

1350