[알고리즘(2)] Python으로 알아보는 배열(Array)

출처: flaticon

 

 

자료구조/알고리즘의 공부 순서, index 분류가 사람마다 달라서 헷갈릴 수도 있다.

학교, 스터디, 교육, 여러 사이트에서 분석한 결과 다음과 같은 순서대로 공부하면 좋다.

(사실 2번~8번까지는 자료구조의 범위이지만 이 자료구조를 응용하면

알고리즘이 되기 때문에 더 넓은 의미의 알고리즘이라는 명칭을 사용함)

 

[알고리즘 포스팅 순서]

1. 시간복잡도

2. 배열

3. 연결리스트

4. 스택

5. 큐

6. 트리

7. 그래프

8. 해쉬테이블

9. 정렬(선택, 버블, 삽입, 퀵, 힙, 병합)

10. 코테 대비 백준 문제 풀이 꿀팁

 

 

 

다음은 파이썬을 기준으로 공부해야 할 자료구조 모형도다.

파이썬에서 기본 제공하는 List, Dictionary, Tuple, Set에 대한 이야기는 생략하고

코테 대비를 위한 자료구조/알고리즘 중심으로 포스팅을 하려고 한다.

 

출처: https://www.edureka.co/blog/data-structures-in-python/

 

 

이제 본격적으로 알아보자,

[배열이란?]

배열은 같은 타입의 데이터들을 모아서 번호(인덱스)로 관리하는 데이터 타입(자료 구조)이다.

변수가 하나의 데이터만을 저장한다면 배열은 여러 데이터를 저장할 수 있다는 차이점이 있다.

 

[배열의 특징]

• 인덱스를 통해 임의 원소에 쉽게 접근할 수 있다.
• 원소를 추가하거나 삭제할 때는 시간이 걸린다.
• 스택, 큐, 힙, 해시 테이블, 행렬 등을 만들 때 사용한다.
• 정렬 알고리즘을 구현할 때도 사용한다.

 

[파이썬의 배열 특징]

1. 리스트와 같은 역할을 한다.

일반적으로 배열은 같은 타입의 데이터를 담는 자료 구조이고

리스트는 다양한 데이터를 담는 자료 구조이다.

그러나 파이썬은 디폴트로 리스트로 정의되므로 배열로 정의하고 싶을 시,

추가하는 데이터 타입이 모두 같은지 확인할 필요가 있다.

 

2. 동적 배열로 정의된다.

배열은 두 가지 타입이 존재한다. 바로, 동적배열(Dynamic)과 정적배열(Static)이다.

일반적인 C, C++, Java 등에서는 arr[5]와 같이 배열을 선언하면 정적배열이 되며

동적배열로 만들려면 new[], delete[]를 이용해야 한다.

그러나 파이썬은 디폴트로 동적배열로 정의되기 때문에 신경 쓰지 않아도 된다.

(만약, 정적배열로 구현하고 싶다면 튜플(Tuple)을 이용하는 방법도 있다.

하지만 튜플은 배열의 크기와 원소를 변경할 수 없기 때문에 배열보다도 고정적이다.)

 

[코드]

클래스로 배열과 다양한 기능들을 구현하는 코드를 작성해 보았다.

1. push_back(T data) : 현재 가변 배열 뒤에 원소를 삽입
2. pop_back() : 현재 가변 배열 뒤의 원소를 삭제
3. insert(Iterator index, T data): 가변 배열의 index위치에 원소를 삽입. index위치의 원소를 포함하여 (k> index) 위치에 있는 원소들은 뒤로 밀린다.
4. delete(Iterator index): 가변 배열의 index위치에 있는 원소를 삭제
5. at(Iterator i): 인덱스에 존재하는 원소의 레퍼런스(or 포인터)를 반환
6. size(): 현재 가변배열의 길이를 반환
7. clear(): 가변 배열을 초기화

class DynamicArray:
  def __init__(self):
    self.arr = []

  def push_back(self, data):# 가변배열 뒤에 원소 삽입
    self.arr.append(data)
    print(self.arr)

  def pop_back(self): # 가변배열 뒤 원소 삭제
    self.arr.pop()
    print(self.arr)

  def insert(self, index, data): # 특정 index에 원소 삽입
    if (index <= len(self.arr)):
      temp1 = self.arr[:index]
      temp2 = self.arr[index:]
      temp1.append(data)
      self.arr = temp1+temp2
      print(self.arr)
    else:
      print("인덱스가 범위를 벗어났습니다. ")

  def delete(self, index): # 특정 index의 원소 삭제
    if (index <= len(self.arr)):
      temp1 = self.arr[:index]
      temp2 = self.arr[index+1:]
      self.arr = temp1 + temp2
      print(self.arr)
    else:
      print("인덱스가 범위를 벗어났습니다.")

  def at(self, i): # 인덱스에 존재하는 원소의 레퍼런스 반환
    return print(id(self.arr[i]))

  def size(self): # 현재 길이 반환
    return print(len(self.arr))

  def clear(self): # 초기화
    self.arr = []
    print("clear")

  def printf(self):
    return print(self.arr)

## __main__ ##
array = DynamicArray()
array.printf()
array.push_back(3)
array.push_back(6)
array.push_back(9)
array.push_back(12)
array.insert(2,1)
array.pop_back()
array.delete(0)
array.at(2)
array.size()
array.clear()

-> main문을 실행시키면 다음과 같은 결과가 나타난다.

 

끄읏

 

[참고문헌]

1. 위키독스: https://wikidocs.net/189478

2. 블로그: https://www.edureka.co/blog/data-structures-in-python/

3. 블로그: https://web-km.tistory.com/52