[누구나 자료구조와 알고리즘] 1. 자료구조의 중요성

해당 포스팅은 누구나 자료구조와 알고리즘을 읽으며

정리한 내용입니다.

 

배열(기초자료구조)

• 배열은 컴퓨터 과학의 기초 자료중 하나

 

 

자료구조는 4가지

• 읽기

  • 자료구조 내 특정 위치를 찾는 것 혹은 특정 인덱스 값을 찾아 보는 것

• 검색

  • 자료 구조 내 특정 값을 찾는 것, 특정 값이 있는지 혹은 특정 값의 인덱스를 찾는 것

• 삽입

  • 자료 구조 내 슬롯을 새로 만들어 새로운 값을 추가하는 것

• 삭제

  • 자료 구조 내 값을 제거하는 것

 

연산이 빠른가에 대한 측정의 기준은 얼마나 많은 연산 단계가 필요한지가 기준이 됩니다.

시간은 연산을 실행하는 하드웨어의 성능에 따른 변수가 발생할 수 있기에 하드웨어의 조건을 동일하다 놓고 볼때

단계(Step)가 결국 성능을 결정합니다. 이러한 측정의 단위를 시간 복잡도, 성능, 효율성이라 표현합니다.

 

 

읽기

---

배열에서 읽기의 단계는 한단계입니다. 배열 내 특정 인덱스에 한번에 접근 하여 데이터를 확인 할 수 있기 때문입니다.

1. 컴퓨터는 모든 메모리의 주소에 한번에 접근 가능

2. 각 배열의 저장된 내용은 메모리의 시작 주소

3. 배열의 인덱스 시작은 0

이러한 조건들로 인해 한번에 접근하여 데이터를 확인 가능하며 길이가 5까지인 배열에서 인덱스 3의 위치를 읽는 단계는 다음과 같습니다.

1. 0부터 시작하는 인덱스의 메모리 주소를 확인

2. 0부터 3까지는 3칸을 이동하면 읽기 가능

3. 0의 메모리 주소인 1010에서 + 3을 하여 메모리주소 1013의 위치 확인

4. 해당 위치의 데이터 값을 반환

 

검색

---

검색은 읽기와 다르게 특정 값을 찾는 활동입니다. 예를들어 카드를 뒤집어 놓고 찾고자 하는 카드를 찾는 것과 동일합니다.

 

"Chelsea", "Arsenal", "Liverpool", "Juventus", "RealMadrid"

라는 배열이 있다고 가정합니다.

Liverpool을 찾는다면?

• 배열의 0번부터 하나씩 순차적으로 확인

  • 한 번에 하나씩 확인 하는 것 -> 선형검색

  • Liverpool을 찾을때 연산은 3단계

    • 이는 배열의 선형검색으로 인한 최대 단계수는 N

      • Ex) RealMadrid를 찾는 단계는 5단계 == 배열의 길이 5

   

삽입

---

삽입은 어느 위치에 삽입하는 것에 따른 효율성의 차이를 보입니다.

 

"Chelsea", "Arsenal", "Liverpool", "Juventus", "RealMadrid"

라는 배열이 있다고 가정합니다.

"AtleticoMadrid" 를 삽입하세요.

 

최적 삽입

• 맨 끝에 삽입

  • 1단계 End~

최악 삽입

• 맨 앞에 삽입

  1. 삽입을 위한 슬롯을 생성해야 합니다.

  2. 배열의 가장 끝인 4번 인덱스인 RealMadird는 5번 인덱스인 오른쪽으로 이동

  3. 빈 4번 인덱스 자리엔 3번 인덱스였던 Juventus가 이동

  4. 빈 3번 인덱스 자리엔 2번 인덱스였던 Liverpool이 이동.. 반복

  5. Chelsea가 1번 인덱스로 이동하여 빈 공간인 0번 인덱스에 AlteticoMadrid 삽입

  6. 이동 5회, 삽입 1회 총 6회 (N+1)

 

삭제

---

삭제는 특정 인덱스의 값을 삭제하는 것이며 삽입과 마찬가지로 맨 끝에 있는 것을 삭제하면 최적이지만 중간이나 앞에 있는 부분을 삭제하면 빈 슬롯이 생겨 이동 해야 하는 경우가 생깁니다.

 

"Chelsea", "Arsenal", "Liverpool", "Juventus", "RealMadrid"

라는 배열이 있다고 가정합니다.

"Juventus"를 삭제하세요.

1. Juventus 삭제

2. 삭제 후 빈 3번 인덱스의 슬롯의 위치로 RealMadrid 이동

삭제는 한 단계지만 삭제 후 빈 슬롯이 발생시 데이터를 이동시켜야 하는 단계가 추가적으로 발생합니다.

 

최적 삭제

• 삽입과 동일 (맨 끝)

최악 삭제

• 삽입과 동일 (맨 앞)

  • N

 

 

집합(중복 허용 X 자료구조)

 

집합은 중복 데이터가 없을 때 유용

이러한 제약은 효율성에 큰 영향

 

집합의 읽기

• 배열의 읽기와 동일

  • 1단계

집합의 검색

• 배열의 검색과 동일

  • 최대 N단계

집합의 삭제

• 배열의 삭제와 동일

  • 최대 N단계

집합의 삽입

• 중복데이터 허용이 되지 않기에 삽입하고자 하는 데이터 값이 기존 배열 있는지 확인 후 삽입해야 합니다.

  • 이는 검색이 우선시 되야 하는 제약

• 배열삽입의 최선삽입 1단계 -> 집합삽입 최선 N+1단계(검색 N + 삽입 1)

• 배열삽입의 최악삽입 N+1 -> 집합삽입의 최악 2N+1단계(검색 N + 이동 N + 삽입 1)

 

참고

---

• 누구나 자료구조와 알고리즘