[Data Structure] Array

Array?

• 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.
• 대부분 프로그래밍 언어에서는 동일 타입 데이터를 저장한다.
  • 예를들어 int 타입의 배열에서는 정수 요소만 저장할 수 있다.
• 배열을 구성하는 각각의 값을 요소(element)라고 한다.
• 배열에서의 위치를 나타내는 숫자를 인덱스(index)라고 한다.

배열 표현

• C언어에서 배열 선언 시 아래와 같다.

• 위 배열을 그림으로 표현 시 다음과 같다.

• 그림에서 알 수 있는 사실은 다음과 같다.
  • 연속된 메모리 공간에 데이터가 순차적으로 저장된다.
  • C언어에서 인덱스는 0부터 시작한다.
  • 배열의 크기는 10이므로 10개의 요소를 저장할 수 있다.
  • 각 요소는 인덱스를 통해 엑세스 할 수 있다.

배열의 시간 복잡도

Operation	Average Case	Worst Case
Read	O(1)	O(1)
Insert	O(N)	O(N)
Delete	O(N)	O(N)
Search	O(N)	O(N)

특징

• 동일한 데이터 유형을 가진다.
  • 주로 동일한 데이터 유형을 가지지만 다른 데이터도 지원 가능한 언어도 있다.
  • 다른 데이터들이 모인 집합체는 주로 레코드라고 한다.
• 배열의 각 요소에 접근하는 시간은 O(1)로 모두 동일하다.
  • 기본 위치 + 오프셋(요소 크기 x 인덱스)연산으로 모든 요소에 접근 가능
• 연속된 메모리에 단일 블록화하여 데이터를 저장한다.
  • 낭비되는 공간이 거의 없음
  • 단, 큰 배열의 경우 메모리 할당이 불가능할 수 있음
• 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하여 indexing 및 slicing이 가능하다.
  • indexing : index를 사용해 특정 요소를 배열로 부터 읽어드리는 것
  • slicing : 요소의 특정 부분을 따로 분리하여 조작하는 것

장단점

장점

• 인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있다.
• 기록 밀도가 1이기 때문에 공간 낭비가 적다.
  • 리스트, 그래프 등은 데이터 외에 주소 정보(포인터)등 부가정보를 가지기 때문에 기록 밀도가 1이 되지 않는다.
  • 배열은 부가정보 없이 데이터만 저장되기 때문에 기록 밀도가 1이다.
• 간단하고 사용하기 쉽다.

단점

• 배열을 선언한 후에는 할당된 정적 매모리 때문에 크기를 변경할 수 없다.
• 중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로 부터 위에 있는 모든 요소를 이동시켜줘야한다.
  • 삽입 및 삭제에 많은 비용이 들게 된다.
• 배열의 크기가 대부분 정적으로 결정되기 때문에 삽입 및 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하기 어렵다.
  • 이로인해 오버플로우나 저장공간의 낭비를 초래할 수 있다.

배열을 사용한 알고리즘

• C++에서 배열 크기 구하기

int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; 
int n = sizeof(arr) / sizeof(arr[0]); // 7

배열 요소 회전

기본적인 회전 알고리즘

• 임시 저장 공간을 사용하여 첫번째 인덱스 값을 저장한 후 arr[0] ~ arr[n-1]을 각각 arr[1] ~ arr[n]의 값을 주고, arr[n]에 임시 저장 공간에 저장된 값을 넣는다.

void leftRotatebyOne(int arr[], int n){
    int temp = arr[0]; // 임시 저장 공간 선언
    for(int i = 0; i < n-1; i++){
        arr[i] = arr[i+1];
    }
    arr[i] = temp;
}

• 이 함수를 이용해 원하는 회전 수 만큼 for문을 돌려 구현이 가능

저글링 알고리즘

• 최대공약수 gcd를 이용해 집합을 나누어 여러 요소를 함꺼번에 이동시키는 것
• 배열이 아래와 같다면
  
  • arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
• 1, 2, 3을 뒤로 옮길 때, 인덱스를 3개씩 묶고 회전시키는 방법이다.
  1. arr[] => { 4 2 3 7 5 6 10 8 9 1 11 12 }
  2. arr[] => { 4 5 3 7 8 6 10 11 9 1 2 12 }
  3. arr[] => { 4 5 6 7 8 9 10 11 12 1 2 3 }

// 최대공약수 gcd 활용
int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
  
    else
        return gcd(b, a % b); 
} 

// input : 배열, 집합 수, 배열 크기
void leftRotate(int arr[], int d, int n) 
{ 
    for (int i = 0; i < gcd(d, n); i++) { 
       
        int temp = arr[i]; 
        int j = i; 
  
        while (1) { 
            int k = j + d; 
            if (k >= n) 
                k = k - n; 
  
            if (k == i) 
                break; 
  
            arr[j] = arr[k]; 
            j = k; 
        } 
        arr[j] = temp; 
    } 
}

역전 알고리즘

• 회전시키는 수에 대해 구간을 나누어 reverse로 구현하는 방법
• d = 2인 경우
  • 1, 2 / 3, 4, 5, 6, 7로 구간을 나눈다
  • 첫번째 구간을 reverse => 2, 1
  • 두번째 구간을 reverse => 7, 6, 5, 4, 3
  • 합치기 => 2, 1, 7, 6, 5, 4, 3
  • 합친 배열을 reverse => 3, 4, 5, 6, 7, 1, 2
• swap을 통한 reverse

void reverseArr(int arr[], int start, int end){
    while (start < end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        
        start++;
        end--;
    }
}

• 구간을 d로 나누었을 때 역전 알고리즘 구현

void rotateLeft(int arr[], int d, int n){
    reverseArr(arr, 0, d-1);
    reverseArr(arr, d, n-1);
    reverseArr(arr, 0, n-1);
}

배열의 특정 최대 값 구하기

• arr[i]가 있을 때, i*arr[i]의 Sum이 가장 클 때 그 값을 출력하기
  • 회전하면서 최대값을 찾아야한다.

Input: arr[] = {1, 20, 2, 10}
Output: 72

2번 회전했을 때 아래와 같이 최대값이 나오게 된다.
{2, 10, 1, 20}
20*3 + 1*2 + 10*1 + 2*0 = 72

Input: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9};
Output: 330

9번 회전했을 때 아래와 같이 최대값이 나오게 된다.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
0*1 + 1*2 + 2*3 ... 9*10 = 330

• 접근 방법
  • arr[i]의 전체 합과 i*arr[i]의 전체 합을 저장할 변수 선언
  • 최종 가장 큰 sum 값을 저장할 변수 선언
  • 배열을 회전시키면서 i*arr[i]의 합의 값을 저장하고, 가장 큰 값을 저장해서 출력하면 된다.
• 해결법

회전 없이 i*arr[i]의 sum을 저장한 값
R0 = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]

1번 회전하고 i*arr[i]의 sum을 저장한 값
R1 = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2]

이 두개를 빼면?
R1 - R0 = arr[0] + arr[1] + ... + arr[n-2] - (n-1)*arr[n-1]

2번 회전하고 i*arr[i]의 sum을 저장한 값
R2 = 0*arr[n-2] + 1*arr[n-1] +...+ (n?1)*arr[n-3]

1번 회전한 값과 빼면?
R2 - R1 = arr[0] + arr[1] + ... + arr[n-3] - (n-1)*arr[n-2] + arr[n-1]

여기서 규칙을 찾을 수 있음.
Rj - Rj-1 = arrSum - n * arr[n-j]

이를 활용해서 몇번 회전했을 때 최대값이 나오는 지 구할 수 있다.

• 소스 코드

int maxVal(int arr[], int n){
    int arrSum = 0; // arr[i]의 전체 합
    int curSum = 0; // i*arr[i]의 전체 합
    
    for(int i = 0; i < n; i++){
        arrSum = arrSum + arr[i];
        curSum = curSum + (i*arr[i]);
    }
    
    int maxSum = curSum;
    
    for (int j = 1; j < n; j++){
        curSum = curSum + arrSum - n*arr[n-j];
        
        if ( curSum > maxSum )
            maxSum = curSum;
    }
    return maxSum;
}

특정 배열을 arr[i] = i로 재배열 하기

• 주어진 배열에서 arr[i] = i이 가능한 것만 재배열 시키기
  • arr[i] = i가 없으면 -1로 채운다.

Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]

Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8,
              11, 10, 9, 5, 13, 16, 2, 14, 17, 4}
Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
         11, 12, 13, 14, 15, 16, 17, 18, 19]

• 접근 방법
  • arr[i]가 -1이 아니고, arr[i]이 i가 아닐 때가 우선 조건
  • 해당 arr[i] 값을 저장(x)해두고, 이 값이 x일 때 arr[x]를 탐색
  • arr[x] 값을 저장(y)해두고, arr[x]가 -1이 아니면서 arr[x]가 x가 아닌 동안을 탐색
  • arr[x]를 x값으로 저장해주고, 기존의 x를 y로 수정

int fix(int A[], int len){
    for(int i = 0; i < len; i++) {
        if (A[i] != -1 && A[i] != i){ // A[i]가 -1이 아니고, i도 아닐 때
            
            int x = A[i]; // 해당 값을 x에 저장
            
            while(A[x] != -1 && A[x] != x){ // A[x]가 -1이 아니고, x도 아닐 때
                
                int y = A[x]; // 해당 값을 y에 저장
                A[x] = x; 
                
                x = y;
            }
            
            A[x] = x;
            
            if (A[i] != i){
                A[i] = -1;
            }
        }
    }
    
}

 

 

 

 

출처

https://yoongrammer.tistory.com/43

[자료구조] 배열 (Array)

https://github.com/gyoogle/tech-interview-for-developer