배열
알고 가기
- 원소를 삭제해서 다른 원소들을 왼쪽으로 옮기기보다는 삭제할 원소에 덮어쓰는 방법이 나을 수도 있다.
- 배열로 표현된 정수를 다룰 때에는, 배열의 끝에서부터 숫자를 처리해 나가는 방법을 고려해 보라. 혹은 배열을 뒤집어서 최하위 숫자를 배열의 첫 번째 위치에 오도록 만들 수 있다.
- 부분 배열을 사용하는 코드를 작성하는 데 익숙해지면 좋다.
- 배열을 사용할 때 인덱스를 잘못 사용하는 실수에 유의해야 한다.
- 실제 반환할 때까지 배열의 초기 상태를 유지(정렬, 균등한 원소 유지 등)하지 않아도 된다.
- 2차원 배열을 사용할 때는 열과 행을 동시에 처리하는 로직을 사용하자.
- 가끔은 문제의 세부 사항을 따라 해 보는 것이 문제를 분석적으로 푸는 것보다 쉬울 수 있다. 예로 나선형으로 채워진 n*n 배열의 i번째 원소를 찾는 수식을 작성하는 것보다 첫 번째 원소부터 나선형으로 하나씩 따라가면서 i번째 원소를 찾는 게 더 쉬울 수 있다.
- 하위 배열을 만들기 위해서는 vector
subarray_A(A.begin() + i, A.begin() + j)와 같이 한다. 이렇게 하면 subarray_A는 A[i, j-1]로 설정된다. - vector<vector
> A = {1, 2}, {3, 4}, {5, 6}} 이런 식으로 각 열이 2개의 원소를 가지고 행의 개수가 3개인 배열. 이런식으로 2차원 배열 초기화 가능 - algorithm에 포함된 주요 메서드로는 binary_search(A.begin(), A.end(), 42), lower_bound(A.begin(), A.end(), 42), upper_bound(A.begin(), A.end(), 42), fill(A.begin(), A.end(), 42), swap(x, y), min_element(A.begin(), A.end()), max_element(A.begin(), A.end()), reverse(A.begin(), A.end()), rotate(A.begin(), A.begin()+shift, A.end()), sort(A.begin(), A.end())가 있다.
예시 문제
정수 배열이 주어졌을 때 짝수가 먼저 나오도록 재배열해 보라. 이 문제는 배열의 길이가 n이라고 했을 때, 추가 공간을 O(n)만큼 사용하면 쉽게 풀 수 있다. 그런데 추가 공간을 이용하지 않고도 풀 수 있다. 배열에서 양쪽 끝을 손쉽게 접근할 수 있는 이점을 떠올려 보자. 배열을 짝수, 정해지지 않은 숫자, 홀수의 세 가지 부분 배열로 나눌 것이다. 초기에는 짝수와 홀수 배열은 비어 있고, 정해지지 않은 숫자는 전체 배열이 될 것이다. 정해지지 않은 숫자를 하나씩 순회하면서 원소를 홀수 혹은 짝수 부분 배열로 옮긴다.
void EvenOdd(vector<int> * A_ptr) {
vector<int>& A = *A_ptr;
int next_even = 0, next_odd = size(A) - 1;
while (next_even < next_odd) {
if (A[next_even] % 2 == 0) {
++next_even;
} else {
swap(A[next_even], A[next_odd--]);
}
}
}
네덜란드 국기 문제
퀵정렬 알고리즘은 다음 과정을 재귀적으로 반복한다. 원소(피벗)를 선택한 후 이보다 작거나 같은 그룹은 왼쪽, 이보다 큰 그룹은 오른쪽에 나오도록 재배치한다. 이를 재귀적으로 반복하면 두 부분 배열을 정렬된다. 피벗의 위치에 따라 부분 배열의 크기가 달라지기 때문에 단순하게 구현한다면, 퀵정렬의 수행 시간은 커지고, 함수 호출 스택에는 깊은 복사에 의한 중복된 부분 배열이 많을 것이다. 이를 해결할 한 가지 방법은 같은 배열에서 피벗보다 작은 원소, 피벗과 같은 원소, 피벗보다 큰 원소 순으로 재배열 하는 것이다.
배열 A와 인덱스 i가 주어졌을 때, Ai보다 작은 원소, 피벗과 같은 원소, 피벗보다 큰 원소 순으로 재배열하는 프로그램을 작성하라.
풀이 방법
힌트: 퀵정렬에서 피벗을 기준으로 원소를 나누는 방법을 다시 생각해 보자.
배열 A의 길이를 n이라고 했을 때, O(n)의 공간을 추가로 사용한다면 이 문제는 굉장히 간단하다. 피벗보다 작은 원소, 피벗과 같은 원소, 피벗보다 큰 원소 이렇게 세 리스트를 만든 뒤에 이들을 A에 넣어 주면 된다. 시간 복잡도는 O(n)이다.
시간복잡도는 약간 증가하지만 O(n)의 추가 공간을 사용하지 않는 방법도 있다. 배열 A를 순차적으로 순회하면서, 피벗보다 작은 원소를 찾은 뒤 피벗보다 작은 원소들로 구성된 부분 배열로(왼쪽) 옮긴다. 그다음에 비슷하게 피벗보다 큰 원소들을 배열의 오른쪽으로 옮긴다.
```cpp
typedef enum { kREd, kWhite, kBlue } Color;
void DutchFlagPartition(int pivot_index, vector* A_ptr) {
vector& A = *A_ptr;
Color pivot = A[pivot_index];
// 첫 단계: 피벗보다 작은 원소의 그룹 구하기
for (int i=0; i <size(A); ++i) {
// 작은 원소 찾기
for (int j= i+1; j < size(A); ++j) {
if (A[j] < pivot) {
swap(A[i], A[j]);
break;
}
}
}
// 두번째 단계: 피벗보다 큰 원소의 그룹을 구한다
for (int i= size(A) -1; i >=0; --i) {
// 큰 원소 찾기. 피벗보다 작은 원소에 맞닥뜨리게 되면 멈춤
// 왜냐하면 윗 단계에서 그들은 이미 A의 앞쪽으로 옮겨졌기 때문
for (int j = i-1; j>=0; --j) {
if(A[j] > pivot) {
swap(A[i], A[j]);
break;
}
}
}
}
```
공간복잡도는 O(1)이고, 시간 복잡도는 O($n^2$)이다.
단일 패스를 통해 피벗보다 작은 원소를 모두 앞으로 옮겨 보자. 그 후 피벗보다 큰 원소를 모두 뒤로 옮길 것이다.
```cpp
void DutchFlagPartition(int pivot_index, vector* A_ptr) {
vector & A = *A_ptr;
Color pivot = A[pivot_index];
//첫 번째 단계: 피벗보다 작은 원소의 그룹을 구한다
int smaller = 0;
for (int i=0; i < size(A); ++i) {
if (A[i] < pivot) {
swap(A[i], A[smaller++]);
}
}
// 두 번째 단계; 피벗보다 큰 원소의 그룹을 구한다
int larger = size(A) -1;
for (int i = size(A) - 1; i >=0; --i) {
if (A[i] > pivot) {
swap(A[i], A[larger--]);
}
}
}
```
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.
이번엔 단일 패스를 통해 피벗보다 작거나, 같거나, 큰 원소들을 분류해보자. 부분 배열을 피벗보다 작은 원소(bottom), 피벗과 같은 원소(middle), 미분류 원소(unclassified), 피벗 보다 큰 원소(top) 이렇게 4개로 나눈다. 미분류 원소에 있는 원소를 차례대로 피벗과 비교하여 나머지 세 부분 배열 중 하나로 옮긴다.
```cpp
void DutchFlagPartition(int pivot_index, vector* A_ptr) {
vector& A = *A_ptr;
Color pivot = A[pivot_index];
/**
* 분류할 때마다 다음 불변식을 만족해야 한다.
* 피벗보다 작은 원소 그룹: A[0, smaller-1]
* 피벗과 같은 원소 그룹: A[smaller, equal -1]
* 미분류 원소 그룹: A[equal, larger-1]
* 피벗보다 큰 원소 그룹: A[larger, size(A) -1]
*/
int smaller = 0, equal = 0, larger = size(A);
// 분류되지 않은 원소가 있는 동안 계속 순회한다.
while(equal < larger) {
// A[equal]은 분류되지 않은 원소를 가리킨다
if (A[equal] < pivot) {
swap(A[smaller++], A[equal++]);
} else if (A[equal] == pivot) {
++equal;
} else { // A[equal] > pivot
swap(A[equal], A[--larger]);
}
}
}
```
매번 분류되지 않은 원소 그룹의 크기는 1씩 감소할 것이고, 원소를 분류하는 데 걸리는 시간은 O(1)이므로 총 시간 복잡도는 O(n)이 된다. 공간 복잡도는 O(1)이다.
</div>
</details>
---
# 임의의 정수값 증가시키기
십진수 D를 나타낸 배열 A가 주어졌을 때, D+1의 결과를 다시 배열 A에 갱신하는 코드를 작성하라. 예로 입력으로 <1,2,9>가 주어졌다면, D+1의 결과는 <1,3,0>이 된다.
## 풀이 방법
- 배열에 연산을 직접 적용하면 오버플로 문제를 피할 수 있다. 즉, 초등학교에서 배운 대로 최하위 숫자부터 덧셈을 한 후 올림수를 넘겨주는 방식을 사용하면 된다.
- 만약 덧셈 결과의 자릿수가 다르다면, 100을 나타내기 위해 세 자리가 필요하지만 입력은 두 자리만 있기 때문에 결과를 저장할 공간이 충분하지 않다.
- 배열의 첫 원소가 10이 되는 경우인데 이 때 배열의 첫 원소를 1로 바꾸고 배열의 끝에 0을 추가해주면 되겠죠.
---
# 임의의 두 정수값 곱하기
매우 큰 정수를 활용하는 한 가지 방법은 배열을 사용해서 정수를 표현하는 것이다. 예로 <1,9,3,7,0,0,2,1>.
정수를 나타내는 두 개의 문자열이 주어졌을 때, 이 둘의 곱셈 결과를 반환하는 함수를 작성하라.
## 풀이 방법
- 초등학생 때 배운 곱셈 연산을 그대로 적용해 보자.
- 공간을 절약하기 위해 각 곱셈 결과를 적어 놓은 후 나중에 한번에 더하는 방식을 쓰지않고 해보자. 길이가 각각 n과 m인 피연산자(operand)를 곱한 결괏값의 자리수는 최대 n+m이 되므로 결과는 n+m 길이의 배열에 저장할 것이다.
코드
```cpp
vector Multiply(vector num1, vector num2) {
const int sign = (num1.front() < 0) ^ (num2.front() < 0) ? -1 : 1;
num1.front() = abs(num1.front()), num2.front() = abs(num2.front());
vector result(size(num1) + size(num2), 0);
for (int i = size(num1) - 1; i >= 0; --i) {
for (int j = size(num2) - 1; j >= 0; --j) {
result[i + j + 1] += num1[i] * num2[j];
result[i + j] += result[i + j + 1] / 10;
result[i + j + 1] %= 10;
}
}
//0으로 시작하는 부분 제거
result = {
find_if_not(begin(result), end(result), [](int a) { return a == 0; });
end(result)};
if (empty(result)) {
return {0};
}
result.front() *= sign;
return result;
}
```
m개의 부분 곱셈이 존재하고, 각각 최대 n+1개의 자릿수와 곱셈을 수행한다. 각 자릿수를 곱하는 데 O(1)의 시간이 걸리므로 총 시간복잡도는 O(nm)이다.
</div>
</details>
---
# 배열에서 이동하기
주어진 위치 정보를 차례대로 걸어 나가야 하는 보드 게임이 있다. 각 위치에는 음이 아닌 정수값이 들어 있고, 해당 위치에서 최대 그 숫자만큼 앞으로 나아갈 수 있다. 이 게임의 목표는 첫 번째 위치에서 시작해서 마지막 위치에 도달하는 것이다. 예로 배열 A= <3,3,1,0,2,0,1>의 i번째 위치에서는 최대A[i]만큼 앞으로 나아갈 수 있다.
길이가 n인 배열 A가 주어졌을 때, 배열의 시작점에서 마지막 지점까지 도달할 수 있는지 판단하는 프로그램을 작성하라. 단, A[i]는 i번째 위치에서 나아갈 수 있는 최대 거리를 뜻한다.
## 풀이 방법
- 현재 위치에서 최대한 멀리 나아가는 방법은 중간에 더 멀리 나아갈 수 있는 위치를 지나칠 수 있기 때문에 해법이 되지 못한다.
- 배열 A의 값을 차례대로 살펴보면서 최대한 움직일 수 있는 거리가 얼마나 되는지 기록해보면 된다. i위치에서는 최대 i + A[i]까지 움직일 수 있다. 위의 예제의 경우 각 위치에서 최대한 움직일 수 있는 거리는 0, 3, 4, 4, 4, 6, 6, 7이 되므로, 마지막 위치에 도달할 수 있다
---
# 문제 5.5 정렬된 배열에서 중복 제거하기
정렬된 배열이 입력으로 주어졌을 때 중복된 원소를 모두 제거한 뒤, 비어 있는 공간이 생기지 않도록 유효한 원소들을 모두 왼쪽으로 시프트하는 프로그램을 작성하라. 유효한 원소의 개수를 반환하면 된다. 많은 언어에서 삭제 연산이 라이브러리로 주어지지만 라이브러리를 사용하지 말고 구현하라
## 풀이 방법
- 공간을 O(n)만큼 추가로 사용할 수 있다면 해시 테이블을 이용하면 된다. 해시 테이블에 원소를 넣고 확인하면 된다. 새로운 원소는 리스트에 넣은 뒤, 그 리스트를 다시 배열 A에 복사한다.
- 가장 효율적이게 해보자. 배열이 이미 정렬되어 있으므로 반복된 원소들은 연달아 나타난다. 즉, 자료구조를 보조적으로 사용하지 않아도 된다.
```cpp
// 삭제 후 유효한 원소의 개수를 반환한다
int DeleteDuplicates(vector* A_ptr) {
vector& A = *A_ptr;
if (empty(A)) {
return 0;
}
int write_index = 1;
for (int i = 1; i < size(A) ; ++i) {
if (A[write_index -1] != A[i]) {
A[write_index++] = A[i];
}
}
return write_index;
}
```
시간 복잡도는 O(n)이고, 추가 변수 두 개를 사용했으므로 공간 복잡도는 O(1)이다.
---
# 주식 한 번 사고팔기
특정 기간, 주식 한 주를 사서 되팔았을 때 최대 이익을 얻을 수 있는 알고리즘을 설계하라. 모든 매매는 시작가를 기준으로 하며, 매도는 매입 후에 발생한다.
어떤 회사의 일일 주식 가격이 배열로 주어졌을 때 한 주를 한 번 사고팔아서 남길 수 있는 최대 이익을 구해 보자.
## 풀이 방법
- 특정 날짜에 주식을 매도할 예정이고, 이때의 수익을 최대로 하고 싶다면, 이전 날짜 중에서 주식 가격 중에 최소 가격인 m을 기록해 놓는다. 즉, 현재 가격과 m의 차이가, 기록된 최고가보다 크다면 최고가를 갱신한다. 시간 복잡도는 O(n)이다. 입력 배열 이외에 두 개의 실수 변수(최고가와 최저가를 기록하는 변수)와 루프 변수 하나가 필요하므로 추가로 필요한 공간 복잡도는 O(1)이다.
---
# 주식 두 번 사고팔기
주식 한 주를 최대 두 번까지 매매할 수 있을 때, 최대 이윤을 구하는 프로그램을 작성하라. 단, 두 번째 주식은 첫 번째 주식을 판 뒤에 구입할 수 있다.
## 풀이 방법
- 이 방법도 이전에 계산해 놓은 값을 제대로 이용하지 못하기 때문에 비효율 적이다. A[0,j]의 최대 이익값을 기록해 놓고, 반대로 순회하면서 A[j, n-1]의 최대 이익값을 구하면서 동시에 앞에서 저장해 놓은 최대 이익값을 합치면, 현재 이전에 얻은 최대 이익과 현재 이후에 얻은 최대 이익의 합을 구할 수 있으며 이는 주식을 두 번 사고팔았을 때의 최대 이익이된다.
- 예를 들어 입력 배열이 <12,11,13,9,12,8,14,13,15>라고 가정하면 첫째 날에서 i번째 날짜 중에 주식을 한 번 사고 팔아 얻을 수 있는 최대 이익은 F = <0,0,2,2,3,3,6,6,7>이 된다. 반대로 i번째 날부터 마지막 날까지 중에 주식을 한 번 사고팔아서 얻을 수 있는 최대 이익은 B = <7,7,7,7,7,7,2,2,0>이 된다. 이 둘을 합치면 M[i] = F[i-1] + B[i]가 된다. 두 번째 주식 구매는 첫 번째 주식 매도 이후에 발생해야 하므로 F[-1]은 0이 된다. 따라서 M = <7,7,7,9,9,10,5,8,6>이 되고 최대 이익은 10이 된다.
이 알고리즘의 시간 복잡도는 O(n)이고, 부분 배열의 최대 이윤을 저장하기 위한 배열이 추가적으로 필요하므로 공간 복잡도 또한 O(n)이다.
---
# 대체 연산
n개의 숫자를 원소로 가지는 배열 A를, B[0] ≤ B[1] ≥ B[2] ≤ B[3] ≥ B[4] ≤ B[5] ≥ … 의 특징을 가지도록, 새로운 배열 B에 재배치하라.
## 풀이 방법
간단한 해결책 중 하나는, 배열 A를 정렬한 뒤 아래쪽과 위쪽 절반을 교차로 배치하는 것이다. 또는 정렬 후 인덱스 (1, 2) 와 (3, 4)를 서로 교환하는 방식으로 나아가는 것이다. 둘다 정렬 시간 복잡도인 O(nlogn)의 시간 복잡도를 가진다.
하지만 굳이 A를 정렬할 필요 없이, 중간 값 주위의 원소를 재배열한 후 교차 배치를 하면 된다. 중간값 찾기는 문제 11.8의 해법에서 볼 수 있는 것 처럼 O(n) 시간에 수행할 수 있다.
더 효율적인 방법으로 문제에서 요구하는 순서가 매우 국지적이므로, 중간값을 찾을 필요가 없이 배열을 순회하면서 i가 짝수고 A[i]>A[i+1] 이거나, i가 홀수이면서 A[i]<A[i+1]일 때, A[i]와 A[i+1]을 교환하면 된다.
이 접근 방식은 중간값 찾기에 기반한 해법과 동일하게 O(n)의 시간 복잡도를 가진다. 하지만 메모리에 두 개이상의 원소를 저장하거나 이전 원소를 읽을 필요가 없는 국지적 변경을 구현하는 것이 훨씬 쉽다. 정렬할 필요 없이 하나씩 순회하면서 요구하는 순서를 맞춰 주면 된다.
---
# n보다 작은 모든 소수 나열하기
양의 정수 n이 주어졌을 때, 1과 n사이에 있는 모든 소수를 반환하는 프로그램을 작성해 보자.
힌트: 합성수는 제외한다
무식한 방법으로 n까지 모든 숫자를 순회하면서 각 숫자가 소수인지 매번 확인하는 방법이 있다. i가 합성수라면 반드시 제곱근보다 크지 않은 숫자를 약수로 가지고 있기 때문에, i의 소수 확인하는데는 $O(n^{1/2})$ 의 시간 복잡도가 필요하고 전체 알고리즘의 시간 복잡도는 O($n^{3/2}$)가 된다. 휴리스틱이지만, 소수를 발견할 때마다 그 소수의 배수를 제거하는 방법도 있다.(에라토스테네스의 체)
불 배열을 이용하여 전체 소수를 구해 보자. 초기에 2이상의 값은 소수의 후보자가 된다. 첫 번째 소수는 2이며, 이를 결과에 추가한다. 2의 배수는 소수가 될 수 없으므로 해당 후보들을 거짓으로 체크해 놓는다. 이런식으로 후보자 배열의 마지막에 도달할 때까지 이 과정을 반복한다.
p의 배수를 걸러 내는 방법의 시간 복잡도는 n/p에 비례한다. 따라서 전체 시간 복잡도는 O(n/2 + n/3 + n/5 + …) 이 된다. 명백하지 않지만 점근적으로 n log log n 으로 수렴한다. 따라서 시간 복잡도는 O(n log log n) 이고, 공간 복잡도는 배열 P의 크기인 O(n)이다.
```cpp
// n이 주어졌을 때, n보다 작거나 같은 모든 소수를 반환하라
vector GeneratePrimes(int n) {
vector primes;
// is_prime[p]는 p가 소수인지 아닌지 나타낸다. 초기에는 0 과 1을 제외한
// 나머지를 모두 참으로 세팅한다. 그 다음에 소수가 아닌 숫자들을 걸러 낸다
deque is_prime(n+1, true);
for (int p=2; p<=n; ++p) {
if (is_prime[p]) {
primes.emplace_back(p);
// p의 배수를 걸러 낸다.
for (int i = p*2; i<=n; i += p) {
is_prime[i] = false;
}
}
}
return primes;
}
```
**수행시간을 개선하기 위해 p가 아닌 $p^2$의 배수부터 제거해 나가도 된다. 모든 kp(k < p)의 합성수에 대해서는 이전에 이미 체크했기 때문이**다. 짝수를 미리 제거함으로써 공간 복잡도를 줄여도 좋다.
```cpp
// n이 주어졌을 떄, n보다 작거나 같은 모든 소수를 반환하라
vector GeneratePrimes(int n) {
if (n < 2) {
return {};
}
const int size = {floor(0.5 * (n-3)) + 1;
vector primes;
primes.emplace_back(2);
// is_prime[i]는 (2i+3)이 소수인지 아닌지 알려 준다.
// 예로, is_prime[0]은 3이 소수인지 아닌지를 나타내고,
// is_prime[1]은 5를, ...
// 초기에는 전부 참으로 세팅한다.
deque is_prime(size, true);
for (int i=0; i < size; ++i) {
if (is_prime[i]) {
int p = (i*2) + 3;
primes.emplace_back(p);
// p^2부터 배수를 제거해 나간다. 그 값은(4i^2 + 12 + 9) 겠죠
// 이 값의 is_prime에서의 인덱스는 (2i^2 + 6i + 3)이다
// 왜냐하면 is_prime[i]가 2i +3을 의미하기 때문
// j에 대해선 long long 자료형을 사용해 하는데 p^2가
// 오버플로 될 수 있기 때문이다.
for (long long j = 2LL * i * i + 6 * i + 3; j <size; j +=p) {
is_prime[j] = false;
}
}
}
return prime;
}
```
---
# 문제 5.10 배열 안의 원소로 순열 구하기
순열이란 일련의 순서로 나열된 원소들을 새로운 순서로 재배열하는 것을 말한다. 배열 P를 이용하여 순열을 나타낼 수 있는데, 예를 들면 P[i]는 i원소의 새로운 위치가 된다. 즉, 배열 <2, 0, 1, 3>은 0번 원소는 2번으로, 1번 원소는 0번으로, 2번 원소는 1번으로, 3번 원소는 제자리에 놓는다는 뜻이다.
길이가 n인 배열 A와 순열 P가 주어졌을 때, P를 A에 적용해 보라
힌트: 모든 순열은 순환 순열의 집합 안에 있다고 말할 수 있다. 이미 순환된 원소를 어떻게 나타낼 수 있을까?
추가 공간을 사용할 수 있다면 순열 배열을 주어진 배열에 적용하는 것은 간단하다.
추가 메모리를 사용하지 않고 풀어 보자. 한번에 한 개의 원소를 올바른 위치로 옮겨야 한다. 추가 메모리를 사용할 수 없기 때문에 기존 원소를 어디론가 옮길 수 밖에 없다. 또한 원소가 이동해야 하는 위치를 기록하기 위해 순열을 업데이트해야 한다. 이는 P의 스왑으로 처리할 수 있다. i를 올바른 위치로 옮겼다면 P[i]도 i로 설정한다. 스왑처리를 하다가 P[i]=i와 같은 i가 있다면 원소가 이미 올바른 순열 위치에 있다는 뜻이다. 예로 A = <a,b,c,d> P = <2,0,1,3> 인 경우를 생각해보자.
1. 인덱스 0에 있는 원소 a를 인덱스 2의 원소와 스왑하고 P를 업데이트한다. A = <c,b,a,d>, P = <1,0,2,3>
2. 인덱스 0에 있는 원소 c를, 이동할 위치인 인덱스 1의 원소와 스왑하고 P를 업데이트 한다. A = <b,c,a,d> , P = <0,1,2,3> 이다.
3. 0,1,2의 원소는 이제 순열된 위치로 이동하였으므로, 인덱스 3 을 확인한다. P[i]=i이므로 올바른 순열 위치에 있다.
```cpp
void ApplyPermutation(vector perm, vector* A_ptr) {
vector& A = *A_ptr;
for (int i = 0; i < size(A); ++i) {
while (perm[i] != i) {
swap(A[i], A[perm[i]]);
swap(perm[i], perm[perm[i]]);
}
}
}
```
각 반복마다 적어도 1개의 원소를 순열된 위치로 옮기므로 시간 복잡도는 O(n)이다. 순열 배열을 수정하기 때문에 공간 복잡도는 O(n)이다.?
## 응용
- 같은 문제를, 추가 공간을 사용하지 않고 P를 수정하지 않은 채 풀 수 있을까?
- 모든 순열은 고유한 역(inverse)이 있다. 역은, 값을 원래의 위치로 다시 옮기는 순열을 말한다. 순열 배열 A가 주어졌을 때, 상수 크기의 공간을 사용해서 A의 역순열을 구하라
---
# 문제 5. 11 다음 순열 구하기
n개의 원소로 만들 수 있는 순열의 개수는 n!이다. 이들은 사전 순으로 정렬이 가능하다 즉, 0번째 인덱스부터 시작해서 처음으로 다른 값이 더 작은 쪽이 앞에 온다.
어떤 순열이 주어졌을 때 다음 순열을 구하는 함수를 작성하라. 단, 순열의 순서는 사전 순서로 정렬되어 있다. 주어진 순열이 가장 마지막 순열이라면 빈 순열을 반환하면 된다.
힌트: 실제 예제를 사용해서 생각해 보자
무식한 방법은 모든 순열을 사전 순으로 나열한 뒤 찾는 것이다. 시간 및 공간 복잡도가 엄청 클 것이다. 순열이 사전 순으로 정렬되어 있으므로, 순열의 크기를 가능한 조금씩 증가시켜야 한다.
순열 <6,2,1,5,4,3,0>을 생각해 보자. 일단 순열의 접미사(suffix) 중에서 가장 긴 감소 순열을 찾는다. <5,4,3,0>이다. 이 순열은 이미 사전 순으로 가장 마지막에 있는 순열이므로 그 다음 순열이 존재하지 않는다. 이 순열 바로 앞에 위치한 원소 e(여기선 1)를 살펴보자. 만약 e가 존재하지 않다면 즉, 가장 긴 감소 순열이라면 이 순열이 사전 순으로 가장 마지막에 있는 순열이므로 다음 순열은 존재하지 않겠죠.
따라서 원소 e는 접미사 순열의 원소 중 적어도 하나보다는 작다. e보다 큰 접미사 순열의 원소 중 가장 작은 원소를 s라고 하자. s와 e를 맞바꾼다면 전체 순열의 접두사(prefix)를 최소한으로 증가시킨 꼴이 된다. 여기선 e가 1, s가 3이다. 이 맞바꿈으로 바로 가장 작은 순열인 것은 아니다. 순열의 접두사 부분만 적용되는 부분이다. 접미사 부분은 아직 가장 작은 수열이 아니다. 정렬을 하면 얻을 수 있다. 여기선 <0,1,4,5> 이다.
1. p[k] < p[k+1] 이면서 k 이후의 접미사가 감소 순열인 k를 찾는다.
2. p[l] > p[k] 중에서 가장 작은 p[l]을 찾는다.
3. p[l]과 p[k]를 맞바꾼다.
4. k이후의 접미사 순열을 뒤집어 준다
```cpp
vector NextPermutation(vector perm) {
// 오른쪽에서 바로 다음 항목보다 작은 첫 번째 항목을 찾는다
auto inversion_point = is_sorted_until(rbegin(perm), rend(perm));
if (inversion_point == rend(perm)) {
return {};
}
// inversion_point가 참조하는 항목을, inversion_point가 참조하는 항목보다 큰,
// inverison_point 뒤에 나타나는 가장 작은 항목으로 바꾼다.
// 1. inversion_point가 참조하는 항목보다 큰 inversion_point 다음의
// 가장 작은 항목을 찾는다. perm은 inversion_point 이후에 내림차순으로
// 정렬되어야 하므로 빠른 알고리즘을 사용하여 이 항목을 찾을 수 있다.
auto least_upper_bound =
upper_bound(rbegin(perm), inversion_point, *inversion_point);
// 2. 스왑 처리를 한다.
iter_swap(inverison_point, least_upper_bound);
// inversion_point 두에 오는 부분 배열을 뒤집는다.
reverse(rbegin(perm), inversion_point):
return perm;
}
```
배열을 상수 번 읽는다. 따라서 전체 시간 복잡도는 O(n)이고, 사용하는 지역 변수의 개수가 상수이므로 공간 복잡도는 O(1)이다.
## 응용
- 사전 순으로 정렬된 순열에서 k번째 순열을 구하는 프로그램을 작성하라.
- 순열p가 주어졌을 때, 사전 순으로 p이전의 순열을 구하는 프로그램을 작성하라.
---
# 문제 5.12 오프라인 데이터 샘플 구하기
서로 다른 원소로 이루어진 배열과 부분 집합의 크기가 주어졌을 때, 주어진 크기의 부분 집합을 반환하는 알고리즘을 작성하라. 모든 부분집합이 생성될 확률은 같아야 한다. 입력 배열을 통해 부분 집합의 결과를 반환하라.
힌트: 크기가 k인 임의의 부분 집합이 존재할 때 크기가 k+1인 임의의 부분 집합을 어떻게 구할 수 있을까?
주어진 배열 A의 길이는 n, 부분 집합의 크기를 k라고 하자. 가장 단순한 방법은 입력 배열을 순회하면서 각 원소를 k/n의 확률로 선택하는 것이다. 평균적으로 k개를 선택하겠지만, 더 선택할수도 덜 선택할 수도 있다. 다른 방법으로 크기가 k인 모든 부분 집합을 나열한 뒤 하나를 선택하는 것이다. 부분 집합은 총 $_nC_k$(?) 개 있으므로 시간 및 공간 복잡도가 굉장히 클 것이다. (문제 15.6)
효율적인 방법은 먼저 크기가 k-1인 부분 집합을 만든 뒤, 임의의 나머지 원소 하나를 추가하는 것이다. K=1일 때는 임의의 숫자 생성기를 한번 호출하면 된다. 임의의 값을 n으로 나눈 나머지를 r이라고 했을 때, A[0]과 A[r]을 맞바꾸고 난 후 A[0]이 임의로 생성된 최종 결괏값이 된다. K>1인 경우에는 위와 같이 임의의 숫자 하나를 선택한 다음에 부분 배열 A[1, n-1]에 대해 앞의 과정을 반복하면 된다. 결과적으로 임의의 부분 집합은 A[0, k-1]에 놓이게 되고, 나머지 원소들은 그 뒤에 놓인다.
직관적으로 생각해보면, 크기가 k인 부분 집합을 생성할 확률이 같다면 크기가 k+1인 부분 집합을 생성할 확률도 같을 것이다. 수학적 귀납법을 이용해 증명할 수 있다. 참고로 길이가 k인 모든 부분 집합의 순열이 A[0, k-1]에 존재할 확률이 같다는 사실이 위 증명의 귀납 가정이다.(??????)
```cpp
void RandomSampling(int k, vector* A_ptr) {
vector& A = *A_ptr;
default_random_engine seed((random_device())()); // 난수 생성기
for (int i = 0; i < k; i++) {
// [i, A.size() - 1] 사이에서 임의의 수를 생성한다.
swap(A[i], A[uniform_int_distribution{
i, static_cast(A.size()) -1}(seed)]);
}
}
```
이 알고리즘의 공간 복잡도는 명백히 O(1)이다. 시간 복잡도는 원소를 선택하는 데 필요한 O(k)와 같다. 약간의 최적화를 해 보자면, k가 n/2보다 큰 경우에는 임의의 숫자 생성기를 n-k번 호출한 뒤 해당 숫자들을 집합에서 제거하면 된다. 예로 k=n-1이라면 임의의 숫자 생성기를 한 번만 호출한 뒤 이를 뺀 나머지 원소들을 반환하면 된다.
## 응용
표준 C라이브러리에 있는 rand() 함수는 [0, RAND_MAX-1] 사이의 값을 동일한 확률로 반환한다. 이때 rand() mod n 은 [0, n-1] 사이의 값을 동일한 확률로 선택한다고 말할 수 있을까?
---
# 문제 5.13 온라인 데이터 샘플 구하기
이 문제는 네트워크 세션에서 균일한 샘플의 패킷을 제공하는 패킷 스니퍼(packet sniffer)를 설계하는 부분에 착안해서 만들어졌다.
어떤 정수값 k가 주어졌을 때, 실시간으로 패킷이 유입되는 상황에서, k개의 임의의 패킷을 균일한 확률로 유지하는 알고리즘을 설계하라
힌트: 이미 k(n≥k)개를 가지고 있다고 가정해 보자. 이때, n+1번째 패킷이 입력으로 들어오면 어떻게 할 것인가?
무식한 방법은 모든 패킷을 읽은 뒤 저장하는 것이다. 매번 패킷을 읽을 때마다 5.12문제의 해법을 적용해서 크기가 k인 부분 집합을 임의로 선택한다. 이 방법은 n개의 패킷을 모두 저장해야 하므로 공간 복잡도가 O(n)으로 매우 크다. 시간 복잡도도 O(kn)으로 매우 크다.
처음 n개의 패킷을 읽고서 크기가 k인 부분 집합을 임의로 선택했다고 가정해 보자. n+1번째 패킷을 읽었을 때 해당 패킷이 부분 집합에 포함될 확률은 k/(n+1)이다. 기존의 부분 집합에서 패킷 하나를 임의로 선택해서 제거한다면, n+1개의 패킷에서 크기가 k인 부분 집합을 임의로 선택한 꼴이 된다.
이는 읽은 패킷의 개수에 대한 수학적 귀납법을 통해 증명할 수 있다. 이 증명의 귀납 가정(induction hypothesis)은 n≥k번째 패킷을 읽은 뒤에 선택한 k개가 이미 균일한 확률을 유지하는 임의이 샘플이라는 사실이다.
```cpp
// 가정: 적어도 k개의 원소가 유입된다.
vector OnlineRandomSample(vector::const_iterator stream_begin,
const vector::const_iterator stream_end,
int k) {
vector running_sample;
// 첫 k개의 원소를 저장한다.
for (int i = 0; i < k; ++i) {
running_sample.emplace_back(*stream_begin++);
}
default_random_engine seed((random_device())()); // 난수 생성기
// 첫 k개의 원소를 읽었다.
int num_seen_so_far = k;
while (stream_begin != stream_end) {
int x = *stream_begin++;
++num_seen_so_far;
// [0, num_seen_so_far - 1] 사이에서 임의의 숫자를 생성한다.
// 그리고 만약에 그 숫자가 [0, k - 1] 사이에 들어 있다면, 해당 원소를
// x와 맞바꾼다.
if (const int idx_to_replace =
uniform_int_distribution{0, num_seen_so_far - 1}(seed);
idx_to_replace < k) {
running_sample[idx_to_replace] = x;
}
}
return running_sample;
}
```
시간 복잡도는 스트리밍으로 유입되는 원소의 개수에 비례한다. 공간 복잡도는 O(k)가 된다.
---
# 문제 5.14 임의의 순열 계산하기
{0, 1, …, n -1}로 이루어진 임의의 순열을 동일한 확률로 만들어 내는 알고리즘을 설계하라.
힌트: 결과를 배열 A에 저장한다고 하자. A[n-1]에 올바른 값이 할당되었을 때 어떻게 처리하겠는가?
무식한 방법은 반복적으로 숫자를 임의로 선택 후, 뽑은 숫자를 다시 뽑으면 무시하고 다른 숫자를 뽑는 방법이 있다. 해시 테이블을 사용하면 되며 공간복잡도는 O(n), 시간 복ㅈ바도는 O(nlogn)으로 알려져 있다.
시간복잡도를 개선하기 위해선 중복된 부분을 피해야 한다. 이를 해결하기 위해 임의의로 선택하는 집합의 개수를 제한한다. 문제 5.12의 해법을 <0, 1, 2, …, n-1>과 k=n에 적용해 보면, 반복마다 배열을 부분 순열과 남아 있는 값으로 나눌 수 있다. 반환되는 부분 집합이 항상 같다고 하더라도 ({0, 1, …, n-1}), 모든 n!개의 가능한 순열이 같은 확률로 선택된다.
```cpp
vector ComputeRandomPermutation(int n) {
vector permutation(n);
// 순열을 0, 1, 2, ..., n-1로 초기화한다.
iota(begin(permutation), end(permutation), 0);
RandomSampling(n, &permutation);
return permutation;
}
```
시간 복잡도는 O(n)이다.
---
# 문제 5.17 스도쿠 체크
9*9 크기의 미완성된 격자판이 2차원 배열로 주어졌을 때 이 게임의 해법이 존재하는지 판별하고자 한다. 즉, 모든 행과 열, 3*3 하위 격자판에 중복되는 숫자가 없어야 한다. 2차원 배열에서 0으로 초기화되어 있는 엔트리는 빈칸을 나타내고, 그 외에는 [1, 9] 숫자로 채워져 있다.
힌트: 직접 제한 사항을 테스트해 보라. 배열을 통해 집합을 표현할 수 있다.
특별한 알고리즘을 사용해야 하는 문제는 아니다. 코드만 깔끔하게 작성하면 된다.
비트 배열(bit array)을 사용해서 제한사항, 즉 [1,9] 사이의 숫자가 한 번 이상 등장했는지를 테스트하면 편리하다.
```cpp
// 미완성된 격자가 올바르게 배치되어 있는지 확인한다.
bool IsValidSudoku(const vector<vector>& partial_assignment) {
// 행 제한사항을 확인한다
for (int i = 0; i < size(partial_assignment); ++i) {
if (HasDuplicate(partial_assignment, i, i +1, 0,
size(partial_assignment))) {
return false;
}
}
// 열 제한사항을 확인한다
for (int j = 0; j < size(partial_assignment); ++j) {
if (HasDuplicate(partial_assignment, 0, size(partial_assignment), j,
j + 1)) {
return false;
}
}
// 격자판 제한사항을 확인한다.
int region_size = sqrt(size(partial_assignment));
for (int I = 0; I < region_size; ++I) {
for (int J = 0; J < region_size; ++j) {
if (HasDuplicate(partial_assignment, region_size * I,
region_size * (I + 1), region_size * J,
region_size * (J + 1))) {
return false;
}
}
}
return true;
}
// 부분배열 partail_assignment[start_row, end_row-1][start_col, end_col-1]이
// {1, 2, ..., size(partial_assignment)};의 값을 중복해서 가지고 있으면 true를 반환한다.
// 그렇지 않으면 false를 반환한다.
bool HasDuplicate(const vector<vector>& partial_assignment, int start_row,
int end_row, int start_col, int end_col) {
deque is_present(size(partial_assingment) + 1, false);
for (int i = start_row; i < end_row; ++i) {
for (int j = start_col; j < end_col; ++j) {
if (partial_assignment([i][j] != 0 &&
is_present[partial_assignment[i][j]]) {
return true;
}
is_present[partial_assignment[i][j]] = true;
}
return false;
}
```
시간 복잡도는 O($n^2$)이고, 추가 공간 복잡도는 비트 배열에 필요한 O(n)이 된다.
스도쿠를 어떻게 푸는 지 알고 싶다면 문제 15.10 참조
---
# 2차원 배열에 나선형으로 원소 배치하기
2차원 배열에 다양한 순서로 원소를 채워 넣을 수 있다. 열별 혹은 행별로 채워 넣는 방법이 일반적일 것이다.
n*n크기의 2차원 배열이 주어졌을 때, 이 배열을 나선형으로 읽은 결과를 반환하는 프로그램을 작성하라.
## 풀이 방법
- 케이스 분석(case analysis)과 분할 정복법(divide-and-conquer)을 사용한다.
- 첫 번째 행에서 n개의 원소, 마지막 열에서 n-1개의 원소, 마지막 행에서 n-1개의 원소, 그리고 첫 번째 열에서 n-2개의 원소를 읽으면 된다. 하지만 읽어야 하는 원소의 개수가 일정하지 않으므로 코드가 복잡해질 수 있다.
- 읽는 원소 개수를 일정하게 유지하기 위해 첫 번째 행에서 n-1개, 마지막 열에서 n-1개, 마지막 행에서 n-1개, 첫 번째 열에서 n-1개의 원소를 읽는다. 그 뒤에는 (n-2) * (n-2) 크기의 2차원 배열을 나선형으로 읽으면 된다. 배열의 길이가 홀수인 경우는 마지막에 가운데 원소만 남으므로 예외처리를 해야 한다.
시간 복잡도는 O($n^2$)이고 공간 복잡도는 O(1)이다.
동일한 반복문 내에서 다음에 처리해야 할 원소와 읽을 방향을 결정해야 한다. 이미 읽은 엔트리는 표식을 위해 0으로 채워 넣었다.
```cpp
vector MatrixInSpiralOrder(vector<vector> square_matrix) {
const array<array<int, 2>, 4> kShift = {0,1}, {1,0}, {0,-1}, {-1,0}}};
int dir = 0, x = 0, y = 0;
vector spiral_ordering;
for (int i=0; i<size(square_matrix) * size(square_matrix); ++i) {
spiral_ordering.emplace_back(square_matrix[x][y]);
square_matrix[x][y] = 0;
int next_x = x + kShift[dir][0], next_y = y + kShift[dir][1];
if (next_x < 0 || next_x >= size(square_matrix) || next_y < 0 ||
next_y >=size(square_matrix) || square_matrix[next_x][next_y] == 0) {
dir = (dir + 1) % 4;
next_x = x + kShift[dir][0], next_y = y + kShift[dir][1];
}
x = next_x, y = next_y;
}
return spiral_ordering;
}
```
시간 복잡도는 O($n^2$)이다.
---
# 2차원 배열 회전하기
$n \times n$ 크기의 2차원 배열이 주어졌을 때 이를 시계방향으로 90도 만큼 회전시키는 프로그램을 작성하라.
## 풀이 방법
추가 공간을 O(1)만큼만 사용해도 문제를 풀 수 있다. 먼저 생각할 수 있는 방법은 각 계층별로 회전을 하는 것이다. 회전 작업을 할 때 다른 계층은 서로 독립적으로 처리할 수 있기 때문이다. 또한 같은 계층에서도 4개의 원소를 한번에 회전할 수 있다. 예로 1은 4의 위치에, 4는 16의 위치에, 16은 13의 위치에 , 13은 1의 위치에 옮긴 뒤, 2도 같은 방법으로 옮긴다. 다음 프로그램은 이러한 방식으로 가장자리 계층에서 시작해서 중심으로 다가오는 방식이다.
시간 복잡도는 O($n^2$)이고 추가 공간 복잡도는 O(1)이다.
다른 방법
약간의 제한사항이 있긴 하지만 O(1)의 공간 및 시간 복잡도로 회전의 효과를 얻을 수 있는 방법이 있다. 객체 r을 반환하는 행렬 A를 가정해 보자. 회전된 행렬 A의 원소(i, j)원소를 읽고자 할 때는 기존 행렬 A에서 [n-1-j,i]의 원소를 반환한다. 쓰는 연산도 이와 비슷하게 처리하면 된다. 객체 r은 단순히 행렬A를 참조하기만 하므로 객체 r을 만드는 데는 상수 시간이면 충분하다. 읽기 연산과 쓰기 연산을 수행하는 데 필요한 시간은 변하지는 않는다. 하지만 기존 행렬 A를 사용하고자 하는 클라이언트가 복수일 때에는 쓰기 연산에 문제가 될 수 있다. 왜쓰기 연산은 기존 행렬 A를 수정하기 때문이다. 행렬 A에 직접 쓰는 작업이 아니더라도 저장된 객체의 메서드가 상태를 변경하면 시스템에 문제가 생길 수 있다. 이 경우에는 ‘copy-on-write’을 사용해서 이 문제를 해결할 수 있다.
```cpp
class RotatedMatrix {
public:
explicit RotatedMatrix(vector<vector<int*>> square_matrix)
: square_matrix_(*square_matrix) {}
int ReadEntry(int i, int j) const {
return square_matrix_[size(square_matrix_) - 1 - j][i];
}
void WriteEntry(int i, int j, int v) {
return square_matrix_[size(square_matrix_) - 1 - j][i] = v;
}
private:
vector<vector>& square_matrix_;
};
```
</div>
</details>
## 응용
- $n \times n$ 크기의 2차원 행렬 A를 수평, 수직, 대각선으로 반사시키는 알고리즘을 작성하라.
---
# 파스칼의 삼각형에서 행 계산하기
음이 아닌 정수 n이 주어졌을 때 파스칼의 삼각형에 해당하는 첫 n개의 행을 출력하는 프로그램을 작성하라.
힌트: 파스칼의 삼각형을 수식으로 작성해 보자
```cpp
vector<vector> GeneratePascalTriangle(int num_rows) {
vector<vector> pascal_triangle;
for (int i = 0; i < num_rows; ++i) {
vector curr_row;
for (int j= 0; j <= i; ++j) {
// 만약 이 위에 인접한 두 엔트리가 존재한다면, 해당 인트리의 값을 위에 인접한
// 두 엔트리의 합으로 나타내라.
curr_row.emplace_back(0 < j && j < i ? pascal_triangle.back()[j - 1] +
pascal_triangle.back()[j] : 1);
}
pascal_triangle.emplace_back(curr_row);
}
return pascal_triangle;
}
```
전체 시간 복잡도는 O(1 + 2 + … + n) = O(n(n + 1) / 2) = O($n^2$)가 된다. 공간복잡도도 비슷하게 O($n^2)$가 된다.
## 응용
- O(n)의 공간 복잡도를 사용해서 파스칼의 삼각형 n번째 행을 구하라.
Leave a comment