[자료구조] 배열 (Array) : 선형 배열 (Linear Arrays)

🔆 자료 구조와 알고리즘 살펴보기 🔆

https://yoonhwis.tistory.com/135

자료구조와 알고리즘

 

---

배열

같은 타입의 변수들로 이루어진 유한 집합

 

 

 

---

 

선형 배열 (Linear Arrays)

선형 배열 Linear Arrays : 데이터들이 선처럼 일렬로 늘어선 형태이다.

 

선형 시간 (리스트 길이에 비례하여 걸리는 시간) : O(n)

 

배열 vs 리스트
배열이란 원소들을 순서대로 늘어놓은 것으로, 개념적인 구조, 즉 데이터를 늘어놓은 모양새를 말한다. 모든 원소가 같은 데이터 타입이어야 한다.
리스트는 데이터형을 가리킨다. 원소별로 다른 데이터 타입을 가져도 된다.

 

길이에 따라서 실행 시간이 달라지는 연산과 길이에 관계 없이 일정하게 빠른 속도로 실행되는 연산이 있다.

 

- 길이에 상관 없이 빠른 실행을 하는 연산 : append(), pop()

- 길이에 따라 실행 시간이 다른 연산 : insert(), del()

 

L = [10, 20, 40]

# 빠르게!
L.append(50)   # 마지막에 요소(50)를 추가한다.
L.pop()        # 맨 끝 요소를 삭제한다.

# 시간 고려..
L.insert(2, 30)   # 2번 인덱스에 요소(30)를 추가한다.
del(10)           # 요소 10을 삭제한다.

# 그 외
L.index(20)   # 요소 20의 인덱스를 출력한다.

 

 

 

(예제) 정렬된 리스트에 원소 삽입하기

Q. 일렬로 정렬된 리스트에 임의의 값을 갖는 원소를 삽입하라. 이 값은 제일 작을 수도 있고, 제일 클 수도 있고, 중간값일 수도 있다.

💡 힌트 : 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입한다.
⚠️ 주의 : 리스트 내에 존재하는 모든 원소들보다 작은 경우, 큰 경우, 혹은 중간값이 주어지는 경우에 대해서 각각 올바르게 처리해야 한다.

def solution(L, x):
    for l in L : 
        if L[-1] < x :
            L.append(x)
        elif l > x :
            L.insert(L.index(l), x)
            break
    return L

 

 

 

 

(예제) 정렬된 리스트에 원소 삽입하기

Q. 인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수를 작성하라.

💡 힌트 : 리스트의 index() 메서드와 리스트 슬라이싱을 활용한다.

⚠️ 주의 : 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킨다.

 

def solution(L, x):
    answer = []
    for l in L :
        if l == x :
            answer.append(L.index(l))
    return [i for i, l in enumerate(L) if l==x] if x in L else [-1]

힌트의 내용과 달리 나는 리스트 슬라이싱을 활용하지 않았다.

 

 

 

---

 

모든 자료 구조와 알고리즘에 대해 알아보고 싶다면?

https://yoonhwis.tistory.com/135

자료구조와 알고리즘