python 을 활용한 자료구조와 알고리즘 공부 - (1)

이 필기내용은 프로그래머스 홈페이지의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 들으면서 제가 필기한 내용입니다.

 

어서와! 자료구조와 알고리즘은 처음이지?  https://programmers.co.kr/learn/courses/57

어서와! 자료구조와 알고리즘은 처음이지? | 프로그래머스

 

---

<<선형 배열(Linear Array)>>

 

> 선형 배열은 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말한다.

 배열 (array)은 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻한다.

Python 에서는 '서로 다른 종류의 데이터 또한' 줄세울 수 있는 리스트 (list) 라는 데이터형이 있다.

이것이 리스트의 장점이다. 서로 다른 자료형들을 가진 원소들도 저장할수있다.

여기에서는 선형 리스트(배열)을 파이썬 문법을 바탕으로 살펴볼것이다.

선형 리스트(배열)은 연결 리스트와는 다르다.

 

---

연산에 따른 수행속도 비교

 

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

 

> 원소 덧붙이기 .append()

> 원소 하나를 꺼내기 .pop()

 

=>위 연산들은 리스트의 길이와 무관하게 빠르게 실행할 수 있는 연산들이다. 

리스트의 길이가 아무리 길어도 맨 끝에 요소 하나를 추가하는 것이나 맨 끝 요소 하나를 빼는건 빠르게 할수 있다.

=> 리스트의 길이와 무관  

=> 상수시간 -> O(1) 

---------------------------------------------------------------------------------

<<리스트의 길이에 비례해서 실행 시간이 오래 걸릴 수 있는 연산들>>

 

> 원소 삽입하기 .insert()   : 삽입하고자 하는 위치의 뒤에 있는 원소들을 한칸씩 다 뒤로 밀어야한다.

> 원소 삭제하기 .del() : 삭제하고자 하는 위치의 뒤에 있는 원소들을 한칸씩 다 앞으로 당겨야한다.

 

=> 이 연산들은 리스트의 길이에 비례해서 실행시간이 걸린다. 

리스트 길이가 100 배가 되면, 위 연산들을 실행하는 데 걸리는 시간도 100 배 커진다.

=> 선형 시간 -> O(n)

 

ex)

L = [20,37,58,72,91]
L.insert(3,65) #인덱스 3에 65를 삽입
print(L) #[20,37,58,65,72,91]
 
del(L[2]) #인덱스 2에 해당하는 원소를 삭제
print(L) #[20,37,65,72,91]
 
L.pop(2) 
print(L) #[20,37,72,91]

---------------------------------------------------------------------------------

<<추가적인 다른 연산>>

 

>> 원소 탐색하기 (index) : 원소가 어느위치에 있느냐에 따라 수행속도가 달라질수있다.

 

L = ['20','37','58','72','91']

print(L.index('72'))  #'72'가 리스트 L에서 몇번째 인덱스에 위치하는가? 3번쨰 인덱스!  3이 출력된다.

---

실습 문제 1)  리스트에 새로운 요소 삽입하기

 

리스트 L과 정수 x가 주어질때, 리스트 내에 x를 삽입한 다음 그 리스트를 반환하는 함수를 완성하여라

입력은 구현할 필요 없고, 그 함수만 완성하기

리스트 L은 오름차순으로 정렬되어있다.

예를 들어, L = [1,3,5,7,9] 이고 x = 6 인 경우, [1,3,5,6,7,9]를 반환해야 한다.

또한, insert() 를 이용하여 삽입해야함

 

 

1번의 정답)

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

---

실습 문제 2) 리스트에서 원소 찾아내기

 

리스트 L에서, 원소 x가 발견되는 모든 위치의 인덱스를 구하여 그 인덱스들을 모아놓은 리스트를 반환하는 함수를 만들어라. 리스트 L은 정렬되어있지 않으며, 동일한 원소가 반복하여 들어 있는 경우도 있다. 만약 그 원소가 존재하지 않으면 그냥 [-1]을 반환해야된다.

 

 

예를 들어, L = [6,4,2,5,2,3] 이고 x = 2면 [2,4]가 반환되어야한다.

또한, L = [1,3,5,7,9] 이고 x = 4면 [-1]가 반환되어야 한다.

 

index()함수를 통해 원소의 인덱스를 구할수있다.

 

2번의 정답)

def solution(L, x):
    answer = []
    for idx, value in enumerate(L):
        if value == x:
            answer.append(idx)
    if len(answer) == 0:
        answer = [-1];
    return answer