CS - 알고리즘

알고리즘

• 입력받은 자료를 출력의 형태로 만드는 과정
• 수행 명령의 규칙적인 나열
• 알고리즘을 평가할 때 정확성도 중요하지만, 효율성도 중요하다.

EX) 3개의 수 중 가장 큰 수를 찾는 알고리즘

3개의 수 A,B,C가 있다고 하자.
A와 B의 대소 관계를 구분한다.
두 수 중 더 큰 수를 임시 값 T에 저장한다.
T와  C의 대소 관계를 구분한다.
두 수 중 더 큰 수를 T에 저장한다.
T값을 출력한다.

 

 입력 A,B,C

 출력 T

1. 만약 A와 B중 A가 더 크거나 같으면 T에 A값을 저장한다.

2. 아니면 T에 B 값을 저장한다.

3. 만약 T와 C중 T가 더 크거나 같으면 T에 계속 진행한다.

4. 아니면 T에 C 값을 저장한다.

5. T값을 출력한다.

 

자바언어로 표현하면

if (A >= B) {
    T = A;
} else {
    T = B;
}

if (T >= C) {
    continue;
} else {
    T = C;
}

return C;

여기서 if와 else문은 조건이다.

if안에 조건절은 결정을 내리기 위한 질문에 해당되는데, 이를 불리얼(boolean)이라 한다.

위에 알고리즘에는 나와 있지 않지만, 반복순환을 나타내는 루프(loop)도 존재한다. (ex. while문)

 

---

생각해보기

친구와 1부터 100까지 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 하려고 합니다. 이 때 사용할 알고리즘을 의사코드로 표현하면 어떻게 될까요?

효율성을 높이기 위해 중간값을 정해서 범위를 줄여나가는 이분 탐색으로 접근하려 한다.

 

1.범위중 가장 작은 min값과 가장 큰 max값을 받는다.

2. 두수의 중간 값 mid값을 저장한다.

3. 친구의 수가 mid값과 일치하면 출력한다.

4. 친구의 수가 mid값 보다 크면 범위는 mid에서 max로 정하고, 1번으로 간다.

5. 친구의 수가 mid값 보다 작으면 범위는 min에서 mid로 정하고, 1번으로 간다.

 

import java.util.Scanner;

public class test {
    private static int num;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
        checkNum(0,100);
    }

    private static void checkNum(int min,int max) {
        int mid = (min+max)/2;
        if(mid == num){
            System.out.println(mid);
        }
        else if (mid<num){
            checkNum(mid,max);
        }
        else {
            checkNum(min,mid);
        }
    }
}

---

https://www.boostcourse.org/

다 함께 배우고 성장하는 부스트코스

 

부스트코스 - 모두를 위한 컴퓨터 과학을 공부하고 작성하였습니다.