알고리즘 1주차( 알고리즘 소개)

알고리즘이란?

1. 문제를 해결하기 위한 단계적 절차 또는 방법

2. 순서대로 구체적이고 명확하게 기술해야 한다.

3. 유효한 입력을 받아 실행한 결과인 해(답)를 출력한다

1.명확성

–알고리즘의 각 단계는 애매모호하지 않고 명확해야 한다.

2.정확성

–모든 유효한 입력에 대해 올바른 해를 출력해야 한다.

3.정지성

–유효한 입력이 주어지면 유한한 시간 내에 종료되어야 한다.

 

 

위와같이 알고리즘을 작성할 때는 명확하고 정확하게 작성을해야 한다.

 

다음 알고리즘을 구현해 보자.

import java.util.Scanner;

public class 함계산 {

        public static void main(String[] args){

                    int n = 5;

                    int sum = 0;

                    int i = 0;

                    while(i < n){

                             i++;

                             sum += i;

                     }

                    System.out.println(sum);

        }

}

입력값이 5일 경우 1 ~ 5의 합을 구하는 알고리즘 코드는 위와 같이 구현하면 된다.

 

위 코드는 잘못된 알고리즘이다. 이유는 무엇일까? 

product = 0이라고 선언한 뒤 while의 조건에 product < 20을 돌리면 무한루프에 걸리게된다.

따라서 잘못된 알고리즘이다.

 

보통 알고리즘을 구현할 때 어려운 문제를 풀수록 문제를 이해하는데 시간이 오래걸린다. 알고리즘 설계도 물론 중요하지만 다양한 문제들을 풀어보며 문제를 이해하는 과정을 학습하는게 중요할 것 같다.

 

배열이 주어진 후 74를 찾는 순차탐색 알고리즘을 구현해보자.

public static void main(String[] args){

           Scanner sc = new Scanner(System.in);

           int n = sc.nextInt();

           int[] arr = {28, 40, 56, 63, 74, 87, 95};

           Arrays.sort(arr)

           for(int i = 0; i < arr.length; i++){

                 if(arr[i] == n){

                    System.out.print("있다");

                    return;

                  }

            }

           System.out.print("없다");

}

arr에 배열을 저장하고 찾을 값 n을 입력한다.

배열을 sort()로 정렬해준다.

배열의 길이를 하나씩 읽어들인 후 n과 값이 같다면 "있다"를 출력한뒤 종료한다.

만약 값이 없다면 "없다"를 출력한다.

 

이번엔 이진탐색으로 알고리즘을 구해보자.

public static void main(String[] args) {

           Scanner sc = new Scanner(System.in);

           int n = sc.nextInt();

           int[] arr = {28, 40, 56, 63, 74, 87, 95};

           Arrays.sort(arr);

           int start = 0;

           int end = arr.length - 1;

           while(start <= end) {

                     int mid = (start + end) / 2;

                     if(arr[mid] == n) {

                         System.out.print("있다");

                         return;

                     } else if(arr[mid] < n) {

                               start = mid + 1;

                     } else {

                               end = mid - 1;

                     }

             }

             System.out.print("없다");

}

n에 찾는 값을 입력받고 arr에 배열을 저장한 뒤, sort()로 정렬해준다.

start노드 = 0, end노드는 배열의 길이 -1을 해줘서 뒤의 값부터 읽어오도록 저장한다.

시작노드부터 끝노드까지 반복문을 만들고

중간값 변수를 생성한뒤 (start + end) /2 를 해서 배열의 중간값을 구한다

중간값이 n이라면 있다를 출력하고 종료한다.

중간값이 n이 아니라면 중간값이 n보다 작을경우 start(첫노드)부터 하나씩 찾고 

중간값이 n보다 클경우 end(마지막 노드)부터 하나씩 찾는다.

모든 배열을 찾은 뒤 n을 발견하지 못했을경우 반복문을 종료하고 "없다"를 출력한다.

 

 

최댓값찾기 문제

1.배열의 첫 번째 요소를 최댓값으로 정한다.

2.배열의 다음 요소와 최댓값을 비교한다. 만약 다음 요소가 최댓값보다 크다면 최댓값을 그 요소로 바꾼다.

3.배열 내에 비교할 요소가 남아 있으면 2 단계로 가고 아니면 종료한다.

public static void main(String[] args){

       int [] arr = {28, 40, 56, 63, 74, 87, 95};

       int max = arr[0];

       for(int i=0; i < arr.length; i++){

            max = arr[i];

        }

        System.out.println("최댓값" + max);

}

}

 

요약

알고리즘: 문제를 해결하기 위한 단계적 절차 또는 방법

알고리즘의 조건: 명확성, 정확성, 정지성

문제를 해결하는 효율적인 알고리즘 선택

문제 해결 과정들

–문제 이해

–알고리즘 설계

–정확성 증명

–효율성 분석

–구현

알고리즘 표현: 자연어(한글 또는 영어), 의사 코드

알고리즘 설계 기법: 분할 정복, 동적 계획, 탐욕 기법, 되추적, 분기한정