배열

정의

메모리 상에 원소를 연속하게 배치한 자료구조

성질

1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
3. Cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

기능과 구현

• 임의의 위치에 있는 원소를 확인/변경: O(1)
• 원소를 끝에 추가: O(1)
• 마지막 원소를 제거: O(1)
• 임의의 위치에 원소 추가: O(N)
• 임의의 위치에 원소 제거: O(N)

사용 팁

전체를 특정 값으로 초기화시킬 때 사용하는 효울적인 방법

1. memset()

#include <string.h>
using namespace std;

int a[21];
int b[21][21];

int main(void) {
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);
    
	returnn 0;
}

실수할 여지가 많음 -> 비추천

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()

#include <algorithm.h>
using namespace std;

fill(a, a + 21, 0);
for (int i = 0; i < 21; i++)
	fill(b[i], b[i] + 21, 0);

실수할 여지도 없고 코드 짧음 -> 가장 추천!!

4. 전역 vs 지역

int arr[3] = {}; // 0으로 초기화

전역변수는 선언만 하면 자동으로 0으로 초기화됨.

vector

정의

배열과 거의 동일한 기능을 수행하는 자료구조

성질

크기를 자유자재로 늘이거나 줄일 수 있다.
인접 리스트에 많이 사용

사용법

https://cplusplus.com/reference/vector/vector/

v.begin()
iterator 공부하기

기능과 구현

• insert, erase : O(N)
• push_back, pop_back : O(1)
• push_front, pop_front : O(N)

vector에서 = 사용하면 deep copy 발생한다.

v4 = v3; // 1 ,2 ,4

이후에 v4를 바꿔도 v3에 영향을 주지 않는다.

모든 원소 순회

range-based for loop

for (int e: v1)
	cout << e << ' ';

배열은 데이터를 자주 바꾸지 않고 그냥 쌓아두고 싶을 때 활용할 수 있다
입력을 담아두기 위해 사용

인덱스에 빠르게 접근하는 목적으로 배열을 사용하면 효율적인 문제
10808 알파벳 개수

연습문제

1 23 53 77 60

수를 차례로 하나씩 읽으면서 이전에 등장한 수 중에서 지금 보고 있는 수와 더해 100이 되는 수가 있는지를 알고싶음
ex) 53이라면 1, 23 중에서 47이 등장했는지 확인
나와 합해서 100이 되는 수의 존재 여부를 O(1) -> 배열로 가능

뺀 수를 배열에 저장해놓고 비교하면 된다. -> 이렇게 생각했으나 결국 n개의 원소를 n번 비교해야 하니 O(n^2)이라 똑같다.

#include <bits/stdc++.h>
using namespace std;
int sub[100];
int func2(int arr[], int N)
{
	for (int i = 0; i < N; i++) 
		sub[i] = 100 - arr[i];
		
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			if (sub[i] == arr[j]) return 1;
	}
	return 0;
}

int main(void) {
	ios::sync_with_stdio(0);
  	cin.tie(0);
  	
  	int arr[] = {1, 33, 53, 77, 60};
	cout << func2(arr, 5); 
		
  	
  	return 0;
}

-> X

각 수의 등장 여부를 체크하는 배열 만들기
101칸짜리 배열 생성
0-100

해당 인덱스의 수가 이전에 등장한 적이 없으면 값이 0, 있으면 1
53을 보면 47번째 인덱스가 이전에 등장한 적이 있는지 (1인지) 확인
1과 더해서 100이 되는 수 99의 인덱스의 값은 0이므로 등장 x
다음 수로 넘어가기 전에 1이 등장했다는 것을 배열에 표시

int func2(int arr[], int N)
{
	int occur[101] = {};
	for (int i = 0; i < N; i++) {
		if (occur[100 - arr[i]]) return 1;
		else occur[arr[i]] = 1;
	}
	return 0;
}