Count 알고리즘
문제 : 영어 시험 성적이 80점 이상인 학생들의 수를 구하는 알고리즘을 제시하라.
- 전체 학생의 수는 100명이다.
- 영어 점수는 100점 만점을 기준으로 채점되었다.
- 영어 점수는 배열 변수 JUMSU(100)에 이미 저장되어 있다고 가정한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class CountAlgorithm {
public static void main(String[] args) {
// 10명 학생들의 영어 점수를 보관하는 배열 변수.
int jumsu[] = {70, 60, 55, 90, 85
, 75, 80, 100, 95, 45};
int cnt = 0; // 80점 이상 count 변수.
int i = 0; // 배열 인덱스 변수.
while(true) {
// 80점 이상일 경우.
if(jumsu[i] >= 80)
cnt = cnt + 1;
i = i + 1;
// 배열 인덱스가 10일 경우 종료.
if(i >= 10) break;
}
System.out.println(cnt); // 5
}
}
|
cs |
최댓값과 최솟값
문제 : 영어 시험 만점 학생들 중에서 가장 높은 수학 시험 점수를 가지고 있는 학생의 수학 점수를 찾아서 출력하는 알고리즘을 제시하라.
- 시험을 본 학생은 모두 200명이다.
- 영어 점수는 배열 변수 ENG(200), 수학 점수는 배열 변수 MATH(200)에 저장되어 있다.
- 영어, 수학 모두 100점 만점이다.
- 영어 점수가 만점인 학생이 최소한 1명은 존재한다고 가정한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class MaxAndMin {
public static void main(String[] args) {
int m = 0; // 수학 최고점 보관 변수.
int i = 0; // 인덱스 변수.
// 10명의 학생들의 영어 점수.
int eng[] = { 70, 60, 55, 90, 85
, 75, 80, 100, 95, 45 };
// 10명의 학생들의 수학 점수.
int math[] = { 90, 45, 60, 77, 85
, 65, 80, 95, 80, 55 };
while (true) {
if (eng[i] == 100) { // 영어 만점자 확인.
if (math[i] > m) // 수학 최고점 확인.
m = math[i]; // 확인된 수학 최고점 대입.
}
i = i + 1;
if (i >= 10) break; // 10이상이면 종료.
}
System.out.println(m); // 95
}
}
|
cs |
합계와 평균
문제 : 다음과 같은 조건에서 휴대폰 고객 1명이 한 달 동안 사용하는 총 통화시간을 토대로 일일 평균 통화시간(초)을 구하는 알고리즘을 제시하라.
- 한 달을 30일로 잡고, 매일(I)의 통화시간은 변수 T(I)에 저장된다.
- 만일 일일 통화시간이 200초 이하이면 무료 서비스를 해주며 총 통화시간에서 제외하고 평균 통화시간을 산정하는 과정에서도 제외한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public class SumAndAvg {
public static void main(String[] args) {
// 30일 동안의 일일 통화시간을 보관하는 변수.
int t[] = { 184, 240, 9, 235, 333
, 295, 20, 38, 329, 34
, 350, 59, 313, 24, 187
, 327, 234, 59, 324, 47
, 145, 95, 282, 148, 213
, 182, 283, 227, 156, 217 };
int sum = 0; // 합계 변수.
int n = 0; // 카운터 변수.
int i = 0; // 인덱스 변수.
while (true) {
/*
* 일일 통화시간 200초 초과일 경우
* 합계 변수에 누산 및 카운터.
*/
if (t[i] > 200) {
sum = sum + t[i];
n = n + 1;
}
i = i + 1;
if (i >= 30)
break;
}
double avg = (double) sum / n;
System.out.println(avg); // 280.1333333333333
}
}
|
cs |
소수 판별
문제 : 1부터 100 사이에서 가장 큰 소수를 구하는 알고리즘을 제시하라.
- 소수(Prime Number)란 1과 자기 자신 이외의 수로는 나누어 떨어지지 않는 1보다 큰 자연수를 가리킨다. 예를 들어 2, 3, 5, 7, 11, 13, 17, ...은 소수이다.
- 만일 자연수 N이 소수라면, 2부터 N의 제곱근 √N까지의 자연수들 중에서 N을 나누어 떨어지게 하는 수는 존재하지 않는다.
- N의 제곱근(√N)은 시스템 함수 SQRT(N)을 호출하여 계산한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class PrimeNumber {
public static void main(String[] args) {
int p = 2; // 가장 큰 소수를 보관하는 변수.
int n = 3; // 3부터 100까지 조사할 자연수를 보관하는 변수.
while(true) {
double tmp = Math.sqrt(n);
int m = (int) tmp; // n의 제곱근을 계산하여 보관하는 변수.
for(int i = 2; i <= m ; i++) {
int r = n % i; // 나머지를 보관하는 변수.
if(r == 0)
break;
if(i == m)
p = n;
}
n = n + 1;
if(n > 100) break;
}
System.out.println(p); // 97
}
}
|
cs |
소인수 분해
정의 : 합성수를 소수의 곱으로 나타내는 방법.
문제 : 자연수 n을 입력받아 소인수 분해하여 그 결과를 출력하는 과정을 반복하는 알고리즘을 제시하라.
- 입력받은 값 n은 1000 이하의 자연수라고 가정한다.
- 입력받은 정수 n이 2보다 작으면 알고리즘을 종료한다.
- 입력받은 정수 n이 소수이면 "소수"라고 출력한다.
- 입력받은 정수 n이 소수가 아니면 소인수 분해한 결과를 출력한다.
- 단계별로 소인수 분해한 결과를 배열에 저장해 두었다가 나중에 한꺼번에 출력한다.
- 132는 2 X 2 X 3 X 11과 같이 소인수 분해된다.
- MOD()는 나누기에서 나머지를 구하는 함수이다.
- 다양한 입력별 알고리즘의 실행 예시는 다음과 같다.
입력 : 132 -> 출력 : "2*2*3*11" 입력 : 20 -> 출력 : "2*2*5"
입력 : 37 -> 출력 : "소수" 입력 : 0 -> 알고리즘 종료
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class PrimeFactorization {
public static void main(String[] args) {
// 소인수 분해한 결과를 저장할 배열.
int a[] = new int[20];
int n = 20; // 소인수 분해할 자연수.
int t = 0; // 배열의 첨자용 변수.
do {
if(n >= 2) {
int p = 2; // n을 나누는 수.
for( ; p <= n ; p++) {
if(n % p == 0) break;
}
a[t] = p;
n = n /p;
t = t + 1;
} else return;
} while(n != 1);
if(t == 1)
System.out.println("소수");
else {
for(int j = 0 ; j < t-1 ; j++) {
System.out.print(a[j] + "*");
}
System.out.println(a[t-1]); // 2*2*5
}
}
}
|
배수와 공배수
문제 : 배열 A에 21, 17, 4, 51, 24, 75, 40, 27, 48, 72가 A(1)부터 시작하여 순차적으로 입력되어 있다고 가정할 때, 3의 배수이면서 4의 배수인 수의 개수를 구하는 알고리즘을 제시하라(단, A를 B로 나눈 나머지를 구해 주는 시스템 함수 MOD(A,B)를 활용한다).
* 배수 : 그 수에 정수를 곱한 수이다.
* 공배수 : 서로 다른 두 개 이상인 자연수의 공통인 배수를 말한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class MultipleAndCommonMultiple {
public static void main(String[] args) {
// 10개의 값을 보관하는 배열 변수.
int a[] = { 21, 17, 4, 51, 24, 75, 40, 27, 48, 72 };
int cnt = 0; // 카운트 변수.
int i = 0; // 인덱스 변수.
do {
int n3 = a[i] % 3; // 3의 배수를 보관하는 변수.
int n4 = a[i] % 4; // 4의 배수를 보관하는 변수.
int n = n3 + n4; // n3과 n4 더한 값을 보관하는 변수.
if(n == 0)
cnt = cnt + 1;
i = i + 1;
} while(i < 10);
System.out.println(cnt); // 3
}
}
|
cs |
약수와 완전수
문제 : 4부터 500까지의 자연수 중에서 완전수를 찾아 출력하고 그 개수를 구하는 알고리즘을 제시하라.
* 약수 : 어떤 수로 정수가 나누어 떨어지는 것.
* 완전수 : 28의 약수는 {1, 2, 4, 7, 14, 28}인데 28을 뺀 나머지 약수의 합이 28이므로, 28은 완전수이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public class DivisorAndPerfectNumber {
public static void main(String[] args) {
int tn = 0; // 완전수 카운트 변수.
for (int n = 4; n <= 500; n++) {
int sum = 0; // 완전수 합계 변수.
/*
* 내부 for문 범위값.
* 1부터 그 절반 값까지만 나누어 보면 자신을 제외한
* 모든 약수를 구할 수 있다는 점을 이용, 나눌 수 있는
* 최대값을 내부 for문의 범위값으로 활용.
*/
int k = n / 2;
for (int j = 1; j <= k; j++) {
int r = n % j; // 나머지를 보관하는 변수.
if (r == 0)
sum = sum + j;
}
if (n == sum) {
// N = 6
// N = 28
// N = 496
System.out.println("N = " + n);
tn = tn + 1;
}
}
System.out.println(tn); // 3
}
}
|
cs |
최대공약수와 최소공배수
문제 : 다음과 같은 유클리드 호제법에 의하여 두 정수 X, Y의 최대공약수(GCD)를 구하는 알고리즘을 제시하라.
1) GCD(X, Y) = GCD(Y, X) => X < Y일 경우
2) GCD(X, Y) = Y => X >= Y이면서 MOD(X,Y) = 0일 경우
3) GCD(X, Y) = GCD(Y, MOD(X,Y)) => 그 외(즉, X >= Y이면서 MOD(X,Y) != 0일 경우)
(단, MOD(X,Y)는 정수 X를 정수 Y로 나눈 나머지를 구하는 시스템 함수이다).
* 최대 공약수 : 두 수 X와 Y의 약수 중 공통된 약수(공약수) 가운데 가장 큰 수.
* 최소 공배수 : X와 Y의 배수 중 공통된 배수(공배수) 가운데 가장 작은 수.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class GCDAndLCM {
public static void main(String[] args) {
int x = 60, y = 124; // 60과 124의 최대공약수
if(x < y) {
int temp = x; // 임시 변수.
x = y;
y = temp;
}
for( ; ; ) {
int m = x % y;
if(m == 0) break;
x = y;
y = m;
}
System.out.println(y); // 4
}
}
|
cs |
근사값
문제 : 배열 A(100)의 원소 100개는 절대값이 500 이하이다. 이 중에서 정수 33에 가장 가까운 근사값을 찾아 해당원소의 첨자를 출력하는 알고리즘을 제시하라.
* 근사값 : 가까운 값.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Approximation {
public static void main(String[] args) {
// 절대값 500이하의 정수 100로 구성된 배열.
int a[] = { 131, 450, -100, 150, 50
, -10, 0, 40, 32, 1 };
int mincha = 533; // 근사값 보관 변수.
int n = 0; // 인덱스 변수.
int ans = n; // 최종 출력 변수.
int cha = 0; // 근사값 계산 변수.
do {
// 절대값 or 양수로 보관해야 하기에.
if (a[n] >= 33)
cha = a[n] - 33;
else
cha = 33 - a[n];
// 근사값 보관값이 계산값보다 클 경우.
if (cha < mincha) {
mincha = cha;
ans = n;
}
n = n + 1;
} while (n < 10);
System.out.println(ans + 1 + "번째 항"); // 9번째 항.
}
}
|
cs |
1의 보수와 2의 보수
정의 : 1의 보수는 2진수의 각 자리에 대하여 0은 1로, 1은 0으로 바꾼 수이고, 2의 보수는 1의 보수보다 1만큼 큰 수이다.
문제 : 어떤 2진수에 대하여 2의 보수를 구하는 알고리즘을 제시하라.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
public class Complement {
public static void main(String[] args) {
int b[] = {0,1,0,1,0}; // 2진수.
int o[] = new int[5]; // 1의 보수.
int t[] = new int[5]; // 2의 보수.
int i = 0; // 인덱스 변수.
// 1의 보수로 변환.
do {
/*
* b 배열의 값을 1 빼기를 하여
* 1 = 0, 0 = 1로 변환한다.
*/
o[i] = 1 - b[i];
i = i + 1;
} while(i < 5);
for(int a = 0 ; a < 5 ; a++)
System.out.print(o[a]); // 10101
System.out.println();
i = 4;
int c = 1; // 자리 올림수(Carry).
// 2의 보수로 변환.
do {
t[i] = 1;
if(o[i] == c)
t[i] = 0;
c = o[i] * c;
i = i - 1;
} while(i >= 0);
for(int a = 0 ; a < 5 ; a++)
System.out.print(t[a]); // 10110
}
}
|
cs |
2진수 10진수 변환
문제 : 다음 조건을 고려하여 2진수를 10진수로 변환하는 알고리즘을 제시하라.
- 변환할 2진수는 크기가 8인 배열 T에 저장되어 제공된다.
- 첫 번째 비트 T(1)은 2진수의 부호를 나타낸다. T(1)이 0이면 양수, 1이면 음수이다.
- 첫 번째 비트 T(1)의 값이 1인 음수의 경우, 2의 보수에 의하여 크기가 표현된다.
- 함수 ABS(X)는 X의 절대값을 계산해 주는 함수이다.
- 함수 POWER(X,Y)는 X의 Y제곱, 즉 X^Y을 계산해 주는 함수이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class 2진수10진수변환 {
public static void main(String[] args) {
// 2진수 저장 변수.
int t[] = { 1, 1, 1, 1, 0, 1, 1, 0 };
// 1의 보수를 저장할 임시 배열 변수.
int c[] = new int[8];
int d = 0; // 10진수 보관 변수.
int sign = 1; // 2진수 "+,-" 구분 변수.
if(t[0] != 0) {
sign = -1;
int b = 1; // 감수 1을 나타내는 변수.
for(int k = 7 ; k >= 1 ; k--) {
c[k] = t[k] - b;
if(t[k] != 0 || b != 1)
b = 0;
c[k] = Math.abs(c[k]);
t[k] = 1 - c[k];
}
}
for(int k = 1; k <= 7 ; k++) {
// 10진수 계산값 임시 변수.
int t1 = (int) Math.pow(2, (7 - (double) k));
int t2 = t[k] * t1;
d = d + t2;
}
d = d * sign;
System.out.println(d); // -10
}
}
|
cs |
10진수와 16진수의 변환
문제 : 다음과 같은 조건에서 10진수를 받아들여 16진수로 변환하여 출력하는 알고리즘을 제시하라.
- 입력으로 주어지는 10진수는 변수 D에 저장하여 처리한다.
- 16진수를 나타내는 각 숫자에 해당하는 문자는 문자형 배열 변수 H(16)에 저장되어 제공된다.
- 16진수는 최대 20자리까지 보관이 가능하며 문자형 배열 변수 T(20)을 이용하여 한 자리씩 저장된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public class 10진16진수변환 {
public static void main(String[] args) {
// 16진수 표현 배열.
char h[] = { '0', '1', '2', '3', '4',
'5','6', '7', '8', '9',
'A', 'B', 'C', 'D', 'E', 'F' };
// 16진수 결과값 보관 배열.
char t[] = new char[20];
int d = 1017; // 10진수 변수.
int i = 0; // 인덱스 변수.
int m; // 변수 d를 16으로 나누었을 때 몫.
int n; // 변수 d를 16으로 나누었을 때 나머지.
do {
m = d / 16;
n = d % 16;
t[i] = h[n];
i = i + 1;
d = m;
} while(m >= 16);
t[i] = h[m];
int k = i; // 순환용 변수.
do {
System.out.print(t[k]);
k = k - 1;
} while(k >= 0);
}
}
|
cs |
BCD코드와 3초과 코드의 변환
문제 : 다음과 같은 조건에서 4비트의 BCD코드를 받아들여 4비트의 3초과 코드로 변환하여 출력하는 알고리즘을 제시하라.
- BCD코드는 크기가 4인 배열 B(4)에 1비트씩 저자오디어 입력으로 제공된다.
- 3초과 코드는 크기가 4인 배열 E(4)에 1비트씩 저장된 후 나중에 출력된다.
- 2진수 0011은 크기가 4인 배열 A(4)에 1비트씩 저장된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public class 3초과_코드_변환 {
public static void main(String[] args) {
// BCD코드 보관 배열.
int b[] = { 0, 1, 1, 1 };
// 3초과 코드 보관 배열.
int e[] = new int[4];
// 3초과 변환 비트 배열.
int a[] = { 0, 0, 1, 1 };
int c = 0; // 자리올림수(Carry).
for(int k = 3 ; k >= 0 ; k--) {
int s = b[k] + a[k] + c;
if(s > 1) {
e[k] = s % 2;
c = 1;
} else {
e[k] = s;
c = 0;
}
}
for(int k = 0 ; k <=3 ; k++)
System.out.print(e[k]); // 1010.
}
}
|
cs |
패리티 비트 검증
문제 : 다음 조건으로 8비트 패리티 비트 오류 검사를 실시하는 알고리즘을 제시하라.
- 입력으로 총 9비트를 받아들인다.
- 첫 번째 비트는 패리티 검사 방식을 나타내는데, 그 값이 1이면 홀수 패리티, 0이면 짝수 패리티로 검사함을 의미한다.
- 나머지 8개의 비트는 0 또는 1의 값을 갖는 데이터 영역이다.
- 홀수 패리티는 8비트 데이터 영역에 저장된 1의 개수가 홀수 개인 경우에 오류가 없음을 의미한다.
- 짝수 패리티는 8비트 데이터 영역에 저장된 1의 개수가 짝수 개인 경우에 오류가 없음을 의미한다.
- 패리티 검사를 오류가 없으면 "오류 미발견"이라고 출력하고, 오류가 있으며 "오류 발견"이라고 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class 패리티비트검증 {
public static void main(String[] args) {
int p[] = { 0, 1, 0, 0, 1, 0, 0, 0, 1 };
int pn = 0;
for(int k = 1 ; k < 9 ; k++) {
if(p[k] == 1)
pn = pn + 1;
}
int e = pn % 2;
if(p[0] == e)
System.out.println("오류 미발견");
else
System.out.println("오류 발견");
// 오류 발견
}
}
|
cs |
'정보처리산업기사 실기 > 알고리즘' 카테고리의 다른 글
| 알고리즘 기출문제 파악(20년 3회 ~ 15년 1회) (0) | 2020.11.20 |
|---|---|
| 소프트웨어 개발 (0) | 2020.11.17 |
| 응용 알고리즘 - 자료 구조 (0) | 2020.11.17 |
| 응용 알고리즘 - 배열 (0) | 2020.11.16 |
| 기본 알고리즘 - 수열 (0) | 2020.11.15 |