자료구조와 알고리즘 2 - 선형 배열 <'어서와! 자료구조와 알고리즘은 처음이지?' Python 강의 정리>

강의링크 - https://school.programmers.co.kr/learn/courses/57

프로그래머스

 

이전 강의 : 1강 개요 및 배경 https://lbsdatastat.tistory.com/196

자료구조와 알고리즘 1 - 개요 및 배경 <'어서와! 자료구조와 알고리즘은 처음이지?' Python 강의 정

 

 

1) 선형 배열 (Linear Arrays)

선형 배열은 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말합니다. 보통 프로그래밍에서 배열 (array) 이라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻하는데요, Python 에서는 서로 다른 종류의 데이터 또한 줄세울 수 있는 리스트 (list) 라는 데이터형이 있습니다.

이 강의에서는 같은 종류의 데이터가 줄지어 늘어서 있는 배열을 이용하려 합니다. 앞으로 배열 (array) 이라는 말과 리스트 (list) 라는 말이 자주 등장할 겁니다만, 우선은 같은 것이라고 생각해도 좋지만, 개념적인 구조, 즉 데이터를 늘어놓은 모양새를 말할 때는 배열 (array), Python 의 데이터형을 가리킬 때에는 리스트 (list) 라는 용어를 사용하겠습니다.

또한, 제 7 강부터는 "연결 리스트 (linked list)" 라는 용어가 등장하게 되는데, 이것과는 구별되어야 합니다. 그것은 그때 가서 다시 얘기하기로 해요.

 

2) Python 리스트에 활용할 수 있는 연산들

리스트 길이과 관계 없이 빠르게 실행 결과를 보게되는 연산들

• 원소 덧붙이기 .append()
• 원소 하나를 꺼내기 .pop()

위 연산들은 리스트의 길이와 무관하게 빠르게 실행할 수 있는 연산들입니다. 리스트의 길이가 아무리 길어도 맨 끝에 요소 하나를 추가하는 것이나 맨 끝 요소 하나를 빼는건 빠르게 할 수 있는 일이죠. 반면, 리스트가 커지면 그에 따라 실행시간이 길어지는 연산들도 있습니다.

 

∴ 순식간에(빠르게) 할 수 있는 일 → 리스트의 길이와 무관 (상수 시간) → O(1)

 

리스트의 길이에 비례해서 실행 시간이 걸리는 연산들

• 원소 삽입하기 .insert()
• 원소 삭제하기 .del()

이런 연산들은 리스트의 길이가 길면 길수록 처리가 오래 걸리게 됩니다. 구체적으로 말하면 리스트의 길이예 실행 시간이 비례합니다. 리스트 길이가 100 배가 되면, 위 연산들을 실행하는 데 걸리는 시간도 100 배 커집니다.

 

∴ 리스트의 길이가 길면 오래 걸리는 일 → 리스트의 길이에 비례 (선형 시간) → O(n)

 

추가 다른 연산

• 원소 탐색하기: .index()

 

3) Python에서의 리스트

 

 

4) 연습문제 1. 정렬된 리스트에 주어진 원소 삽입하기

💡 문제 설명

리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요.

인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다.

예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다.

힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다.

 

주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다.

def solution(L, x):
    for i in range(len(L)):
        if L[i] > x:
            return L[:i] + [x] + L[i:]
    L.append(x)
    return L

테스트 1
입력값 〉	[20, 37, 58, 72, 91], 65
기댓값 〉	[20, 37, 58, 65, 72, 91]
실행 결과 〉	테스트를 통과하였습니다.

→ 조건문과 슬라이싱을 활용하여 인덱스를 찾아 원소를 삽입하게 되었습니다.

 

def solution(L, x):
    L.append(x)
    L.sort()
    return L

그런데 '다른 사람의 풀이'를 보니, 그냥 정렬 함수 sort()를 써도 해결된다고 하더군요.

 

 

5) 연습문제 2. 주어진 리스트에서 특정 원소를(여러 번 들어있을 수 있음) 모두 찾아내기

💡 문제 설명

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

리스트 L 은 정수들로 이루어져 있고 그 순서는 임의로 부여되어 있다고 가정하며, 동일한 원소가 반복하여 들어 있을 수 있습니다. 이 안에 정수 x 가 존재하면 그것들을 모두 발견하여 해당 인덱스들을 리스트로 만들어 반환하고, 만약 존재하지 않으면 하나의 원소로 이루어진 리스트 [-1] 를 반환하는 함수를 완성하세요.

예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 72 인 경우의 올바른 리턴 값은 [1, 3] 입니다.또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 83 인 경우의 올바른 리턴 값은 [2] 입니다.마지막으로 또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 49 인 경우의 올바른 리턴 값은 [-1] 입니다.

 

힌트 1: 리스트의 index() 메서드와 리스트 슬라이싱을 활용하는 것이 한 가지 방법이 됩니다. 리스트 슬라이싱은 아래와 같이 동작합니다.

L = [6, 2, 8, 7, 3] 인 경우

L[1:3] = [2, 8]

L[2:] = [8, 7, 3]

L[:3] = [6, 2, 8]

힌트 2: 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킵니다. 이것을 try ... except 로 처리해도 되고, "if x in L" 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다.

 

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

테스트 1
입력값 〉	[64, 72, 83, 72, 54], 72
기댓값 〉	[1, 3]
실행 결과 〉	테스트를 통과하였습니다.

테스트 2
입력값 〉	[64, 72, 83, 72, 54], 83
기댓값 〉	[2]
실행 결과 〉	테스트를 통과하였습니다.

테스트 3
입력값 〉	[64, 72, 83, 72, 54], 49
기댓값 〉	[-1]
실행 결과 〉	테스트를 통과하였습니다.

테스트 결과 (~˘▾˘)~

3개 중 3개 성공

 

→ 마찬가지로 조건문을 활용하여 원소 x가 리스트 L에 없으면 반환을 위한 리스트 [-1] 를 추가하고, 원소가 리스트에 있으면 인덱스 값을 answer 리스트에 리턴해 주었습니다.

 

def solution(L, x):
    if x in L:
        return [i for i, y in enumerate(L) if y == x]
    else:
        return [-1]

'다른 사람의 풀이'에서는 enumerate() 메서드를 활용하여 코드를 간소화한 모습이 있었습니다. 반복문을 작성하기 위해 해당 함수를 활용한다는데, 이 부분에 대해서는 아래 링크의 글과 함께 더 자세히 배워야겠다고 생각했습니다.

(※ 참고자료 - https://www.daleseo.com/python-enumerate/)

파이썬의 enumerate() 내장 함수로 for 루프 돌리기

 

 

다음 강의 : 3강 정렬과 탐색 (Sorting & Searching)