선형 자료구조
선형 자료구조란 요소가 일렬로 나열되어 있는 자료구조를 말한다. 대표적으로 배열, 리스트, 스택, 큐 등이 있다.
배열
정의와 성질
배열은 메모리 상에 원소를 연속하게 배치한 자료구조 이다.
- O(1)에 k번째 원소를 확인/변경 가능
- 추가적으로 소모되는 메모리의 양 (오버헤드) 이 거의 없음.
- Cache hit rate가 높음.
- 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림.
cf) Cache hit rate ??
Cache hit란 CPU가 참조하려고 하는 메모리가 캐시에 존재하고 있는 경우를 말한다. 이 비율이 높을수록 좋은 성능을 가질 수 있다.
메모리에 대한 개념 중 '참조 지역성의 원리'라는 것이 있는데, 이는 동일한 값 또는 해당 값과 관련된 스토리지 위치가 자주 액세스 되는 특성을 말한다. 지역성의 원리 (Principle of Locality) 라고도 불린다.
참조 지역성에는 3가지 종류가 있다.
- 공간 지역성: 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성
- 시간 지역성: 최근에 참조된 주소는 빠른 시간 내에 다시 참조되는 특성
- 순차 지역성: 데이터가 순차적으로 액세스 되는 특성 (공간 지역성에 포함시켜 설명하기도 함)
배열은 메모리 상에 원소를 연속하게 배치한 자료구조이므로, 공간 지역성이 좋아 높은 Cache hit rate을 가진다고 할 수 있다.
기능과 구현
- 임의의 위치에 있는 원소를 확인/변경 - O(1)
- 마지막 원소에서 추가/삭제 - O(1)
- 임의의 위치에서 원소를 추가/삭제 - O(N)
임의의 위치에 원소를 삽입할 때는 그 뒤의 모든 원소들을 한칸씩 뒤로 밀어야 하고
임의의 위치에서 원소를 삭제할 때는 그 뒤의 모든 원소들을 한칸씩 앞으로 당겨야 한다.
삭제하고 나서 가만히 냅두면 안 되나 라는 생각이 들 수도 있는데, 그러면 앞서 언급했던 배열의 정의에도 위배되고 임의의 위치에 있는 원소를 O(1)에 찾을 수 없게 된다.
int main() {
int arr[10] = {10, 50, 40, 30, 70, 20};
int len = 6;
// 3번째 인덱스 위치에 원소 60을 추가한다.
insert(3, 60, arr, len); // 10 50 40 60 30 70 20
// 4번째 인덱스 위치의 원소를 삭제한다.
erase(4, arr, len); // 10 50 40 60 70 20
}임의의 위치에서 원소를 추가/삭제하는 insert, erase 함수를 직접 구현해보자.
insert 함수
앞에서부터 왼쪽의 항을 오른쪽으로 한칸씩 옮기면 계속 같은 값이 덮어씌워지는 문제가 발생한다. 따라서 '뒤에서부터' 왼쪽의 항을 오른쪽으로 한칸씩 옮겨야 한다.
// idx 인덱스 위치에 num 삽입
void insert(int idx, int num, int arr[], int& len) {
if(idx < 0 || idx > len - 1) return // error
for(int i = len; i > idx; i--){ // 뒤에서부터 원소 이동 시작
arr[i] = arr[i - 1];
}
arr[idx] = num;
len++;
}erase 함수
이번에는 '앞에서부터' 오른쪽의 항을 왼쪽으로 한칸씩 옮긴다.
// idx 인덱스 위치의 원소 삭제
void erase(int idx, int arr[], int& len) {
if(idx < 0 || idx > len - 1) return // error
len--;
for(int i = idx; i < len; i++){
arr[i] = arr[i + 1];
}
}배열 초기화 방법
int a[21];
int b[21][21];
// 1. memset 함수 - cstring 헤더
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
// 2. for문
for(int i = 0; i < 21; i++){
a[i] = 0;
}
for(int i = 0; i < 21; i++){
for(int j = 0; j < 21; j++){
b[i][j] = 0;
}
}
// 3. fill 함수 - algorithm 헤더
fill(a, a + 21, 0);
for(int i = 0; i < 21; i++){
fill(b[i], b[i] + 21, 0);
}배열을 특정값으로 초기화 할 때 위와 같은 방법들을 사용할 수 있다. 그런데 이 중에서 memset 함수는 실수할 여지가 굉장히 많다. 예를 들어, 0이나 -1이 아닌 다른 값을 넣으면 오동작한다거나, 2차원 이상의 배열을 함수의 인자로 넘겨 그 곳에서 memset을 하면 값이 잘못 들어가는 등의 문제가 있다. 그래서 memset은 비추천 한다.
for문은 코드가 투박하긴 하지만, 실수할 여지가 없기 때문에 무난하고 좋다.
마지막으로, fill 함수는 코드량도 짧고 실수할 여지도 적어서 가장 추천하는 방법이다.
STL vector
벡터는 배열과 거의 동일한 기능을 수행하는 자료구조로, 임의의 원소에 접근/수정 시 O(1)의 시간복잡도로 수행할 수 있다.
그런데 벡터는 배열과 달리 크기를 자유자재로 변경할 수 있다는 장점도 있다. 나중에 그래프를 인접 리스트로 구현할 때도 벡터가 유용하게 쓰인다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> v1(3, 5); // {5, 5, 5}
cout << v1.size() << "\n"; // 3
v1.push_back(7); // {5, 5, 5, 7}
vector<int> v2(2); // {0, 0}
v2.insert(v2.begin() + 1, 3); // {0, 3, 0}
vector<int> v3 = {1, 2, 3, 4};
v3.erase(v3.begin() + 2); // {1, 2, 4}
vector<int> v4; // {}
v4 = v3; // deep copy (메모리가 새로 할당되어 v4가 바뀌어도 v3에 영향 X)
cout << v4[0] << v4[1] << v4[2] << "\n"; // 124
v4.pop_back(); // {1, 2}
v4.clear(); // {}
}벡터의 insert, erase 함수는 배열에서 구현한 것과 동일하게 시간복잡도가 O(N)이다.
push_back(), pop_back()은 맨 끝의 원소를 추가하거나 삭제하는 것이므로 O(1)이고
맨 앞에서 원소를 추가하거나 삭제하는 push_front(), pop_front() 함수는 시간복잡도가 O(N)이라는 것을 꼭 기억하자!!
배열의 모든 원소 순회
vector<int> v1 = {1, 2, 3, 4, 5, 6};
// 1. range-based for loop (since C+11)
// 그냥 int는 원소의 복사본, int&은 원본 자체를 변경할 수 있음.
// list, map, set에도 동일하게 적용됨.
for(int e : v1) cout << e << " ";
// 2. not bad
for(int i = 0; i < v1.size(); i++){
cout << v1[i] << " ";
}
// 3. *** WRONG ***
for(int i = 0; i <= v1.size() - 1; i++){
cout << v1[i] << " ";
}위의 방법 중에 3번은 아주 잘못된 결과가 나올 수 있다!!
기본적으로 vector의 size 함수는 unsigned int 타입을 반환한다. 따라서, 3번 방법에서 "만약 벡터가 비어있으면" v1.size() - 1 -> (unsigned int)0 - (int)1 이 되고 자동 형변환에 의해 (unsigned int) -1 즉, unsigned int 타입의 최댓값인 4294967295 (2^32 - 1)가 반환된다. (unsigned int overflow 발생)
이렇게 되면 i가 계속 커지다가 어느 순간 런타임 에러가 발생하게 될 것이다.
연습 문제 1
https://www.acmicpc.net/problem/10808
배열은 데이터를 자주 바꾸지 않고 그냥 쌓아두고 싶을 때 활용할 수 있다. 대부분의 문제에서 입력값을 저장할 때 배열을 사용한다.
이번 문제는 특정 인덱스의 원소에 빠르게 접근할 때 배열을 사용하면 효율적인 문제이다.
방법 1
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
for(char ch = 'a'; ch <= 'z'; ch++) {
int cnt = 0;
// 각 알파벳에 대하여 str 전체를 훑어야 한다.
for(auto e: str) {
if(ch == e) cnt++;
}
cout << cnt << " ";
}
}알파벳 소문자의 개수를 N, 입력으로 주어진 문자열의 길이를 M이라고 하면, 위 코드의 시간복잡도는 O(NM)이다.
방법 2
#include <bits/stdc++.h>
using namespace std;
int freq[26]; // 0으로 초기화
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
for(auto e: str){
freq[e - 'a']++;
}
for(int i = 0; i < 26; i++){
cout << freq[i] << " ";
}
}배열을 이용하여 각 알파벳 소문자의 빈도를 저장하는 위 풀이의 시간복잡도는? O(N + M)
연습 문제 2
길이가 N인 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. (단, arr의 원소는 0 이상 100 이하이고, N은 1000 이하이다.)
func2({1, 52, 48}, 3) = 1
func2({50, 42}, 2) = 0
func2({4, 13, 63, 87}, 4) = 1
방법 1
1 23 53 77 60
위와 같은 배열이 있다고 해보자. 서로 다른 위치의 두 원소를 합해 100이 되는지 알아보자.
자기 자신을 제외한 N-1 개의 원소들을 모두 살펴보며 합이 100이 되는지 확인하는 방법이 있다.
이 과정을 N개의 원소에 대해 반복하면 결국 시간복잡도는 O(N^2)이 된다.
방법 2
시간복잡도를 O(N)으로 단축시킬 수 있는 방법이 있다.
바로 각 수의 등장 여부를 체크하는 배열을 만드는 것이다. arr의 각 수는 0 이상 100 이하이므로 원래는 101 칸의 배열을 만들어야 하지만, 아래 표에서는 일부 인덱스만 표시했다. 이 배열은 인덱스에 해당하는 수가 이전에 등장한 적 없으면 0, 있으면 1을 저장한다.
1과 더해서 100이 되는 수인 99가 이전에 등장한 적 있는가? 없다. -> 0
1은 방금 등장했으므로 배열의 값을 1로 바꾼다.
23과 더해서 100이 되는 수인 77이 이전에 등장한 적 있는가? 없다. -> 0
23은 방금 등장했으므로 배열의 값을 1로 바꾼다.
53과 더해서 100이 되는 수인 47이 이전에 등장한 적 있는가? 없다. -> 0
53은 방금 등장했으므로 배열의 값을 1로 바꾼다.
77과 더해서 100이 되는 수인 23이 이전에 등장한 적 있는가? 있다. -> 1
func2 함수에서 바로 1을 반환한다.
int func2(int arr[], int N){
// 각 원소의 등장 여부를 저장하는 배열
int occur[101] = {};
for(int i = 0; i < N; i++){
// arr[i]와 더해서 100이 되는 수가 나온 적 있는가?
if(occur[100 - arr[i]] == 1){
return 1;
}
// 현재 원소를 1로 표시
occur[arr[i]] = 1;
}
// 끝까지 발견되지 않으면 0 반환
return 0;
}배열 관련 문제
