[강의정리] [배열] 실전 알고리즘 0x03 정리

바킹독의 [실전 알고리즘] 0x03강 - 배열 정리.

 

-배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능
   시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문.
2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
   다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다.
3. Cache hit rate가 높음
   메모리 상에데이터들이 붙어 있으니까.
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

-시간 복잡도

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

 

-배열 전체를 특정값으로 초기화

1. for문으로 값을 하나하나 다 바꾸는 방식 : 무난
2. algorithm 헤더의 fill함수 사용
   
   

int a[21];
fill(a, a+21, 0);

 

- STL Vector

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

배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점.

• insert, erase는 배열에서 우리가 구현한 것과 비슷하게 시간복잡도가 O(N)
• push_back, pop_back은 제일 끝에 원소를 추가하거나 빼는 것이니 O(1)

이 사실을 깜빡해서 잘못된 시간복잡도로 문제를 접근하는 경우를 막기 위해서 메소드의 시간복잡도를 잘 생각!

 

• vector에서 =를 사용하면 깊은 복사가 발생

vector<int> v3 = {1,2,3,4}
vector<int> v4;
v4 = v3; // {1,2,3,4} -> deep copy!
v4.pop_back(); // {1,2,3} -> v4를 바꿔도 v3에 영향 X
v4.clear(); // {}

 

 

- 연습문제들

https://jjpearl.tistory.com/46?category=1033721 

[백준 - 10808번] [배열] 알파벳 개수

 

(0x01강의 연습문제)

주어진 길이 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

 

포인트는 O(n^2) 알고리즘 말고 O(n) 알고리즘 풀이로 생각하는 것.

// 백준 알파벳 개수 문제랑 비슷한 알고리즘으로 풀면 됨.
// 숫자가 등장했는지 확인하는 배열을 확인하면 O(n) 시간 안에 풀 수 있다
// 핵심 포인트는 나와 합해서 100이 되는 수의 존재 여부를 O(N)이 아닌 O(1)에 알아차리는 것이고,
// 이걸 배열을 이용해서 해결할 수 있습니다. 그 방법은 바로 각 수의 등장 여부를 체크하는 배열을 만드는 것입니다.  
// 이전에 등장한적 잇으면 1, 아니면 0
int func2(int arr[], int N)
{
	int check[101] = {};
	for (int i = 0; i < N; ++i)
	{
		if (check[100 - arr[i]])
			return 1;
		check[arr[i]] = 1;
	}
	return 0;
}

https://jjpearl.tistory.com/47

[백준 - 2577번] 숫자의 개수

https://jjpearl.tistory.com/48

[백준 - 1475번] 방 번호

https://jjpearl.tistory.com/49

[백준 - 3273번] 두 수의 합

https://jjpearl.tistory.com/50

[백준 - 10807번] 개수 세기