[Java 알고리즘 기초] 반복문, 배열 기본 및 선형 검색 (2장/ 1104)

- 독학 교재: <알고리즘 첫걸음 C&자바 편>

아직까지는 수월했다. 인터넷서점에서 너무할 정도로 친절하다는 후기를 본 적이 있는데, 진도 나가기 부담스럽지 않아서 좋았다.(C와 자바 배열의 인덱스는 0부터 시작한다거나, 초깃값을 대입해서 변수를 초기화하는 것부터 언급한다. 이 포스팅에서는 생략하였음)

---

2-1장. 반복문과 배열의 기본

• 포인트1: 루프 카운터(반복 회수를 세는 변수)와 배열의 인덱스를 대응시키기
• 포인트2: 변수를 초기화하기

배열 요소의 합을 구하는 알고리즘 구현

자바 공부 경험이 있다면 아래 코드는 정말 익숙할 것이다.

sum에 array[i] 값을 더한 후 i의 값을 증가시킨다는 점을 기억해 두자.

public class SumOfArray {
    public static void main(String[] args) {
        int[] array = {2, 45, 66, 33, 454, 223, 4453};
        int sum = 0;
        int sum2 = 0;

        for(int i=0; i<array.length; i++) {
            sum += array[i];
        }

        for(int arr: array) { // for-each문
            sum2 += arr;
        }
        System.out.println(sum); // 5276
        System.out.println(sum2); // 5276
    }
}

알고리즘의 추적(책에서 사용하는 방법)

- 추적이라고 하니 어감이 다른데, 책에 앞서 언급되었듯이 trace로 받아들이면 좀 더 와닿았다.

• 알고리즘 설명: 알고리즘의 개요를 설명하고, 의사코드로 세세히 알아본 뒤 자바로 구현해 실행 결과를 확인
• 알고리즘 추적: 디버깅하듯 값의 변화를 짚어서, 처리 단계를 직접 살펴보며 알고리즘의 동작을 이해
• 자바를 이용한 알고리즘 추적: 자바의 처리 내용을 화면에 표시하는 코드를 추가해 깊이 이해

배열 요소의 합 계산 추적

public class SumOfArrayTrace {
    int sumOfArray(int[] arr) {
        int sum = 0;
        System.out.printf("반복 실행 전: sum = %d\n", sum);

        for(int i = 0; i < arr.length; i++) {
            sum += arr[i];
            System.out.printf("반복 실행 중: sum = %d, i = %d\n", sum ,i);
        }
        System.out.printf("반복 실행 후: sum = %d\n", sum);
        return sum;
    }

    public static void main(String[] args) {
        int[] array = {2, 45, 66, 33, 454, 223, 4453};
        SumOfArrayTrace sumOfArrayTrace = new SumOfArrayTrace();
        System.out.println(sumOfArrayTrace.sumOfArray(array));
    }
}

2-2장. 선형 검색

• 포인트1: 반복을 도중에 종료하는 방법 - 발견된 경우 요소의 인덱스를 표시하고, 그 시점에서 처리를 종료한다.
• 포인트2: 원하는 값이 발견되지 않았음을 나타내는 방법 - 요소의 인덱스로 사용할 수 없는 값인 -1을 표시한다.

선형 검색(linear search)

임의의 배열에서 특정한 값을 찾는 알고리즘을 말한다. 순차 검색(sequential search) 알고리즘이라고도 한다.

*정렬된 배열일 경우 이진 검색(binary search)을 이용하는 편이 효율적이다.

선형 검색 알고리즘의 개요

1. pos를 -1로 초기화
2. 루프 카운터인 i를 변화시키는 반복을 통해서, a[i]와 x를 비교해 동일한 값이면 pos를 요소 번호인 i로 변경한 후 반복을 종료
3. pos 값을 표시

- 원하는 값이 발견되지 않은 것으로 가정해서 검색을 시작하고, 찾으면 pos(position) 값을 변경하고 종료함.

- 같은 값이 여러 개 있어도, 처음 발견한 시점에 종료하는 것.

보초법(sentinel method)

- 검색 실패 조건을 제거해 판단 횟수를 줄여 선형 검색을 효율화하는 방법.

- 보초법 이용 방법: 배열의 마지막에 보초값을 넣어 검색이 실패하지 않도록 하면 된다.

- 예를 들어 어떤 수(예: 60)를 찾는다고 할 때, 보초법의 값이 없을 때에는 '이 수가 찾는 수인지'와 '여기가 배열의 마지막인지' 두 가지에 대해 판단해야 한다. 그러나 보초법 값이 있을 경우에는 검색하려는 수(60)는 배열의 끝에서 무조건 찾을 수 있으므로 검색 실패의 경우가 사라져 판단해야 할 조건이 줄어든다. 단순하게 봐도 if문이 하나만 필요해지므로 훨씬 효율적이다.

 

선형 검색 문제

- 변수 x와 같은 값을 찾으면 그 인덱스를, 찾지 못하면 -1를 표시하는 프로그램 구현

public class SequentialSearch {
    int searchPosition(int[] arr, int x) {
        int pos = -1;

        for(int i = 0; i < arr.length && pos == -1; i++) { // 원하는 값이 발견되지 않으면 반복
            if(arr[i] == x) {
                pos = i;
                return pos;
            }
        }
        return pos;
    }

    public static void main(String[] args) {
        int[] array = {2, 45, 66, 33, 454, 223, 4453};
        int x = 454;

        SequentialSearch sequentialSearch = new SequentialSearch();
        System.out.println(sequentialSearch.searchPosition(array, x));
    }
}

- 배열의 최댓값 최솟값 구하기

public class MaxAndMinOfArray {
    void searchMaxAndMinOfArray(int[] arr) {
        int max = arr[0]; // 첫 인덱스 값을 임시 최댓값으로 설정
        int min = arr[0]; // 첫 인덱스 값을 임시 최솟값으로 설정

        for(int i=0; i<arr.length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            }
            if(arr[i] < min) {
                min = arr[i];
            }
        }
        System.out.printf("최댓값: %d\n", max);
        System.out.printf("최솟값: %d\n", min);
    }

    public static void main(String[] args) {
        int[] array = {2, 45, 66, 33, 454, 223, 4453};

        MaxAndMinOfArray maxAndMinOfArray = new MaxAndMinOfArray();
        maxAndMinOfArray.searchMaxAndMinOfArray(array);
    }
}