[Data Structure] 자료구조 - Array

1. Introduction to Arrays

 

Array는 item들의 collection이 메모리에 연이은 위치에저장된다. 여러 같은 type의 여러 item을 같이 저장하는 것이다. 기본 값에 offset을 추가하여 각 요소의 위치를 쉽게 계산할 수 있다.

 

offset: 기준이 되는 주소에 더해지는 값

 

각 element는 array의 index로 식별할 수 있다.

 

Array의 장점

 

1. Array에서는 element의 random access가 된다. 이 말은 위치로 element에 접근하는 것이 빠르다는 것이다.

2. Array는 성능에 큰 차이를 만들 수 있는 더 나은 캐시 locality를 가지고 있다.

locality: 기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한순간에 특정 부분을 집중적으로 참조하는 특성

 

Array의 단점

 

사이즈를 바꿀 수 없다. 즉, array를 한 번 선언하고 나면 static memory에 할당되기 때문이다.

2. Array rotation

A Juggling Algorithm

 

Array의 길이 n과 회전할 요소 d가 있을 때 GCD(n, d)만큼 다른 sets으로 나눈다. set내의 element를 이동시킨다.

 

 n =12 and d = 3

GCD = 3

 

arr[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

 

첫번째 set을 옮긴 후

arr[] {4 2 3 7 5 6 10 8 9 1 11 12}

 

두번째 set을 옮긴 후

arr[] {4 5 3 7 8 6 10 11 9 1 2 12}

 

세번째 set을 옮긴 후

arr[] {4 5 6 7 8 9 10 11 12 1 2 3}

class RotateArray {
	void leftRotate(int arr[], int d, int n)
    {
    	d = d % n;
        int i, j, k, temp;
        int g_c_d = gcd(d, n);
        for (i = 0; i < g_c_d; i++) {
        
        	temp = arr[i];
            j = i;
            while (true) {
            	k = j + d;
                if (k >= n)
                	k = k - n;
                if (k == i)
                	break;
                arr[j] = arr[k];
                j = k;
            }
            arr[j] = temp;
        }
    }
    
    void printArray(int arr[], int size)
    {
    	int i;
        for (i = 0; i < size; i++)
        	System.out.print(arr[i] + " ");
    }
    
    int gcd(int a, int b)
    {
    	if (b == 0)
        	return a;
        else
        	return gcd(b, a % b);
    }
    
    public static void main(String[] args) 
    { 
        RotateArray rotate = new RotateArray(); 
        int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; 
        rotate.leftRotate(arr, 2, 7); 
        rotate.printArray(arr, 7); 
    } 
} 

    

 

Time complexity : O(n)
Auxiliary Space : O(1)

 

출처: www.geeksforgeeks.org/array-data-structure/