[PCCP] 자료구조 - 배열

1. 이론

- 배열: 동일한 타입의 데이터를 그룹화하여 관리. 연속된 메모리 할당. 인덱스와 값을 일대일 대응해 관리하는 자료구조

- 특징: 임의 접근으로 O(1)에 탐색 가능

 

(시간복잡도)

- 임의 접근: O(1)

- 삽입: 맨 앞 O(N), 중간 O(N), 맨 뒤 O(1)

- 삭제: 맨 뒤 O(1)

 

(선택시 고려할 점)

- 할당 가능한 메모리 크기 확인: (1차원) 1,000만개/(2차원) 3000X3000 개

- 중간에 데이터 삽입 횟수 여부

 

2. 프로그램 언어별 문법

- 배열 선언 및 초기화(1차원/2차원)

- 삽입(맨앞, 중간, 맨뒤) / 삭제(맨앞, 중간, 맨뒤) / 변경 / 탐색(조회)

- 크기

 

<C언어>

// 1차원 배열 선언 및 초기화
int arr1[10];
int arr2[3] = {1, 2, 3};

// 값 변경
arr2[1] = 10;

// 값 확인
printf("%d\n", arr2[0]);

// 전체 배열값 조회
for (int i = 0; i < 3; ++i) {
    printf("%d ", arr2[i]);
}

// 2차원 배열 선언 및 초기화
int arr3[2][2];
int arr4[2][3] = {{1, 2, 3}, {4, 5, 6}};

// 값 변경
arr4[1][2] = 10;

// 값 확인
printf("%d\n", arr4[0][0]);

// 전체 배열값 조회
for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 3; ++j) {
        printf("%d ", arr4[i][j]);
    }
    printf("\n");
}

 

<C++>

(정적 배열)

/* 1차원 배열 선언 및 초기화 */
int arr[개수];             // 쓰레기값으로 초기화
int arr[개수] = {};         // 0으로 초기화
int arr[개수] = {값1, 값2, 값3};  // 나머지는 0으로 초기화
int arr[개수]{값1, 값2, 값3};     // C++11부터 사용 가능

/* 1차원 배열 삽입 */

/* 1차원 배열 삭제 */

/* 1차원 배열 변경 */
arr[인덱스] = 값;

/* 1차원 배열 조회 */
arr[인덱스];

/* 1차원 배열 탐색 */


/* 1차원 배열 전체 조회 */
for (int i=0; i < 10; ++i)
    std::cout << arr[i] << " " << std::endl;
    
    
/* 2차원 배열 선언 및 초기화 */
int arr[열개수][행개수];         // 쓰레기값으로 초기화
int arr[열개수][행개수] = {};    // 0으로 초기화
int arr[열개수][행개수] = {{값1, 값2, 값3, 값4}, {값5, 값6, 값7}};  // 나머지는 0으로 초기화

/* 삽입 */

/* 삭제 */

/* 변경 */
arr[열][행] = 값;

/* 조회 */
arr[열][행];

/* 탐색 */

/* 전체 조회 */
for (int i = 0; i < 행크기; ++i) {
    for (int j = 0; j < 열크기; ++j) {
        std::cout << arr[i][j] << " ";
    }
    std::cout << std::endl;
}

(동적 배열): 메모리 할당 해제 필수!!

/* 1차원 동적배열 선언 및 초기화 */
int *arr = new int[크기];
int *arr = new int[크기](); // 0으로 초기화. c++ 11 이후
int *arr = new int[크기]{값1, 값2, 값3, 값4}; // 명시적으로 크기 설정 필수. c++ 11 이후

/* 1차원 동적배열 할당 해제(필수) */
delete[] arr;

/* 1차원 동적배열 삽입 */

/* 1차원 동적배열 삭제 */

/* 1차원 동적배열 변경 */
arr[인덱스] = 값;

/* 1차원 동적배열 조회 */
arr[인덱스];

/* 1차원 동적배열 탐색 */

/* 1차원 동적배열 전체 조회 */
for (int i=0; i < 10; ++i)
    std::cout << arr[i] << " " << std::endl;


/* 2차원 동적배열 선언 및 초기화 */
int** arr = new int*[행개수];       // 쓰레기값으로 초기화
for(int i = 0; i < 행개수; i++)
    arr[i] = new int[열개수];

/* 2차원 동적배열 할당 해제(필수) */
for(int i=0; i<행개수; i++)
	delete[] arr[i];
delete[] arr;

/* 2차원 동적배열 삽입 */

/* 2차원 동적배열 삭제 */

/* 2차원 동적배열 변경 */
arr[열][행] = 값;

/* 2차원 동적배열 조회 */
arr[열][행];

/* 2차원 동적배열 탐색 */

/* 2차원 동적배열 전체 조회 */
for (int i = 0; i < 행크기; ++i) {
    for (int j = 0; j < 열크기; ++j) {
        std::cout << arr[i][j] << " ";
    }
    std::cout << std::endl;
}

(가변 배열: vector)

- 1차원 배열

#include <vector>

/* 1차원 vector 선언 및 초기화 */
vector<자료형> vec;
vector<자료형> vec(크기);
vector<자료형> vec(크기, 값);
vector<자료형> vec = {값1, 값2, 값3};

/* 삽입 */
vec.insert(반복자, 값); // 해당 위치 요소 삽입
vec.insert(인덱스, 값); // 해당 위치 요소 삽입. 삽입한 곳의 반복자 반환
vec.insert(인덱스, 개수, 값) // 해당 위치에 정해진 개수만큼 값 삽입
vec.push_back(값); // 맨 뒤 사입. O(1)

/* 삭제 */
vec.erase(반복자); // 해당 위치 요소 삭제
vec.pop_back(); // 맨 뒤 요소 삭제

/* 변경 */
vec[인덱스] = 값;

/* 조회 */
vec.front(); // 맨 앞 값 조회
vec[인덱스];
vec.at(인덱스);
vec.back(); // 맨 뒤 값 조회

/* 탐색 */
vector<자료형>::iterator = find(vec.begin(), vec.end(), 값);

if (it != vec.end())
    std::cout << "find" << std:end;
else
    std::cout << "not exist" << std::endl;

/* 전체 조회 */
for (auto v : vec)
    std::cout << v << std::endl;

/* 기타 메서드 */
vec.size(); // vec에 실제로 들어있는 요소 개수
vec.empty(); // 비어있다면 true 반환
vec.capacity(); // vec에 할당된 공간수
vec.resize(크기, 값); // 크기를 변경. 값으로 초기화
vec.reserve(크기); // vec 용량을 크기만큼 늘림. 불필요한 메모리 재할당 방지
vec.clear(); // 모든 요소 제거. size는 0, capacity 유지

- 2차원 배열

#include <vector>

/* 2차원 vector 선언 및 초기화 */
vector<vector<자료형>> vec;
vector<vector<자료형>> vec(행개수, vector<자료형>(열개수, 값)); // 해당 값으로 행렬 초기화


/* 삽입 */
vec.push_back(vector<자료형>()); // 맨 뒤에 행 삽입
vec[행].insert(반복자, 값); // 해당 행, 열에 값 삽입
vec[행].push_back(값); // 해당 행의 맨 뒤에 값 삽입


/* 삭제 */
vec[행].erase(반복자); // 해당 위치 요소 삭제
vec[행].pop_back(); // 해당 행의 맨 뒤 요소 삭제

/* 변경 */
vec[행][열] = 값;

/* 조회 */
vec[행].front(); // 해당 행의 0번쨰 열 조회
vec[행][열];
vec.at(행).at(열);
vec[행].back(); // 해당 행의 마지막 열 조회

/* 탐색 */


/* 전체 조회 */
for (auto row : vec)
    for (auto v : row)
        std::cout << v << std::endl;

 

<C#>

 

 

<Java>

- 배열: 처음 선언시 배열의 크기 결정

- Java에서는 1차원 배열이 하나의 객체이므로 2차원 배열은 1차원 배열 객체가 여러개 있는 것. 메모리가 반드시 연속적이지 않을 수 있음

- sort() API는 O(NlogN). Dual-Pivot QuickSort 혹은 Time-Sort

// 1차원 배열 선언 및 초기화
int[] arr1 = {0, 1, 2, 3};
int[] arr2 = new int[5];
int[] arr3 = new int[3]{1, 2, 3};
int[] arr4 = arr1.clone(); // 배열을 복사하여 새로운 배열 생성

// 값 변경

// 값 확인

// 배열 전체 조회

// 2차원 배열 선언 및 초기화
int[][] arr3 = new int[2][3];
int[][] arr4 = {{1, 2, 3}, {4, 5, 6}};

// 값 변경
arr[0][0] = 10;

// 값 확인
System.out.println(arr[0][1];)

// 배열 길이
arr.length;

// 정렬(원본 배열 정렬)
Arrays.sort(배열);

// String으로 반환
Arrays.toString(배열);

 

<Python>

# 1차원 배열 생성
arr1 = []
arr2 = list()
arr3 = [0 for _ in range(N)]

# 2차원 배열 생성
arr4 = [i+j for i in range(2) for j in range(3)]
arr5 = [None for _ in range(2) for _ in range(3)]

# 맨 끝 추가
arr.append(val)

# 확장
arr.extend(list)

# 위치 삽입
arr.insert(idx, val)

# 값 변경
arr[idx] = val

# 값 접근
arr[idx]

# 삭제
del arr[idx]

# 가장 먼저 등장하는 val과 동일한 값 삭제
arr.remove(val)

# 해당 위치 반환 후 제거
arr.pop(idx)

# 복사
arr[start:end:step]

# 전체 배열 확인
for i in arr3:
    print(i)

for i in range(len(arr3)):
    print(arr3[i])

 

<Javascript>

// 배열 선언 및 초기화
let arr1 = new Array(10);
let arr2 = new Array(1,2,3,"Hello");
let arr3 = [1, 2, 3, "Hello"];


// 삽입
arr3.push(val);

// 삭제


// 값 확인


// 탐색

 

 

3. 추천 문제

(프로그래머스)

- Lv1: 두 개 뽑아서 더하기(68644) / 두 개 뽑아서 더하기(68644) 해설

- Lv1 : 모의고사(42840) / 모의고사(42840) 해설
- Lv2 : 행렬의 곱셈(12949) / 행렬의 곱셈(12949) 해설
- Lv1 : 실패율(42889) / 실패율(42889) 해설
- Lv2 : 방문 길이(49994) / 방문 길이(49994) 해설

 

- Lv 0 : 배열의 평균값(120817) / 배열의 평균값(120817) 해설
- Lv 0: 배열 뒤집기(120821) / 배열 뒤집기(120821) 해설
- Lv 2: N^2 배열 자르기(87390) / N^2 배열자르기(87390) 해설
- Lv 1: 나누어 떨어지는 숫자 배열(12910) / 나누어 떨어지는 숫자 배열(12910) 해설

 

(leetcode)

-