정의와 성질
배열은 메모리 상에 원소를 <<연속으로>> 배치한 자료구조이다.
원래 C++에서 배열을 선언한 뒤에 arr의 길이를 변경하는게 불가능하지만, 자료구조로써의 배열의 길이를 가변적으로 조절할 수 있다.
성질은 다음과 같다. 가볍게 읽고 넘어가기
기능과 구현
임의의 원소의 위치를 확인하거나 변경 -> O(1)
원소를 마지막에 추가 -> O(1)
마지막 원소를 제거 -> O(1)
임의의 위치에 원소 추가 -> O(N)
사진을 예시로 5번째 자리에 원소를 추가하려면, 뒤에 이미 존재하는 원소들도 모두 한칸씩 밀어내야 한다.
첫번째 위치에 추가할 때는 n번 실행, 마지막 위치에 추가할 때는 1번 실행이므로 평균적으로 n/2번이고, 시간복잡도는 O(N)이 된다.
임의의 위치에 원소 제거 -> O(N)
위 기능들을 직접 구현해보자.
//가장 오른쪽부터 한 칸씩 옮기는 방법. 임시변수나 추가 메모리가 필요하지 않다.
void insert(int idx,int num,int arr[],int& len){
for(int i=len; i>idx; i--){
arr[i] = arr[i-1];
}
arr[idx] = num;
len++;
}
void erase(int idx,int arr[],int& len){
len--;
for(int i=idx; i<len; i++){
arr[i]=arr[i+1];
}
}배열 전체를 초기화하는 팁
memset함수는 실수할 일이 많으니 권장 X
for문으로 일일이 초기화 하는 방법 또는
algorithm 헤더의 fill 함수 사용하기
STL vector
vector는 배열과 거의 비슷한 자료구조이지만 크기를 유동적으로 조절할 수 있는 장점이 있다.
insert, erase 함수는 배열과 마찬가지로 O(n)의 시간복잡도를, 마지막 위치에 원소를 추가,삭제하는 push_back, pop_back 함수는 동일하게 O(1)의 시간복잡도를 갖게 된다.
또 벡터에서 =를 사용하면 deep copy가 이루어진다.(16번 줄)
v4가 {1,2,4}가 된 이후 v4를 바꿔도 v3에는 영향을 주지 않는다.
벡터 원소 순회하기
첫번째 방법은 range based loop이다.
04번 줄에서, e는 v1의 모든 원소가 하나씩 들어가는 반복문이 된다.
int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e : v1이라고 하면 원본이 e에 들어간다.
그렇기 때문에 int e : v1라고 쓴 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만, int& e : v1이라고 쓴 for문 내에서는 e를 바꾸면 원본인 v1에서 실제 해당 원소의 값이 바뀌게 된다.
이 순회법은 list,map,set 등 다른 자료구조에서도 사용가능하지만 c++11을 지원해야 가능!
두번째로는 일반적인 for문을 사용하는 방법이다. 이때 주의해야 할 점은 12번 줄처럼 v1.size()-1로 사용하면 벡터 사이즈가 0이라면 unsigned int overflow가 발생하여 런타임 에러가 생긴다.
연습문제
문제1 백준10808 - 알파벳개수
freq 배열을 전역 변수로 선언한다면 초기값이 알아서 0으로 채워지기 때문에 따로 초기화를 하지 않았습니다. freq가 지역 변수였다면 int freq[26]; 이라고만 할 경우 0이 아닌 다른 쓰레기 값이 채워지기 때문에,
int freq[26] = {}
혹은 fill(freq, freq+26, 0);
과 같은 조치가 필요해짐.
내 코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string str;
int alphabet[30]={0};
cin >> str;
for(int i=0; i<str.length(); i++){
alphabet[str[i]-'a']++;
}
for(int i=0; i<26; i++){
cout << alphabet[i] << " ";
}
return 0;
}문제2
이전 강의에서 풀어본 문제를 O(N)풀이법으로 접근해보자.
위와 같은 배열이 있을 때, 만약 53을 본다면 배열 내부에 47이 있는 지 확인해야한다. 이를 한번에 찾기 위해서는?
0부터 100까지의 빈 배열을 하나 만든다.
해당 원소가 등장한 적이 있으면 1, 없으면 0으로 표시한다.
가장 첫번째 원소인 1부터 살펴보자. 100-1=99인 원소가 등장한 적이 없으므로 다음 원소로 넘어간다. 이때 넘어가기 전,원소 1을 방문하였으므로 배열의 1번 인덱스를 1로 바꾸어준다.
두번째 원소도 마찬가지로 100-23=77인 원소가 등장한 적이 없으므로 같은 방법으로 배열의 23번 인덱스를 1로 바꾼 뒤 넘어간다.
같은 방법으로 진행하며 네번째 원소를 보면, 100-77=23인 원소는 등장한 적이 있다. 따라서 합쳐서 100이되는 쌍을 발견하였으므로 1을 반환하면 된다.
코드는 위와 같다.
처음에는 정렬 후 투 포인터를 이용하는 방법밖에 생각이 안 났는데 해시 테이블 이용하면 되는구나,,
