알고리즘 알고가자(1)

배열 요소를 역순으로 정렬하기

배열의 요소를 역순으로 정렬하려면
우선, 배열의 첫 번째 요소(a[0])와 마지막 요소의 값(a[last])을 교환한다.
이어서, 안쪽 요소들을 교환한다
(a[1] <-교환-> a[last-1])
(a[2] <-교환-> a[last-2])
...
이런식으로 교환을 모두 하게되면, 배열은 역순으로 정렬되게 된다.
결국 별을 역순으로 정렬하기 위한 교환 횟수는 요소개수/2 가 되며 이 때, 나눗셈에서 나머지는 버리면 되는데 왜냐하면 요소 개수가 홀수인 경우에 가운데 요소는 교환할 필요가 없기 때문이다.

이제, JAVA 코드를 통해 배열을 역순 정렬하는 메소드를 구현해 보자

void reverse(int [] a){
        for(int i = 0; i < a.length/2; i++){
            int tmp = a[i];
            a[i] = a[a.length-1-i];   
            a[a.length-1-i] = tmp;
        }
    }

*a[a.length-1-i] : 배열의 인덱스는 0 부터 시작한다. 따라서 마지막 요소는 a[a.length] 가 아닌 a[a.length-1]이 된다.

두 배열의 비교

두 배열의 모든 요소의 값이 같은지 비교하는 알고리즘에 대해서 생각해보자

가장 우선, 두 배열 a,b가 같으려면 a, b의 요솟수가 같아야한다.
다음으로 두 배열을 처음부터 스캔하여 a[i] 와 b[i]가 모두 같아야 한다.

이제, JAVA 코드를 통해 두 배열이 같은지 비교하는 메소드를 구현해 보자

 boolean equals(int[] a, int[] b){
        if(a.length != b.length)   
            return false;
        for(int i = 0 ; i < a.length; i++){
            if(a[i] != b[i])
                return false;
        }
        return true;
    }

• 스캔(Scan)
  스캔은 자료구조내의 모든 데이터들을 하나씩 확인하는 작업을 의미한다.