데브코스-데이터엔지니어링
선형배열, 정렬, 탐색, 재귀, 시간복잡도
묠니르묘묘
2024. 3. 25. 17:33
데이터 엔지니어링 데브코스 Day 1
- 자료구조 및 알고리즘 풀기 1
🚀 선형 배열 (Linear Array)
- 배열은 원소들을 순서대로 늘어놓은 것 : [1, 3, -9, 10, 4]
- 배열의 각각의 원소에는 번호가 있는데 이를 index(인덱스)라 함
- index 는 0부터 시작함
- 마지막 인덱스부터 첫 번째 인덱스까지 접근하려면 -1 부터 -1씩 증가시키면 됨
- 파이썬에서는 서로 다른 종류의 데이터 또한 줄세울 수 있는 list(리스트) 라는 데이터형 있음
🖥 리스트에 활용할 수 있는 연산들
1. 리스트 길이와 관계 없이 빠른 실행 결과를 보여주는 연산
- 원소 덧붙이기 : `.append(추가할원소)`
- 리스트 끝에 추가함
- 끝에서 원소 하나 꺼내기 : `.pop()'
- a번째 원소 하나 꺼내기 : `.pop(a)`
- `pop()` 연산은 해당 원소를 꺼내고 리스트에서 삭제함
2. 리스트 길이에 비례하여 실행 시간이 걸리는 연산
- 원소 삽입하기 : `.insert(a,b)`
- 리스트의 a번째 위치에서 b를 삽입
- 원소 삭제하기 : `.del(L[x])` or `del L[x]`
- 리스트 L의 x번째 요소값을 삭제
- 원소 탐색하기 : `.index(a)`
- 리스트에 a 값이 있으면 a의 인덱스 리턴
🚀 정렬(Sort)
- 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업
- 파이썬 내장 함수 : `sorted(L)`
- 정렬된 새로운 리스트 반환
- 원본 리스트 L은 변경 X
- 리스트에 쓸 수 있는 메서드 : `.sort()`
- 해당 리스트를 정렬
- 정렬의 순서를 반대로 하려면 `reverse=True` 옵션 추가
- `L2 = sorted(L, reverse=True)`
- `L.sort(reverse=True)`
숫자(number)가 아닌 문자열을 정렬할 때는 사전순으로 정렬함.
이 때, 문자열 길이가 더 크다고 더 큰 문자로 취급 X
Python 문자열은 대문자가 소문자에 비해 무조건 우선.
예시
L = ['abcd', 'xyz', 'spam']
sorted(L, key=lambda x: len(x))
# ['xyz', 'abcd', 'spam']
L = ['spam', 'xyz', 'abcd']
sorted(L, key=lambda x: len(x))
# ['xyz', 'abcd', 'spam']
## 사전(dictionary)를 정렬하는 방법 중 이름순으로 하는 방법
L = [{'name' : 'John', 'score' : 83},
{'name' : 'Paul', 'score' : 92}]
# 레코드들을 이름순 정렬
L.sort(key=lambda x: x['name'])
# 레코드들을 점수가 높은순으로 정렬
L.sort(key=lambda x: x['score'], reverse=True)- `key` 매개변수는 정렬의 기준이 됨
- `lambda x: len(x)` 는 각 원소 x의 길이를 기준으로 정렬하도록 함
- 이를 통해 리스트의 각 요소들이 길이에 따라 정렬됨
lambda(람다)는 파이썬에서 간단한 익명 함수를 생성하는 키워드.
즉, 이름이 없는 함수를 생성할 때 사용됨.
람다 함수의 일반적인 구조는 `lambda 매개변수: 표현식`이다.
- lambda : 함수를 정의하는 키워드
- 매개변수 : 함수의 입력 값
- 표현식 : 함수의 결과 값
람다 함수 예시
addition = lambda x, y: x + y
print(addition(3, 5)) # 8
🚀 탐색(Search)
- 복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업
- 기본적으로 선형 탐색(Linear Search)와 이진 탐색(Binary Search)가 있음
선형 탐색
- 순차 탐색(Sequential Search)라고도 함
- 순차적으로 모든 요소 탐색하여 원하는 값 찾음
- 배열의 길이에 비례하는 시간 걸림 O(n)
# 선형 탐색 구현
def linear_search(L, x):
for i in range(len(L)):
if x == L[i]:
return i
return -1
이진 탐색
- 탐색하려는 배열이 정렬되어 있는 경우에만 적용 가능
- 배열 가운데 원소와 찾으려 하는 값을 비교하고, 가운데 원소가 더 작다면 왼쪽의 값들(절반)은 없애고, 다시 오른쪽 배열들에서 반복함
- 탐색할 때마다 절반씩 사라지므로 빠른 탐색 가능 O(log n)
# 이진 탐색 구현
def binary_search(L, x):
start, end = 0, len(n) - 1
while start <= end:
mid = (start + end) // 2
if L[mid] == x: return mid
start, end = (start, mid - 1) if L[mid] > x else (mid + 1, end)
return -1
# 예시
# 시작 상태: 전체 배열 [4, 8, 15, 16, 23, 42, 48, 50, 56, 71, 88]
# 찾고자 하는 값: 23
# 1. 중간 값: 42
# 중간 값이 더 크기에 오른쪽은 탐색 X
# [4, 8, 15, 16, 23]
# 2. 중간 값: 15
# 중간 값이 더 작기에 왼쪽은 탐색 X
# [16, 23]
# 3. 중간 값: 16
# 중간 값이 더 작기에 왼쪽 탐색 X
# [23]
# 4. 중간 값: 23
# 찾고자 하는 값과 중간 값이 일치하므로 찾음
🚀 재귀 알고리즘 (Recursive Algorithm)
- 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법
- 재귀함수는 하나의 함수에서 자신을 다시 호출하여 작업 수행하는 것
- 종결 조건(trivial case) 명시해야하고, 스택오버플로우가 나지 않도록 주의
예시
# 자연수의 합 구하기
def sum(n):
if n <= 1:
return n
else:
return n + sum(n - 1)# 피보나치 구하기
mem = {}
def fibo(n) :
if n in mem:
return mem[n]
if n <= 1:
return n
mem[n] = fibo(n-1) + fibo(n-2)
return mem[n]- mem 이라는 빈 딕셔너리(dictionary)를 만들어서 한번이라도 구했던 값 저장
- 딕셔너리는 키와 값으로 이루어진 데이터 구조
- mem[5] = 8 이 있으면 키가 5이고 값이 8
- 이 코드는 메모이제이션 기법을 구현한 방법으로, 메모이제이션은 이전에 계산한 값을 저장해 두고 필요할 때마다 사용하는 기법
- 중복 계산을 피하고 효율적인 알고리즘을 만들 수 있도록 도와줌
재귀를 통해 문제를 풀다보면 반복적으로 똑같은 함수를 여러번 실행하여 비효율적인 모습을 보일 때가 있다. 이럴 때 쓰이는 것이 메모이제이션 기법이다.
🚀 시간 복잡도
이것에 대해서는 아래 글에 작성했으니 참고하자.