Array

<자료구조 배열>
배열이라는 자료구조의 개념은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 구조
하나의 타입으로 통일, 연속적 인접 => 밀집 배열

<장접>

1. 배열의 요소는 동일한 크기를 갖으며, 빈틈없이 연속적으로 이어져 있고, 인텍스를 통해 단 한번의 연산으로 임의의 요소에 접근, 시간 복잡도 O(1) => 이는 매우 효율적

2. 메모리 공간의 효율성: 배열은 연속된 메모리 공간에 요소를 저장, 메모리 공간을 효율적 사용 & 요소들은 순서대로 저장하기 때문에, 인접 요소들에 대한 캐시 지역성 까지 좋아 성능 향상에 도움

3. 다차원 배열: 배열은 다차원으로 선언 가능, 행렬과 같은 다차원 데이터 표현 가능

<단점>

1. 크기 제한: 배열은 생성할 때 크기 정함, 변경 불가능. 미리 최대 크기를 예상하고 배열을 생성, 크기를 동적으로 조정할 수는 없음

2. 삽입, 삭제의 어려움: 배열은 요소를 삭제 -> 작업비용 큼.
   배열의 중간에 요소를 삽입하거나 삭제할 경우 해당 위치 이후 요소들을 모두 이동
   따라서 시간 복잡도가 O(n)이 되어 성능 저하

<Java에서 배열 선언 및 사용 방법>

1) 배열 선언 & 초기화
배열을 선언하기 위해서는 배열의 타입과 크기를 지정
int[] numbers = new int[5];

2) 배열에 값 할당
배열에 값을 할당하려면 인덱스를 사용해 특정 위치에 값을 대입
인덱스는 0 부터 배열의 크기보다 1 작은 값 까지 유효
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
numbers[3] = 40;
numbers[4] = 50;

3) 배열값 참조
배열 값을 참조 하기 위해서 index 사용
System.out.println(numbers[3]);

4) 배열의 길이
배열의 길이는 length 속성을 사용하여 알 수 있다.
System.out.println(numbers.length);

5) 배열 반복문
배열에 모든 요소에 접근하기 위해 반복문 사용
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}

+) ArrayList

1) 동적 크기 조정 가능: 내부적으로 배열을 사용하여, 요소를 추가, 삭제 필요에 따라 크기를 동적으로 조정 가능. 크기가 자동으로 조정 -> 크기 제한 X & 유연하게 요소를 관리 할 수 있음

2) 제네릭 타입: 요소의 타입을 지정 가능. 잘못된 타입이 들어오는 것을 막을 수 있다.

3) 요소 접근: 인덱스는 0부터 시작하며, 해당 인덱스에 접그나여 읽거나 변경 가능

4) 요소 추가와 삭제: add 메서드를 사용해 리스트의 끝 부분에 추가, 특정 인덱스에 요소를 삽입
remove 메서드 사용시 특정 인덱스 또는 값에 해당하는 요소 삭제 가능

5) 반복과 순회: for, iterator를 사용하여 순회 가능

단) 요소의 추가/삭제 작업이 빈번이 일어나는 경우 성능 저하 가능성이 있음
따라서 요소의 추가 삭제가 빈번하지 않고 요소의 순차적 접근이 필요한 경우 ArrayList를 활용

참고로 추가/삭제 작업이 많이 일어나는 경우 LinkedList 사용 하는게 더 효율 적일 수도 있다.

배열에 대해 추가적으로 더 알아보겠다.

1. 선형배열
   데이터 요소들이 일렬로 연결 되어 있는 배열
   각 요소들은 인덱스라는 고유한 숫자로 식별, 배열을 선언시 타입과 배열의 길이를 지정
   

2. 비선형 배열
   일렬로 나열하는 것이 아닌 특정 규칙에 따라 구조를 형성
   tree, graph -> 우선 트리는 부모 자식 관계의 노드들이 연결된 구조, 그래프는 노드와 간선 연결

<선형배열, 선형구조, 선형탐색>
선형구조 -> 데이터 일렬 나열 & 데이터간 순서, 논리적 이어져 있는 구조

선형배열과 선형구조
-> 선형 배열의 경우 데이터의 요소들이 일렬로 되어 있는 배열을 의미. 이는 고유한 인덱스로 식별. 선형구조는 일렬로 나열 되어 있을 뿐만 아닌, 데이터 간에 순서가 있고 논리적 식별 가능

즉) 선형 구조에는 선형 배열 포함 & 링크드 리스트, 스택 큐 등 다양한 자료 구조 포함

선형 탐색
-> 배열이나 리스트의 처음부터 끝까지 하나씩 값을 비교

<선형배열과 선형탐색의 관계>
-> 선형배열은 데이터를 일렬로 저장하는 자료구조, 선형탐색의 경우 선형 배열을 이용하여 처음부터 끝가지 순서대로 탐색

<선형 구조, 배열, 탐색의 관계>
선형구조와 배열의 경우 -> 자료구조 이는 알고리즘
선형 구조 내에는 선형 배열이 존재.

<선형 배열의 종류>

1. 일반배열 (Array)
   고정된 크기를 가지며 동일한 데이터 타입만 저장
   

메서드 설명
clone(): 배열의 복사본을 생성
length: 배열의 길이를 반환
sort(): 배열을 정렬
fill(): 배열의 모든 요소를 특정 값으로 초기화
binarySearch(): 이진 검색을 수행하여 배열에서 지정된 값의 인덱스를 반환
equals(): 배열이 지정된 객체와 같은지 여부를 확인
toString(): 배열의 문자열 표현을 반환

2. 가변배열(ArrayList)
   

메서드 설명
add(): ArrayList에 요소를 추가
addAll(): 지정된 컬렉션의 모든 요소를 ArrayList에 추가
remove(): ArrayList에서 지정된 요소를 제거
removeAll(): 지정된 컬렉션의 모든 요소를 ArrayList에서 제거
contains(): ArrayList가 지정된 객체를 포함하는지 여부를 확인
indexOf(): ArrayList에서 지정된 객체의 인덱스를 반환
size(): ArrayList의 요소 수를 반환

3. 연결 리스트
   

메서드 설명
add(): LinkedList에 요소를 추가
addFirst(): LinkedList의 맨 앞에 요소를 추가
addLast(): LinkedList의 맨 뒤에 요소를 추가
remove(): LinkedList에서 지정된 요소를 제거
removeFirst(): LinkedList의 첫 번째 요소를 제거
removeLast(): LinkedList의 마지막 요소를 제거
contains(): LinkedList가 지정된 객체를 포함하는지 여부를 확인
get(): LinkedList에서 지정된 인덱스에 해당하는 요소를 반환

<Array와 관련된 문제를 풀어봄>

백준 문풀

<참고>
Array는 좀더 새밀하게 다뤄야 할 것 같아 2탄, 3탄도 올려야 할 듯... 하다