자료구조 - 선형 구조: 배열

배열

자료구조의 복습을 위해 배열부터 다시 시작한다. 만약 이 포스팅을 통해 학습하는 미래 개발자가 있다면, 언어 기초 -> 자료구조 -> 알고리즘 순으로 학습해 효율을 높이는것을 추천한다. 해당 포스팅은 자바를 기준으로 진행한다.

 

---

배열 개요

배열은 동일한 자료형을 Heap 영역내 연속적으로 메모리를 할당해 활용한다. 더 쉽게 표현하면, 하나의 변수에 많은 데이터를 저장하기 위해 사용하는것 이라고 볼 수 있다. 

이해를 돕기위해 프로그래밍 기초 기술의 집약체 계산기로 예시를 한번 살펴보자. 

단순히 숫자 2개를 더해야 하는상황엔 우리는 다음과 같이 프로그래밍을 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String args[]) throws IOException {
    	/*
        1. BufferedReader
        Scanner와 동일한 역할을 한다. 입력받는 양이 많아질수록 효율이 높아진다.
        
        2. InputStreamReader()
        매개 변수로 주어진 입력 바이트를 변환해 버퍼드리더의 생성자의 매개변수로 전달한다.
        
        3. System.in
        키보드를 통해 입력받은 데이터를 바이트로 변환해 InputStreamReader의 매개변수 역할을 한다.
        
        */
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        /*
        1. Integer.parseInt()
        문자열을 int형식으로 변환하기 위한 메서드. java에서 기본적으로 제공한다.
        c언어의 Atoi와 같은 기능을 한다.
        
        2. br.readLine()
        줄을 기준으로 입력받는 메서드. BufferedReader의 메서드다.
        */
        int a = Integer.parseInt(br.readLine());
        int b = Integer.parseInt(br.readLine());
        
        System.out.println(a + b);
    }
}

/*
입력: 
5
4

출력:
9
*/

위와 같이 2개의 수를 더하는 경우는 간편하게 a와 b 변수를 선언해 덧셈이 가능하다. 하지만 100개의 수를 입력받아 더하는 경우엔 변수 100개가 필요하게 된다. 한줄의 선언으로 N개의 변수를 다룰 수 있게 해주는것이 배열이다.

배열을 선언한 덧셈 코드를 보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String args[]) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //int형 배열 10칸 선언
        int[] dArr = new int[10];
        
        for (int index = 0 ; index < 10 ; ++index) {
        	//선언한 int형 배열 dArr의 index번 째 칸에 입력받은 정수를 저장
        	dArr[index] = Integer.parseInt(br.readLine);
        }
        
        int sum = 0;
        
        for (int index = 0 ; index < 10 ; ++index) {
        	//dArr의 index번 째 정수형 데이터를 sum에 누적
        	sum += dArr[index];
        }
        
        System.out.println(sum);
    }
}

/*
입력: 
1
2
3
4
5
6
7
8
9
10

출력:
55
*/

변수를 a부터 j까지 선언하는것 보다 훨씬 직관적으로 코드작성이 가능하다. 이것이 우리가 배열을 사용하는 이유다.

---

배열의 장점

1. 구현이 쉽다.
2. 특정 위치에 접근이 가능하다. ex)7번 째 데이터에 접근하기 = dArr[6];
   즉 빠른 검색을 지원한다.
3. 연속된 메모리 할당으로 인해 참조를 위한 포인터 설정이 필요없다. 즉 추가적인 메모리 할당이 필요없다.
4. 순차적으로 접근하는 경우도 연속된 메모리에 할당되므로 연결 리스트보다 빠른 성능을 자랑한다.

배열의 단점

1. 힙에 연속된 메모리로 미리 할당받기 때문에 배열 크기를 동적으로 변경할 수 없다.
   따라서 필요한양을 미리 계산해서 배열을 할당해야 한다.
2. 삽입 및 삭제 연산이 비효율적이다. 
3. GC를 통해 배열 자체가 사라지지 않는다면, 해당 메모리는 배열이 아닌이상 메모리 활용이 불가능하다.