[(Programmers 강의) Algorithm with Data Structure 02강. 선형 배열(Linear Array)]

선형 배열(Linear Arrays)

1. 선형 배열이란?

• 데이터들일 선(line)처럼 일렬로 쭉 늘어선 형태를 가져 붙여진 이름

• Python에서는 이 배열을 List를 통해 구현할 수 있음

  • 배열(Arrays) : 같은 종류의 데이터가 줄지어 늘어서 있는 것.

  • Python에서는 따로 배열 자료형(Data type)이 존재하지 않음.

  • 대신 리스트(List)라는 자료형 제공

    • 타언어의 배열보다는 융통성이 있음

• 배열 : 원소들을 순서대로 늘어놓은 것.

보통 배열의 인덱스는 0부터 시작

Python도 마찬가지

• Python 에서의 리스트(List)

• 다른 언어에서의 배열은 한 종류의 데이터만 취급

• 파이썬은 여러 종류의 데이터를 취급할 수 있다는 점에서 융통성이 있다.

  • 문자열의 길이가 다 달라도 됨.

  • 리스트의 각 원소가 서로 다른 데이터 타입을 가지고 있어도, 리스트로 취급할 수 있음.

L = ['Bob', 'Cat', 'Spam', 'Programmers']

직접 만들어보자!

L = ['Bob', 'Cat', 'Spam', 'Programmers']
print(L)
print(L[1])
print(L[-2])

['Bob', 'Cat', 'Spam', 'Programmers']
Cat
Spam

리스트 (배열) 연산 1

• (1) 원소 덧붙이기

• (2) 끝에서 꺼내기

L.append('New')           # (1)
print(L)
print(L.pop())            # (2)
print(L)

['Bob', 'Cat', 'Spam', 'Programmers', 'New']
New
['Bob', 'Cat', 'Spam', 'Programmers']

• 이러한 연산들은 순식간에(빠르게) 할 수 있는 일

  • 리스트의 길이와 무관 (상수 시간)

  • 빅오표기법(Big O Notation)으로 O(1)

    • 나중에 배울 것!

리스트 (배열) 연산 2

• (1) 원소 삽입하기

• (2) 원소 삭제하기

• 위 연산들은 리스트의 길이(크기)가 커질수록 연산량 증가, 실행 속도 감소

L = [20, 37, 58, 72, 91]
L.insert(3, 65)    # (1)
L

[20, 37, 58, 65, 72, 91]

• 리스트 3번 인덱스 자리에 65를 삽입하기 위해 일어나는 과정

  • 배열 크기 + 1

  • 91의 인덱스 + 1

  • 72의 인덱스 + 1

  • 3번 인덱스에 65 삽입

del(L[2])    # (2)
L

[20, 37, 65, 72, 91]

• 리스트 2번 인덱스 자리에 있던 원소를 삭제하는 과정

  • 2번 자리에 있던 58 삭제

  • 65의 인덱스 - 1

  • 72의 인덱스 - 1

  • 91의 인덱스 - 1

  • 리스트의 크기 - 1

• 이러한 연산들은 리스트의 길이가 길어질수록 오래걸리는 일

  • 리스트의 길이에 비례(선형 시간)

  • 빅오표기법(Big O Notation : O(n)

리스트 (배열) 연산 3

• (1) 원소 탐색

L = ['Bob', 'Cat', 'Spam', 'Programmers']
L.index('Spam')

2

• ‘Spam’ 원소가 리스트 내에 있는지 탐색하는 과정

2. 과제 : 프로그래머스 테스트에 익숙해지기

2강 실습 (1)

Link

• 정렬된 리스트에 주어진 원소 삽입하기

• 힌트

  • (1) 주어진 원소를 삽입할 위치를 찾는다.

  • (2) 해당 위치에 원소를 삽입한다.

  • 결과는 여전히 정렬된 상태를 유지하는 리스트여야 한다.

def solution(L, x):
    for i in range(len(L)):
        if L[i] > x:
            L.insert(i, x)
            break
        if L[-1] < x:
            L.append(x)
    return L

2강 실습 (2)

Link

• 주어진 리스트에서 특정 원소 탐색

  • 단, 원소가 여러개일 수 있음

• 힌트

  • index() 메소드 이용

  • 리스트 슬라이싱 이용

def solution(L, x):
    answer = []
    if x in L:
        for i in range(len(L)):
            if L[i] == x:
                answer.append(i)
    else:
        answer.append(-1)             

    return answer