.append() : 리스트의 맨 마지막에 원소 추가
.pop() : 리스트의 맨 마지막 원소 제거
리스트의 길이와 무관하게 상수시간(O(1))에 연산 가능
.insert(index, val): 원하는 위치 index에 원하는 val 추가
.del(val) : val와 동일한 원소 제거
리스트의 길이에 따라 연산 시간 변함(O(n))
- pop/del 차이
- pop: index로 원소 제거
- del: 값으로 원소 제거
- .index(val)
- val의 위치 index 반환
실습2-1.
리스트 L 과 정수 x 가 인자로 주어질 때 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요
주의) 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다.
def solution(L, x):
for i, v in enumerate(L):
if v > x:
L.insert(i, x)
break
elif L[-1] < x:
L.append(x)
return L실습2-2.
인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수 solution 을 완성하세요.
def solution(L, x):
answer = list()
for i, v in enumerate(L):
if v == x:
answer.append(i)
else:
continue
return answer- 배열 - 정렬과 탐색
정렬(sort)Permalink
리스트 내의 원소를 오름차순 or 내림차순으로 정렬하는 것
default는 오름차순
- sorted()
- 내장함수
- 정렬된 새로운 리스트를 얻어냄
원래의 리스트는 변화 없음
- sort()
- 리스트의 메서드
- 해당 리스트 자체를 정렬함
reverse=True 인자를 추가하면 내림차순으로 정렬가능
문자열의 경우 사전 순으로 정렬
‘key = ‘ 인자를 추가하면, 원하는 기준으로 정렬가능
(조건을 충족하는 인자가 중복되어 있을 경우에는 원래의 리스트의 순서대로 정렬됨)
탐색 알고리즘 (1) - 선형(순차) 탐색
- 리스트를 처음부터 마지막까지 순서대로 탐색하는 방법
- 리스트의 길이에 비례하는 시간 소요
O(n)의 시간 복잡도를 가짐
최악의 경우 배열의 모든 원소를 탐색해야 되는 경우가 발생할 수 있다
탐색 알고리즘 (2) - 이진 탐색
- 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
- 크기 순으로 정렬되어 있다는 성질 이용
- 값을 찾기 위해 리스트의 크기를 줄여나가며 탐색
- 한 번 비교가 일어날 때마다 리스트 반식 줄임(divde & conquer)
O(logn)의 시간 복잡도를 가짐
이진 탐색이 선형 탐색보다 보통의 경우 더 빠르긴 하지만, 기본적으로 정렬을 해야되기 때문에 무조건적으로 이진 탐색이 더 빠른 것은 아니다. 따라서, 경우에 따라서 적절히 탐색 알고리즘을 선택해야 사용해야 한다.Permalink
실습3.
리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.
def solution(L, x):
# 탐색을 시작할 처음 시작점(lower)과 끝점(upper)지정
lower = 0
upper = len(L) - 1
# while 반복문을 이용하여 lower과 upper를 갱신하며 탐색
while lower <= upper:
# 갱신된 lower과 upper로 middle 값 계산
middle = (lower + upper) // 2
# 계산된 middle 값을 index로 L 리스트 내의 원소 값과 찾고자 하는 x 값 비교
if L[middle] == x:
return middle
elif L[middle] < x:
lower = middle + 1
else:
upper = middle - 1
# 찾고자 하는 값이 없을 경우에는 -1 return
return -1- 재귀 알고리즘 - 기초(Recursive Algorithms)Permalink
재귀 함수란?
하나의 함수에 자신을 다시 호출 하여 작업을 수행하는 것
- 재귀 알고리즘의 종료 조건을 설정하는 것이 매우 중요
- 시간 복잡도가 반복문과 동일하더라도 효율성 측면에서 함수를 계속해서 호출해야 하기 때문에 반복문보다 효율성에서 떨어질 수 있음
ex) 이진 트리(binary tree), 자연수의 합 구하기, 조합의 수, 하노이의 탑, 피보나치 수열
실습4. 재귀 함수 풀이
인자로 0 또는 양의 정수인 x 가 주어질 때, Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.
# 재귀함수(피보나치 수열)
def solution(x):
if x >= 2:
return solution(x - 1) + solution(x - 2)
else:
return x# 반복문 풀이
def solution(x):
f0 = 0
f1 = 1
# 입력된 x 인자 만큼 반복
for _ in range(x):
# f0, f1 변수를 동시에 갱신하며 연산 진행
f0, f1 = f1, f0 + f1
print(f0, f1)
# f0를 최종값으로 반환
return f0실습 3. 의 이진 탐색을 재귀 알고리즘으로 풀이
재귀호출을 위해 lower, upper도 함수의 인자로 추가
# 이진탐색 재귀함수로 풀이 def solution(L, x, l, u): # 예외 조건 if l > u: return -1 else: middle = (l + u) // 2 if L[middle] == x: return middle elif L[middle] > x: return solution(L, x, l, middle - 1) else: return solutIon(L, x, middle + 1, u)
