[바킹독: 알고리즘] 배열

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

 

[목차]  정의와 성질, 기능과 구현, STL Vector, 연습 문제

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

출처: blog.encrypted.gg/927?category=773649

---

정의와 성질

배열은 메모리 상 원소를 연속하게 배치한 자료구조입니다. 자료구조로서의 배열은 길이를 줄이거나 늘릴 수 있다고 생각하겠습니다.

배열의 성질은 다음과 같습니다.

 

1. O(1)에 k번째 원소를 확인하고, 변경할 수 있습니다.
   
   
2. 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양( = overhead )가 거의 없습니다.
   
   
3. 메모리 상 데이터가 붙어있어 Cache hit rate가 높습니다.
   
   
4. 메모리 상 연속한 구간을 잡아야 해 할당에 제약에 걸립니다.
   
   

캐시메모리 적중률(Cache hit rate)

캐시메모리가 있는 컴퓨터 시스템은 CPU가 메모리에 접근하기 전, 먼저 캐시 메모리에 원하는 데이터의 존재 여부를 확인합니다. 이때 필요한 데이터가 있는 경우를 적중(hit), 없는 경우를 실패(miss)라고 합니다.

이때 요청한 데이터를 캐시메모리에서 찾을 확률을 적중률이라고 합니다.

 

---

기능과 구현

(1) 임의의 위치에 있는 원소를 확인 및 변경, O(1)

 

(2) 원소를 끝에 추가, O(1)

 

(3) 마지막 원소 제거, O(1)

 

(4) 임의의 위치에 원소 추가, O(N)

 

왜 '(4)'번은 시간복잡도가 O(N)일까요? 왜냐하면 중간에 추가함으로 그 뒤에 존재하는 책들을 뒤로 밀어야하기에 시간복잡도가 긴 것입니다. 추가하는 위치가 끝에 가까울수룩 시간은 줄어들고, 앞에 가까울수록 시간은 늘어납니다. 하지만 평균적으로 N/2를 밀어야하니 O(N)이라 합니다.
[ 참고. 빅오표기법 ]

 

(5) 임의의 위치에 원소 제거, O(N)

 

'(5)'번의 시간복잡도가 O(N)인 이유는 '(4)'번이 O(N)인 이유와 같습니다. 중간에 있는 원소를 삭제함으로, 그 뒤에 존재하는 원소들을 한 칸씩 앞으로 땡겨와야하기 때문입니다.
'제거하는 원소 위치만 비워두면 되지 않을까' 생각할 수 있지만, 그렇게 될 경우 메모리 상 원소가 연속해 존재하지 않기 때문에 배열의 정의도 위배되며, k번째 원소를 O(1)의 시간복잡도로 찾을 수 없게 됩니다.

 

(4)번과 (5)번을 구현해보도록 하겠습니다.

 

주석에도 있지만, 이런 경우 자바는 ArrayList를 쓰는게 가장 좋습니다..ㅎㅎ

 

---

STL Vector

원소가 메모리에 저장되어 있어 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있습니다. Vector는 배열과 달리 크기를 유동적으로 관리할 수 있습니다.

 

자바에서는 ArrayList가 많이 쓰이고 있습니다. add method와 remove(Object o) method의 시간복잡도를 O(1)이라 착각할 수 있지만, 전혀 아닙니다! 마찬가지로 O(N)입니다.

 

---

연습 문제

(1) BOJ 10808번 : 알파벳 갯수

10808번: 알파벳 개수

 

(2) 0x01강의 문제 2번 [ 아래의 문제를 시간복잡도 O(N)으로 풀이하라. ]

 

출처 - 바킹독 ( https://www.youtube.com/watch?v=mBeyFsHqzHg )

하늘 풀이

바킹독 님 풀이

 

더 메모리를 사용할 필요 없이 깃발을 꼿는 배열을 만들어, 해당 값의 차이 값이 이전에 등장하였을 경우 1을 반환합니다. 제가 짠 코드의 경우 시간복잡도가 O(N의 2승)을 못 벗어났습니다. [ 반복문을 진행해 또 하나의 배열을 만들었기 때문이죠. ] 하지만 해당 풀이의 경우 반복문이 추가로 필요하지 않고, 배열로 값의 등장을 체크해 시간복잡도를 낮추어 문제를 풀 수 있었습니다.

 

 

---

 

바킹독 님이 올려주신 BOJ 문제집

encrypted-def/basic-algo-lecture

 

문제집: 0x03강 - 배열 (BaaaaaaaaaaarkingDog)

---

백준 3273번 꼭 다시 풀어보기.