[CS - Data Structure] 배열(Array)과 알고리즘
배열 (Array)
배열은 데이터를 저장하고 관리하기 위한 자료구조이다.
같은 데이터 타입의 요소들이 순차적으로 나열되어 있으며, 각 요소는 index를 통해 접근할 수 있다.
메모리 상에서 연속적인 공간에 요소들을 저장하며, index를 통해 각 요소에 접근할 때에는 index 값으로부터 해당 요소의 메모리 위치를 계산하여 접근한다.
배열의 메모리 구조
- 배열 변수는 참조 변수에 속한다.
- 배열도 객체이므로 힙 영역에 생성된다.
- 배열 변수는 힙 영역의 배열 객체를 참조하게 된다.
1 2 3
int a = 10; // 메모리에 10을 저장 int[] b = {10, 20, 30}; // 메모리에 배열 객체 {10, 20, 30}의 객체 주소를 저장 // 즉, 배열 변수 b는 메모리에 배열 객체 {10, 20, 30}의 주소를 저장하고 있기 때문에 b는 객체 {10, 20, 30}을 가리킨다.
배열의 특징
- 배열의 각 요소에 접근하는 시간은 O(1)로 모두 동일하다.
- 기본 위치 + 오프셋(요소 크기 X index) 연산으로 모든 요소에 접근 가능하다.
- 연속된 메모리에 단일 블록화하여 데이터를 저장한다.
- 낭비되는 공간이 거의 없다.
- 단, 큰 배열의 경우 메모리 할당이 어려울 수 있다.
- 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하여 indexing 및 slicing이 가능하다.
indexing : index를 사용하여 특정 요소를 배열로부터 읽어드리는 것
slicing : 요소의 특정 부분을 따로 분리하여 조작하는 것
배열의 장단점
장점
- 인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있다.
- 기록 밀도가 1이기 때문에 공간 낭비가 적다.
- 리스트, 그래프 등은 데이터 외에 주소 정보(포인터) 등 부가정보를 가지기 때문에 기록 밀도가 1이 되지 않는다.
- 배열은 부가정보 없이 데이터만 저장되기 때문에 기록 밀도가 1이다.
기록 밀도 : 기억 매체의 단위 길이로, 단위 면적 또는 단위 부피당의 기억 정보량을 나타낸다.
- 간단하고 사용하기 쉽다.
- 메모리 연속성으로 인한 캐시 효율이 높다.
단점
- 배열을 선언한 후에는 할당된 정적 메모리 때문에 크기를 변경할 수 없다.
- 중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로부터 위에 있는 모든 요소를 이동시켜줘야 한다.
- 삽입 및 삭제에 많은 비용이 들어가게 된다.
- 배열의 크기가 대부분 정적으로 결정되기 때문에 삽입 및 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하기 어렵다.
- 이로인해 오버플로우나 저장공간의 낭비를 초래할 수 있다. (메모리 낭비)
배열 회전 프로그램
기본 회전 알고리즘
예를 들어, {1, 2, 3, 4, 5, 6, 7} 배열을 왼쪽으로 2번 회전시켜 {3, 4, 5, 6, 7, 1, 2} 배열로 만드는 알고리즘이다.
- {1, 2, 3, 4, 5, 6, 7} -> {2, 3, 4, 5, 6, 7, 1}
- {2, 3, 4, 5, 6, 7, 1} -> {3, 4, 5, 6, 7, 1, 2}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class CommonRotationAlgorithmExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
int n = arr.length;
leftRotate(arr, 2, n);
printArray(arr); // 3 4 5 6 7 1 2
}
static void leftRotate(int[] arr, int d, int n) {
for (int i = 0; i < d; i++) {
leftRotateByOne(arr, n);
}
}
static void leftRotateByOne(int[] arr, int n) {
int temp = arr[0];
for (int i = 0; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
arr[n - 1] = temp;
}
static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
}
}
저글링 알고리즘
최대공약수(GCD, Greatest Common Divisor)를 이용해서 집합을 나누어 여러 요소를 한번에 이동시키는 것이다.
예를 들어, 배열이 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}일 경우 1, 2, 3을 뒤로 옮길 때 index를 3개씩 묶어서 회전시키는 방법이다.
- {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} -> {4, 2, 3, 7, 5, 6, 10, 8, 9, 1, 11, 12}
- arr[0]를 T 변수에 저장한다.
- index를 0에서 3씩 키워가면서, index 기준으로 3번째는 0번째, 6번째는 3번째, 9번째는 6번째로 값을 옮긴다.
- 9에 3을 더한 12는 배열의 마지막 index인 11을 초과하기 때문에 멈춘 후 9번째 index에 아까 저장한 T 값을 옮긴다.
- {4, 2, 3, 7, 5, 6, 10, 8, 9, 1, 11, 12} -> {4, 5, 3, 7, 8, 6, 10, 11, 9, 1, 2, 12}
- arr[1]을 T 변수에 저장한다.
- index를 1에서 3씩 키워가면서, index 기준으로 4번째는 1번째, 7번째는 4번째, 10번째는 7번째로 값을 옮긴다.
- 10에 3을 더한 13은 배열의 마지막 index인 11을 초과하기 때문에 멈춘 후 10번째 index에 아까 저장한 T 값을 옮긴다.
- {4, 5, 3, 7, 8, 6, 10, 11, 9, 1, 2, 12} -> {4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3}
- arr[2]을 T 변수에 저장한다.
- index를 2에서 3씩 키워가면서, index 기준으로 5번째는 2번째, 8번째는 5번째, 11번째는 8번째로 값을 옮긴다.
- 11에 3을 더한 14는 배열의 마지막 index인 11을 초과하기 때문에 멈춘 후 11번째 index에 아까 저장한 T 값을 옮긴다.
이러한 사이클을 n번 반복하는 방법은 배열의 길이가 n의 배수일 때만 사용할 수 있다.
예를 들어, 배열의 길이가 12이고 n이 3이면 사용할 수 있다.
반면에 배열의 길이가 회전 횟수의 배수가 아닌 경우에는 한 사이클 내에 전부 처리할 수 없다.
예를 들어, 배열의 길이가 5이고 n이 2인 경우이다.
이때는 한 사이클에 모든 원소를 바꾸지 못하고, 사이클을 반복해서 모든 원소를 회전시킨다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class JugglingAlgorithmExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = arr.length;
leftRotate(arr, 3, n);
printArray(arr); // 4 5 6 7 8 9 10 11 12 1 2 3
}
static 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 (true) {
int k = j + d;
if (k >= n) {
k -= n;
}
if (k == i) {
break;
}
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
}
}
역전 알고리즘
회전시키는 수에 대해 구간을 나누어 reverse로 구현하는 방법이다.
예를 들어, b = 2 이면 1, 2와 3, 4, 5, 6, 7로 구간을 나눈다.
- {1, 2, 3, 4, 5, 6, 7} -> {2, 1, 3, 4, 5, 6, 7}
- 처음부터 d-1 까지의 요소를 역순으로 변경한다.
- {2, 1, 3, 4, 5, 6, 7} -> {2, 1, 7, 6, 5, 4, 3}
- d부터 마지막까지의 요소를 역순으로 변경한다.
- {2, 1, 7, 6, 5, 4, 3} -> {3, 4, 5, 6, 7, 1, 2}
- 전체 배열을 역순으로 변경한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class ReverseAlgorithmExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
int n = arr.length;
rotateLeft(arr, 2 , n);
printArray(arr); // 3, 4, 5, 6, 7, 1, 2
}
static void rotateLeft(int[] arr, int d, int n) {
reverseArr(arr, 0, d - 1);
reverseArr(arr, d, n - 1);
reverseArr(arr, 0, n - 1);
}
static void reverseArr(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
}
}
특정 배열 최대 합 (i * arr[i])
예를 들어, arr[i]가 {1, 20, 2, 10}인 경우 2번 회전시킨다면 i * arr[i]의 합이 72로 가장 큰 경우의 값이 될 것이다.
- {1, 20, 2, 10} = 54 -> {20, 2, 10, 1} = 25
- 첫 번째 회전을 통해 배열을 변경한다.
- {20, 2, 10, 1} = 25 -> {2, 10, 1, 20} = 72
- 두 번째 회전을 통해 배열을 변경한다.
이 문제를 수식으로 정리해 보면
- 회전없이
i * arr[i]의 합을 저장한 값- R(0) = 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … + (n - 1) * arr[n - 1]
- 1번 회전 후
i * arr[i]의 합을 저장한 값- R(1) = 0 * arr[n - 1] + 1 * arr[0] + 2 * arr[1] … + (n - 1) * arr[n - 2]
- 2번 회전 후
i * arr[i]의 합을 저장한 값- R(2) = 0 * arr[n - 2] + 1 * arr[n - 1] + … + (n - 1) * arr[n - 3]
따라서
- R(1) - R(0)는
- R(1) - R(0) = arr[0] + arr[1] + … + arr[n - 2] - (n - 1) * arr[n - 1]
- R(2) - R(1)은
- R(2) - R(1) = arr[n - 1] + arr[0] + arr[1] + … + arr[n - 3] - (n - 1) * arr[n - 2]
여기서 규칙을 확인할 수 있다.
R(i) - R(i - 1) = arr[i - 1] + arr[i] + … + … arr[n - i - 1] - (n - 1) * arr[n - i]
= arr[i - 1] + arr[i] + … + … arr[n - i - 1] - n * arr[n - i] + arr[n - i]
= arr[i - 1] + arr[i] + … + … arr[n - i - 1] + arr[n - i] - n * arr[n - i]
= arrSum - n * arr[n-i]
arrSum = arr[i - 1] + arr[i] + … + … arr[n - i - 1] + arr[n - i]
R(0) 일 경우 arr[-1]과 arr[n]은 없으므로, 생략되어 arr[0] + … + arr[n - 1] 이다.
따라서 R(i)는
R(i) = arrSum - n * arr[n-i] + R(i - 1)
위 규칙을 활용해서 몇 번 회전해야 최대값이 나오는 지 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class MaxRotationSumExample {
public static void main(String[] args) {
int[] arr = {1, 20, 2, 10};
int n = arr.length;
maxRotationSumArray(arr, n); // 72
}
static void maxRotationSumArray(int[] arr, int n) {
int arrSum = 0;
int tempSum = 0;
// R(0)
for (int i = 0; i < n; i++) {
arrSum += arr[i];
tempSum += i * arr[i];
}
int maxSum = tempSum;
// 1, 2, ..., n-1 회전
for (int i = 1; i < n; i++) {
tempSum += arrSum - n * arr[n - i];
if (maxSum < tempSum) {
maxSum = tempSum;
}
}
System.out.println(maxSum);
}
}
특정 배열 재배열 (arr[i] = i)
예를 들어, arr[i] = i이 가능한 것만 재배열 시킨다면
- {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1} -> {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
- {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1} -> {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
- {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1} -> {-1, -1, 2, 1, 9, 3, 6, -1, 4, -1}
- {-1, -1, 2, 1, 9, 3, 6, -1, 4, -1} -> {-1, 1, 2, -1, 9, 3, 6, -1, 4, -1}
- {-1, 1, 2, -1, 9, 3, 6, -1, 4, -1} -> {-1, 1, 2, -1, -1, 3, 6, -1, 4, 9}
- {-1, 1, 2, -1, -1, 3, 6, -1, 4, 9} -> {-1, 1, 2, 3, -1, -1, 6, -1, 4, 9}
- {-1, 1, 2, 3, -1, -1, 6, -1, 4, 9} -> {-1, 1, 2, 3, -1, -1, 6, -1, 4, 9}
- {-1, 1, 2, 3, -1, -1, 6, -1, 4, 9} -> {-1, 1, 2, 3, -1, -1, 6, -1, 4, 9}
- {-1, 1, 2, 3, -1, -1, 6, -1, 4, 9} -> {-1, 1, 2, 3, 4, -1, 6, -1, -1, 9}
- {-1, 1, 2, 3, 4, -1, 6, -1, -1, 9} -> {-1, 1, 2, 3, 4, -1, 6, -1, -1, 9}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class RearrangementExample {
public static void main(String[] args) {
int[] arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1};
int n = arr.length;
rearrangeArray(arr, n);
printArray(arr); // -1 1 2 3 4 -1 6 -1 -1 9
}
static void rearrangeArray(int[] arr, int n) {
for (int i = 0; i < n; i++) {
if (arr[i] != -1 && arr[i] != i) {
int x = arr[i];
while (arr[x] != -1 && arr[x] != x) {
int y = arr[x];
arr[x] = x;
x = y;
}
arr[x] = x;
if (arr[i] != i) {
arr[i] = -1;
}
}
}
}
static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
}
}
References
This post is licensed under CC BY 4.0 by the author.