선형 배열(Linear Array)

알고리즘(algorithm)이란?

• [사전적 정의] 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
• [프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
• 해결하고자 하는 문제에 따라(응용 종류와 범위에 따라) 최적의 해법은 서로 다르다! -> 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 함

---

1강 실습: 리스트 원소 두 개의 합 구하기

def solution(x):
    return x[0] + x[-1]

---

배열(Arrays)

같은 종류의 데이터가 줄지어 늘어서있는 자료 구조를 의미한다. 파이썬에서는 리스트(List) 자료구조가 이와 비슷하게 사용된다.

 

리스트(배열) 연산

• 원소 덧붙이기

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

• 끝에서 꺼내기

L = ['Bob', 'Cat', 'Spam', 'Programmers', 'New']
L.pop() # New를 반환해줌

📌 두 연산다 상수 시간안에 끝낼 수 있음. $O(1)$

 

• 원소 삽입하기
• 원소 삭제하기

L = [20, 37, 58, 72, 91]
L.insert(3, 65) # index 3의 위치에(네번 째) 원소 65를 삽입하라
print(L) # [20, 37, 58, 65, 72, 91]

del(L[2]) # 리스트 L의 index 2의 위치(세 번째) 원소를 삭제하라
print(L) # [20, 37, 65, 72, 91]
print(L.pop(2)) # 65 삭제 후 반환해줌.
print(L) # [20, 37, 72, 91]

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

• 원소 탐색하기

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

---

2강 실습: (1) 리스트에 새로운 요소 삽입하기

뭔가 복잡하게 푼 느낌,,,, 진짜 무지성으로 풀었던것 같다.

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

너무 생각없이 푼것 같아 다시 정리해서 푼 코드

def solution(L, x):
    idx = 0
    for i in range(len(L)):
        if x > L[i]:
            idx += 1
    L.insert(idx, x)
    return L

---

2강 실습: (2) 리스트에서 원소 찾아내기

def solution(L, x):
    answer = []
    diff = 0
    while True:
        if x in L:
            idx = L.index(x)
            answer.append(idx+diff)
            L = L[idx+1:]
            diff += idx + 1
        else:
            break
    if len(answer) == 0:
        return [-1]
    return answer