알고리즘이란?
문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합을 말한다.
- 순차적(concatenation) 구조: 여러 문장(프로세스)이 순차적으로 실행되는 구조
- 선택(selection) 구조:
()안에 있는 식의 평가 결과에 따라 프로그램의 실행 흐름을 변경하는 if문
System.int: 키보드와 연결된 표준 입력 스트림
stdIn:System.in에서 문자나 숫자를 꺼내는 장치
세 값의 최댓값
Q1. 네 값의 최댓값을 구하는 m4 메서드 작성
1
2
3
4
5
6
7
static int max4 (int a, int b, int c, int d) {
int max = a;
if (b > max) b = max;
if (c > max) c = max;
if (d > max) d = max;
return max;
}
Q2. 세 값의 최솟값을 구하는 min3 메서드 작성
1
2
3
4
5
6
static int min3 (int a, int b, int c) {
int min = a;
if (b < min) min = b;
if (c < min) min = c;
return min;
}
Q3. 네 값의 최솟값을 구하는 min4 메서드 작성
1
2
3
4
5
6
7
static int min4 (int a, int b, int c, int d) {
int min = a;
if (b < min) min = b;
if (c < min) min = c;
if (d < min) min = d;
return min;
}
Q4. 세 값의 대소 관계 13종류의 모든 조합에 대해 중앙값을 구하여 출력하는 프로그램
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
package com.monica.doit.chap01;
public class Exam0104 {
static int median3 (int a, int b, int c) {
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (b > c)
return c;
else
return b;
}
public static void main(String[] args) {
System.out.println("median3(3,2,1) =" + median3(3,2,1));
System.out.println("median3(3,2,2) =" + median3(3,2,2));
System.out.println("median3(3,1,2) =" + median3(3,1,2));
System.out.println("median3(3,2,3) =" + median3(3,2,3));
System.out.println("median3(2,1,3) =" + median3(2,1,3));
System.out.println("median3(3,3,2) =" + median3(3,3,2));
System.out.println("median3(3,3,3) =" + median3(3,3,3));
System.out.println("median3(2,2,3) =" + median3(2,2,3));
System.out.println("median3(2,3,1) =" + median3(2,3,1));
System.out.println("median3(2,3,2) =" + median3(2,3,2));
System.out.println("median3(1,3,2) =" + median3(1,3,2));
System.out.println("median3(2,3,3) =" + median3(2,3,3));
System.out.println("median3(1,2,3) =" + median3(1,2,3));
}
}
Q5. 중앙값을 구하는 2개의 메서드 중 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
// 1번
static int median3 (int a, int b, int c) {
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (b > c)
return c;
else
return b;
}
// 2번
static int med3(int a, int b, int c) {
if ((b >= a && c <= a) || b <= a && c >= a))
return a;
else if ((a > b && c < b) || (a < b && c > b))
return b;
return c;
}
2번 방법의 경우 위에 if문에서 실행했던 비교 (b>=a, c<=a 등)을 아래 else if 문에서 또 비교하고 있으므로, 이미 나온 결론을 또 연산하고 있다. 따라서 1번의 경우 최악의 시나리오일 때 최대 3번의 비교를 한다. 그러나 2번의 경우 med3함수는 최악의 시나리오일 때 5번의 비교를 한다. 따라서 2번 방법이 효율이 떨어진다.
조건 판단과 분기
1
2
3
4
5
6
7
// if ~ else if ~ else 문
if (n > 0)
System.out.println("이 수는 양수입니다.");
else if (n < 0)
System.out.println("이 수는 음수입니다.");
else
System.out.println("이 수는 0입니다.");
3개의 분기로 나눠진다.
1
2
3
4
5
6
7
8
9
10
11
// if ~ else if ~ else if문
if (n == 1)
System.out.println("이 수는 1입니다.");
else if (n == 2)
System.out.println("이 수는 2입니다.");
else if (n == 3)
System.out.println("이 수는 3입니다.");
/*
else
;
*/ // 공백문: 실제로 아무것도 하지 않는 문장
4개의 분기로 나눠진다
순서도의 기호
순서도: 문제에 대한 정의/분석/해법을 그림으로 표현
- 데이터(data): 데이터의 입력과 출력을 나타낸다.
- 처리(process): 여러 종류의 처리를 담당한다. 즉 정보의 값, 자료형, 위치를 바꾸도록 정의한 연산이나 연산 집합의 실행 또는 연속적인 몇 가지 흐름 가운데 하나의 방향을 결정하는 연산 집합이나 연산군의 실행을 나타낸다.
- 미리 정의한 처리(predefined process)는 서브 루틴 및 모듈 등 다른 곳에서 이미 정의한 하나 이상의 연산 또는 명령어들로 이루어진 처리를 나타낸다.
- 판단(decision): 하나의 입구와 하나 이상을 선택할 수 있는 출구가 있고, 기호에서 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능(스위치형 기능)을 나타낸다. 주로 예상되는 평가 결과의 경로를 선 가까이에 쓴다.
- 루프 범위(loop limit): 두 부분으로 구성되어 루프의 시작과 종료를 나타낸다. 기호의 두 부분에는 같은 이름(루프에 대한 임의의 이름)을 사용한다. 루프의 시작 기호(반복 전에 판단하는 경우) 또는 종료 기호(반복 후에 판단하는 경우) 안에 초기값, 증갓값, 종룟값(종료 조건)을 표기한다.
- 선(line): 제어의 흐름을 나타낸다. 주로 흐름의 방향을 분명히 나타내고자 할 때 화살표를 붙이는데, 순서도에 작성할 때도 보기 슆게 화살표를 붙이기도 한다.
- 단말(terminator): 외부 환경으로 나가거나 외부 환경에서 들어오는 것을 나타낸다. 예를 들어 프로그램 흐름의 시작과 종료를 나타낸다.