기본 자료구조 - 배열이란

자료구조 정의하기.

배열을 공부하기 위해서 자료구조가 무엇인지 간단히 알아야 합니다.
자료구조란 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
쉽게 말해 자료를 효율적으로 사용할 수 있도록 컴퓨터에게 저장하는 방법을 말합니다.

자료구조는 데이터를 효율적으로 조직화하고 저장하고 처리하는 방법을 다루는 컴퓨터 과학의 학문 분야이며
데이터의 특성과 연산의 효율성을 고려하여 데이터를 구성하고 저장하는 방법을 설계하며, 데이터의 접근, 삽입, 삭제, 검색 등의 연산을 수행하기 위한 알고리즘을 개발합니다.

자료구조는 다양한 형태로 구현될 수 있으며, 각각의 자료구조는 특정한 상황에서 효율적인 동작을 보장합니다. 예를 들어, 배열은 데이터에 연속적인 메모리 공간을 할당하여 인덱스를 통해 데이터에 접근하는데 효율적이지만, 삽입 또는 삭제 연산이 빈번하게 발생하는 경우에는 비효율적일 수 있습니다. 이에 반해 연결 리스트는 각각의 노드가 데이터와 다음 노드를 가리키는 링크로 연결되어 있어 데이터의 삽입과 삭제가 유연하게 이루어질 수 있지만, 특정 위치의 데이터에 접근하는 데는 추가적인 연산이 필요합니다.

자료구조의 선택은 데이터의 특성과 예상되는 연산의 종류와 빈도에 따라 결정됩니다. 효율적인 자료구조 선택은 데이터의 처리 속도와 메모리 사용량에 영향을 미치며, 알고리즘의 성능을 크게 좌우할 수 있습니다. 따라서 프로그램의 목적과 요구사항을 고려하여 적합한 자료구조를 선택하는 것이 중요합니다.

 

배열 다루기.

배열(Array)은 동일한 자료형의 데이터를 일렬로 나열한 자료구조입니다. 배열은 고정된 크기를 가지며, 각각의 데이터는 인덱스(index)를 통해 접근됩니다. 인덱스는 배열의 시작 위치로부터 각 데이터의 상대적인 위치를 나타냅니다.

배열은 메모리 상에서 연속적인 공간에 데이터를 저장하므로 데이터에 빠르게 접근할 수 있습니다. 또한 인덱스를 이용하여 특정 위치의 데이터에 상수 시간(O(1))에 접근할 수 있습니다. 이러한 특징 때문에 배열은 데이터를 순차적으로 접근하는 작업에 유용합니다.

배열은 선언 시에 크기를 지정하고, 크기는 변경할 수 없습니다. 즉, 배열의 크기는 고정되어 있으며, 크기를 초과하여 데이터를 저장하려면 새로운 배열을 생성하여 데이터를 복사해야 합니다. 이러한 제약 사항은 배열의 활용을 제한할 수 있습니다.

배열은 다양한 프로그래밍 언어에서 지원되며, 많은 알고리즘과 자료구조의 기반이 됩니다. 배열은 데이터의 순서를 유지하고, 인덱스를 통해 빠른 접근이 필요한 경우에 주로 사용됩니다. 또한 다차원 배열을 이용하여 행렬과 같은 복잡한 구조를 표현할 수도 있습니다.

 

• 5명의 학생의 점수를 담는 배열을 만들어 보고 그림으로 이해해 봅시다.

int[] scores;
scores = new int[5]; // 배열 본체를 생성한 뒤 배열 변수 scores 와 연결

 

• 인덱스 식과 구성 요소와 배열 본체 길이

배열 본체 안의 구성 요소에 접근하려면 정수형 인덱스를 연산자 [ ] 안에 넣은 인덱스 식을 이용합니다.
배열의 길이는 length 메서드를 이용해 확인 할 수 있습니다.

int[] scores;
scores = new int[5]; // 배열 본체를 생성한 뒤 배열 변수 scores 와 연결
int[] otherScores = {90, 95, 80, 85, 0}; // 생성시 값을 할당해 초기화


scores[0] = 90; // 0번째 인덱스에 90을 대입
scores[1] = scores[0] + 5; // 1번째 인덱스에 scores[0] + 5 대입
System.out.println(scores[0]); // 90
System.out.println(scores.length); // 5

 

• 기본 값

scores 배열의 값을 반복문을 통해 출력해보면 90, 95, 0, 0, 0 을 확인할 수 있습니다.
값을 대입해 주지 않은 요소는 int 타입의 기본 값인 0으로 초기화되어 있습니다.

for (int i = 0; i < scores.length; i++) {
    System.out.printf(scores[i] + " "); // 90 95 0 0 0
}

 

byte, short, int, long 타입은 0
float, double 은 0.0
boolean 은 false
char 는 '\u0000', null
참조형 데이터 타입은 null 으로 기본 값이 생성됩니다.

 

배열 요소의 최댓값 구하기.

배열 요소가 3개 있다고 가정하고 그중 최댓값을 구하는 코드는 아래와 같습니다.

int[] numbers = {1, 100, 10};
int max = numbers[0];
        
if (max < numbers[1]) {
    max = numbers[1];
}

if (max < numbers[2]) {
    max = numbers[2];
}
System.out.println(max); // 100

만약 배열의 요소가 4, 5, ... 100개 까지 늘어난다면
조건에 따른 조건문을 다 작성해야 합니다.
이럴때 반복문을 통해 max 값을 찾을 수 있게 구현할 수 있습니다.
이렇게 배열 요소를 하나식 차례로 조사하는 과정을 스캔이라고 합니다.

int[] nums = {1, 2, 3, 4, 5};
int maxNumber = nums[0];

for (int i = 1; i < nums.length; i++) {
     if (maxNumber < nums[i]) {
     maxNumber = nums[i];
     }
}

System.out.println(maxNumber); // 5

 

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

배열 2, 5, 1, 3, 9, 6, 7 을 역순으로 정렬하면 7, 6, 9, 3, 1, 5, 2 가 됩니다.
이는 양쪽 끝을 차례대로 바꿔주면 됩니다.
그렇기 때문에 배열 길이의 중간까지만 반복해주면 되고
양 쪽 끝의 값을 변경해줄 메서드를 구현해주면 원하는 결과를 얻을 수 있습니다.

import java.util.Arrays;

public class ReversedArrayTest {
    static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

    static void reversedArray(int[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            swap(arr, i, arr.length - i -1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 1, 3, 9, 6, 7};
        reversedArray(arr);
        System.out.println(Arrays.toString(arr));
        // [7, 6, 9, 3, 1, 5, 2]
    }
}

import java.util.Arrays;

public class ReversedArrayTest {
    // 배열의 합 메서드
    static int sumOf(int[]arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return sum;
    }

    // 새로운 배열에 모든 요소를 복사하는 메서드
    static void copyOf(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }
    }

    // 새로운 배열에 arr 의 역순으로 복사하는 메서드
    static void reverseCopy(int[] a, int[] b) {
        for (int i = 0; i < a.length ; i++) {
            b[i] = a[a.length - 1 - i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 1, 3, 9, 6, 7};

        System.out.println(sumOf(arr)); // 33

        int[] b = new int[arr.length];
        copyOf(arr, b);
        System.out.println(Arrays.toString(b)); // [2, 5, 1, 3, 9, 6, 7]

        int[] c = new int[arr.length];
        reverseCopy(arr, c);
        System.out.println(Arrays.toString(c));
    }
}