선형배열, 정렬, 탐색, 재귀, 시간복잡도

데이터 엔지니어링 데브코스 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
• 이 코드는 메모이제이션 기법을 구현한 방법으로, 메모이제이션은 이전에 계산한 값을 저장해 두고 필요할 때마다 사용하는 기법
  • 중복 계산을 피하고 효율적인 알고리즘을 만들 수 있도록 도와줌

재귀를 통해 문제를 풀다보면 반복적으로 똑같은 함수를 여러번 실행하여 비효율적인 모습을 보일 때가 있다. 이럴 때 쓰이는 것이 메모이제이션 기법이다.

 

🚀 시간 복잡도

이것에 대해서는 아래 글에 작성했으니 참고하자.

https://ssdragon.tistory.com/100