Array

CHOYEAH·2023년 10월 31일

자료구조

배열이란?

배열은 데이터를 나열하고, 각 데이터를 인덱스(메모리주소)에 대응하도록 구성한 데이터 구조.

장점

메모리 효율성: 배열은 동일한 타입의 데이터를 저장할 때 메모리 공간을 효율적으로 사용합니다. 연속적인 메모리 블록에 데이터가 저장되기 때문에 메모리 관리가 용이합니다.
- 배열이 같은 자료형에만 효율적인 이유
  1. 메모리 연속성: 배열은 연속된 메모리 블록에 데이터를 저장합니다. 같은 자료형의 데이터를 저장하면 각 요소의 크기가 동일하기 때문에 인덱스 계산이 간단해집니다. 이를 통해 배열의 원소에 빠르게 접근할 수 있습니다. 만약 배열에 서로 다른 자료형의 데이터가 섞여 있다면, 각 요소의 크기가 일정하지 않아 인덱싱 과정이 복잡해지고 느려질 수 있습니다.
  2. 형식 안정성: 프로그래밍 언어 중 일부는 형식 안정성(type safety)을 중요시합니다. 같은 자료형의 데이터만 저장하는 배열은 형식 안정성을 보장합니다. 이를 통해 프로그램이 예상치 못한 오류나 형 변환 문제로부터 보호받을 수 있습니다.
  3. 코드 가독성 및 유지 보수: 같은 자료형의 데이터를 저장하는 배열은 코드를 읽고 이해하기 쉽게 만들어 줍니다. 이는 개발자가 코드를 작성하고 수정하는 데 도움이 되며, 유지 보수에도 유리합니다.
  하지만 모든 프로그래밍 언어와 상황에서 같은 자료형의 데이터만 효율적인 것은 아닙니다. 일부 프로그래밍 언어에서는 다양한 자료형을 함께 저장하는 배열이나 다른 자료 구조를 제공합니다. 예를 들어, Python의 리스트(list)는 서로 다른 자료형의 데이터를 함께 저장할 수 있습니다. 이런 경우에는 배열의 효율성이 상대적으로 떨어질 수 있으며, 여러 자료형을 함께 저장할 수 있는 자료 구조를 사용하는 것이 더 적합할 수 있습니다.
빠른 접근 속도: 배열의 인덱스를 이용해 데이터에 빠르게 접근할 수 있습니다. 이는 상수 시간(constant time)에 데이터를 찾을 수 있게 해줍니다.
쉬운 구현: 배열은 프로그래밍 언어에서 기본적으로 제공되는 자료 구조로, 사용하기 간편하고 코드를 작성하는 데 도움이 됩니다.

단점:

고정된 크기: 배열의 크기는 선언할 때 결정되며, 나중에 크기를 변경하기 어렵습니다. 따라서 배열의 크기를 늘리거나 줄이려면 새 배열을 생성하고 데이터를 복사해야 합니다.
메모리 낭비: 배열에 할당된 메모리 공간이 모두 사용되지 않을 경우 메모리 낭비가 발생할 수 있습니다. 배열의 크기를 예측하기 어려운 상황에서는 이러한 문제가 더욱 심각해집니다.
삽입 및 삭제 비효율성: 배열에서 데이터를 삽입하거나 삭제할 때 다른 요소들을 이동시켜야 하는 경우가 많습니다. 이로 인해 선형 시간(linear time)이 소요되며, 작업량이 많아질수록 비효율적입니다.

적합한 상황:

데이터의 개수가 고정되어 있거나 예측 가능한 경우
데이터 접근이 빈번하게 발생하고 삽입, 삭제 작업이 적은 경우
동일한 데이터 타입의 요소를 연속적인 메모리 공간에 저장해야 하는 경우

부적합한 상황:

데이터의 개수가 불확실하거나 동적으로 변하는 경우
데이터 삽입 및 삭제 작업이 빈번한 경우
다양한 데이터 타입을 함께 저장하고 싶은 경우

배열이 부적합한 경우에는 다음과 같은 자료 구조를 고려할 수 있습니다.

연결 리스트 (LinkedList): 데이터의 개수가 불확실하거나 동적으로 변하는 경우, 연결 리스트를 사용하면 메모리 낭비를 줄이고 동적으로 크기를 조절할 수 있습니다. 하지만 인덱스를 사용한 빠른 접근이 어려워집니다.
스택 (Stack) 또는 큐 (Queue): 데이터 삽입 및 삭제 작업이 빈번한 경우 스택이나 큐를 사용하면 더 효율적입니다. 이러한 자료 구조는 삽입 및 삭제 작업에 특화되어 있어 배열보다 더 빠르게 처리할 수 있습니다.
딕셔너리 (Dictionary) 또는 해시 테이블 (HashTable): 다양한 데이터 타입을 함께 저장하고 싶은 경우 딕셔너리나 해시 테이블을 사용할 수 있습니다. 이러한 자료 구조는 키-값 쌍으로 데이터를 저장하며, 키를 사용해 빠르게 데이터에 접근할 수 있습니다.

주의사항:

배열을 사용할 때 주의해야 할 몇 가지 사항이 있습니다. 이러한 사항들을 고려하지 않으면 프로그램의 성능이 저하되거나 오류가 발생할 수 있습니다.

인덱스 범위: 배열의 인덱스는 0부터 시작하여 배열 크기보다 작은 정수로 제한됩니다. 이 범위를 벗어나는 인덱스에 접근하려고 하면 인덱스 범위 초과 오류(Index out of range)가 발생할 수 있습니다. 인덱스를 사용하여 배열 요소에 접근할 때 인덱스 범위를 항상 확인해야 합니다.
고정된 크기: 배열의 크기는 생성 시 고정되며, 나중에 크기를 변경할 수 없습니다. 동적으로 크기가 변경되어야 하는 경우에는 연결 리스트나 동적 배열을 사용하는 것이 더 적합합니다.
- 동적배열 동적 배열(dynamic array)은 크기를 실행 중에 변경할 수 있는 배열입니다. 동적 배열은 메모리를 할당받아 초기 크기를 설정한 후, 필요에 따라 크기를 늘리거나 줄일 수 있습니다. 이를 통해 데이터의 삽입, 삭제, 조회 등의 작업을 유연하게 수행할 수 있습니다. 동적 배열은 내부적으로 일반 배열을 사용하며, 크기 변경이 필요할 때마다 새로운 메모리 영역에 적절한 크기의 배열을 할당한 다음, 기존 데이터를 복사합니다. 이후 기존 배열이 차지하던 메모리를 해제하여 메모리 누수를 방지합니다. 동적 배열의 장점:
  1. 크기 변경 가능: 실행 중에 배열 크기를 동적으로 변경할 수 있어, 메모리 사용 효율이 높아집니다.
  2. 삽입 및 삭제 효율성: 동적 배열은 크기 변경을 통해 중간 위치에 데이터 삽입 및 삭제 작업을 비교적 효율적으로 수행할 수 있습니다.
    
    동적 배열의 단점:
  3. 크기 변경 시 오버헤드: 배열 크기를 변경할 때마다 메모리를 할당하고 복사하는 과정에서 오버헤드가 발생합니다. 이러한 오버헤드는 상황에 따라 성능 저하로 이어질 수 있습니다.
    - 오버헤드 오버헤드(overhead)란, 컴퓨터 시스템에서 작업을 수행하는 데 필요한 추가적인 자원이나 작업 시간을 의미합니다. 오버헤드는 특정 작업을 완료하기 위해 필요한 처리 과정 외에 발생하는 부가적인 비용으로, 시스템의 성능이나 효율성에 영향을 줄 수 있습니다.
  4. 메모리 단편화: 동적 배열의 크기 변경으로 인해 메모리 단편화가 발생할 수 있습니다. 이는 시간이 지남에 따라 메모리 사용 효율이 떨어지게 할 수 있습니다.
    
    동적 배열은 크기 변경이 필요한 작업에 적합한 자료구조입니다. 예를 들어, 언어에서 제공하는 ArrayList(Java)나 vector(C++) 등의 구현이 동적 배열을 사용합니다. 실행 중에 크기가 변경되어야 하는 경우에는 동적 배열이 일반 배열보다 더 효율적인 선택이 될 수 있습니다.
메모리 낭비: 배열은 고정된 크기를 가지므로, 사용하지 않는 공간에 대한 메모리가 낭비될 수 있습니다. 배열의 크기를 적절하게 선택하거나, 공간 효율성이 높은 다른 자료구조를 사용하여 이 문제를 해결할 수 있습니다.
데이터 삽입 및 삭제: 배열에서 중간 위치에 데이터를 삽입하거나 삭제하려면, 해당 위치 이후의 모든 요소를 이동해야 합니다. 이로 인해 배열에서의 삽입 및 삭제 작업은 비효율적입니다. 이 경우 연결 리스트와 같은 자료구조를 사용하는 것이 더 효율적일 수 있습니다.
멀티스레드 환경에서의 동기화: 멀티스레드 환경에서 배열을 사용할 때는 동시성 문제를 고려해야 합니다. 여러 스레드가 동시에 배열에 접근하면 데이터의 무결성이 깨질 수 있습니다. 이를 방지하기 위해 동기화 기법을 사용하여 스레드 간의 작업 순서를 제어해야 합니다.

따라서 배열의 장점과 단점을 고려하여, 특정 상황에서 가장 적합한 자료 구조를 선택하는 것이 중요합니다. 배열은 동일한 타입의 데이터에서 빠른 데이터 접근이 필요하거나 메모리를 효율적으로 사용해야 하는 상황에 적합하며, 그 외 상황에서는 다른 자료 구조를 사용하는 것이 더 효과적일 수 있습니다.

배열 구현

#include <stdio.h>

int main(int argc, char * argv[])
{
    char country[3] = "US"; // 마지막 빈공간은 데이이터의 끝을 의미  
    printf ("%c%c\n", country[0], country[1]);
    printf ("%s\n", country);    
    return 0;
}

Python

# 1차원 배열: 리스트로 구현시
data_list = [1, 2, 3, 4, 5]
data_list
# [1, 2, 3, 4, 5]

# 2차원 배열: 리스트로 구현시
data_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
data_list
# [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

print (data_list[0])
print (data_list[0][0])
print (data_list[0][1])
print (data_list[0][2])
print (data_list[1][0])
print (data_list[1][1])
# [1, 2, 3]
# 1
# 2
# 3
# 4
# 5

// 1차원 배열: 배열로 구현
let data_list = [1, 2, 3, 4, 5];
console.log(data_list);
// [1, 2, 3, 4, 5]

// 2차원 배열: 배열로 구현
data_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log(data_list);
// [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

console.log(data_list[0]);
console.log(data_list[0][0]);
console.log(data_list[0][1]);
console.log(data_list[0][2]);
console.log(data_list[1][0]);
console.log(data_list[1][1]);
// [1, 2, 3]
// 1
// 2
// 3
// 4
// 5

// Array 클래스 정의
class Array {
  data = {};
  length = 0;

  // 배열의 특정 인덱스에 해당하는 값을 반환하는 메서드
  get(index) {
    return this.data[index];
  }

  // 배열의 마지막에 새로운 요소를 추가하는 메서드
  push(data) {
    this.data[this.length] = data;
    this.length++;
  }

  // 배열의 마지막 요소를 삭제하고 해당 요소를 반환하는 메서드
  pop() {
    if (this.isEmpty()) {
      console.error("Error: Cannot pop from an empty array.");
      return;
    }
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }

  // 배열의 특정 인덱스에 해당하는 값을 삭제하고 해당 요소를 반환하는 메서드
  remove(index) {
    console.log(`Removed item at index ${index}:`, this.data[index]);
    if (this.isEmpty()) {
      console.error("Error: Cannot remove an item from an empty array.");
      return;
    }
    if (!this.isExistItem(index)) {
      console.error(
        `Error: Item at index ${index} does not exist. Check the index value.`
      );
      return;
    }

    delete this.data[index];
    this.shift(index);
  }

  // 배열의 특정 인덱스부터 끝까지 요소들을 왼쪽으로 한 칸씩 이동시키는 메서드
  shift(index) {
    for (let i = index; i < this.length -1; i++) {
      this.data[i] = this.data[i + 1]; // 지운 아이템 인덱스에 다음 아이템 넣기
    }

    delete this.data[this.length - 1]; // 오른쪽 맨 마지막 아이템 제거
    this.length--;
  }

  // 어레이가 비어있는지 확인하는 메서드
  isEmpty() {
    return this.length === 0;
  }

  // 배열에 아이템이 있는지 확인하는 인덱스
  isExistItem(index) {
    return this.data.hasOwnProperty(index);
  }
}

// Array 클래스 인스턴스 생성
const myArray = new Array();

// 배열 요소 추가
myArray.push("Apple");
myArray.push("Banana");
myArray.push("Cherry");
myArray.push("Choyeah");
myArray.push("Jun");
myArray.push("Min");
console.log("print", myArray);

// 배열 요소 출력
console.log(myArray.get(0)); // 'Apple'
console.log(myArray.get(1)); // 'Banana'
console.log(myArray.get(2)); // 'Cherry'
console.log(myArray.get(3)); // 'Choyeah'
console.log(myArray.get(4)); // 'Jun'
console.log(myArray.get(5)); // 'Min'

// 배열 요소 삭제
myArray.remove(1);
console.log("print", myArray);

// 배열 요소 삭제
myArray.remove(4);
console.log("print", myArray);

// 배열 요소 삭제
myArray.remove(6);
console.log("print", myArray);

// 배열 요소 삭제
myArray.remove(0);
console.log("print", myArray);

// 팝
myArray.pop();
console.log("print", myArray);

// 팝
myArray.pop();
console.log("print", myArray);

// 팝
myArray.pop();
console.log("print", myArray);

// 팝
myArray.pop();
console.log("print", myArray);

// get, set, pop, remove, shift

연습문제

배열에서 특정 문자의 빈도수 구하기

Python

dataset = ['Braund, Mr. Owen Harris',
'Cumings, Mrs. John Bradley (Florence Briggs Thayer)',
'Heikkinen, Miss. Laina',
'Futrelle, Mrs. Jacques Heath (Lily May Peel)',
'Allen, Mr. William Henry',
'Moran, Mr. James',
'McCarthy, Mr. Timothy J',
'Palsson, Master. Gosta Leonard',
'Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)',
'Nasser, Mrs. Nicholas (Adele Achem)',
'Sandstrom, Miss. Marguerite Rut',
'Bonnell, Miss. Elizabeth',
'Saundercock, Mr. William Henry',
'Andersson, Mr. Anders Johan',
'Vestrom, Miss. Hulda Amanda Adolfina',
'Hewlett, Mrs. (Mary D Kingcome) ',
'Rice, Master. Eugene',
'Williams, Mr. Charles Eugene',
'Vander Planke, Mrs. Julius (Emelia Maria Vandemoortele)',
'Masselmani, Mrs. Fatima',
'Fynney, Mr. Joseph J',
'Beesley, Mr. Lawrence',
'McGowan, Miss. Anna "Annie"',
'Sloper, Mr. William Thompson',
'Palsson, Miss. Torborg Danira',
'Asplund, Mrs. Carl Oscar (Selma Augusta Emilia Johansson)',
'Emir, Mr. Farred Chehab',
'Fortune, Mr. Charles Alexander',
'Dwyer, Miss. Ellen "Nellie"',
'Todoroff, Mr. Lalio']

m_count = 0
for data in dataset:
    for index in range(len(data)):
        if data[index] == 'M':
            m_count += 1
print (m_count)
# 38

range(stop): range(10)은 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

range(start, stop): range(1, 11)은 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

range(start, stop, step): range(0, 20, 2)은 0, 2, 4, 6, 8, 10, 12, 14, 16, 18

start, stop, step은 음수로도 지정 가능

JS

  const dataset = [
    "Braund, Mr. Owen Harris",
    "Cumings, Mrs. John Bradley (Florence Briggs Thayer)",
    "Heikkinen, Miss. Laina",
    "Futrelle, Mrs. Jacques Heath (Lily May Peel)",
    "Allen, Mr. William Henry",
    "Moran, Mr. James",
    "McCarthy, Mr. Timothy J",
    "Palsson, Master. Gosta Leonard",
    "Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)",
    "Nasser, Mrs. Nicholas (Adele Achem)",
    "Sandstrom, Miss. Marguerite Rut",
    "Bonnell, Miss. Elizabeth",
    "Saundercock, Mr. William Henry",
    "Andersson, Mr. Anders Johan",
    "Vestrom, Miss. Hulda Amanda Adolfina",
    "Hewlett, Mrs. (Mary D Kingcome) ",
    "Rice, Master. Eugene",
    "Williams, Mr. Charles Eugene",
    "Vander Planke, Mrs. Julius (Emelia Maria Vandemoortele)",
    "Masselmani, Mrs. Fatima",
    "Fynney, Mr. Joseph J",
    "Beesley, Mr. Lawrence",
    'McGowan, Miss. Anna "Annie"',
    "Sloper, Mr. William Thompson",
    "Palsson, Miss. Torborg Danira",
    "Asplund, Mrs. Carl Oscar (Selma Augusta Emilia Johansson)",
    "Emir, Mr. Farred Chehab",
    "Fortune, Mr. Charles Alexander",
    'Dwyer, Miss. Ellen "Nellie"',
    "Todoroff, Mr. Lalio",
  ];
  
  function countChar(dataset, char) {
    let count = 0;
    for (let row of dataset) {
      for (let i = 0; i < row.length; i++) {
        if (row[i] === char) {
          count++;
        }
      }
    }
    return count;
  }
  
  // or
  function countChar(dataset, char) {
    return dataset.reduce((count, row) => {
      const charCount = [...row].filter(c => c === char).length;
      return count + charCount;
    }, 0);
  }
  
  console.log(countChar(dataset, "M"));

CHOYEAH

Move fast & break things

이전 포스트

Recursive Call

다음 포스트