데이터 엔지니어링 1일차 TIL

오늘 학습 내용

자료구조(Data Structures)

리스트
리스트에서 최대값을 구하려면 모든 원소를 뒤져보지 않고서는 찾을 수 없다.
단위가 큰 리스트에서 최대값을 찾는 max함수를 이용하면 갯수에 비례하는 만큼의 시간이 걸린다.

풀어야 하는 문제에 따라 내가 이용하는 자료구조가 어떤 성질을 가지느냐를 이해해야 한다.

알고리즘(algorithm)이란?

[사전적 정의]어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
[프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

 

해결하고자 하는 문제에 따라 최적의 해법이 다르기 때문에 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 한다.

 

배열(Arrays)
같은 종류의 데이터가 줄지어 늘어서 있는 것
-원소들을 순서대로 늘어 놓은 것

 

리스트(Lists)
배열보다 좀 더 융통성 있는 자료
-서로 다른 타입의 데이터라도 리스트의 원소로 채택이 가능하다.

리스트(배열)의 연산

1. 리스트의 끝에 대한 연산
append함수 ex) L.append('a')
- 끝에 a라는 원소를 덧붙임

pop함수 ex) L.pop()
- 끝에서 원소 하나를 제거함

리스트의 길이와 무관(상수 시간)하게 할 수 있다.
O(1)의 시간이 걸린다.

 

2.배열의 중간에 대한 연산

insert함수 ex) L.insert(3,65)
insert(인덱스,값)
해당 인덱스 바로 뒤에 값을 삽입
L=[20,37,58,72,91]

 

del함수 ex)del(L[2])
해당리스트의 인덱스의 값을 삭제
L=[20,37,58,65,72,91]
=> L=[20,37,65,72,91]

 

del과 pop의 차이 :
pop은 지워진 인덱스의 값을 반환하지만 del은 반환하지 않는다.
이 차이 때문에 del이 pop보다 수행속도가 더 빠르다.
또한 del은 범위지정 삭제가 가능하다.

배열의 중간에서의 연산시간은 리스트의 길이에 비례(선형 시간)한다.
O(n)의 시간이 걸린다.

 

3.원소 탐색
L = ['Bob','Cat','Spam','Programmers']
index함수 ex) L.index('Spam')
=>2
해당하는 인덱스 값을 반환한다.

정렬과 탐색

sorted() 함수 - 새로운 정렬된 리스트를 만듦
sort() 함수 - 해당 리스트를 정렬함
기본적으로 오름차순 정렬
내림차순 시, reverse = True 을 추가
문자의 경우 알파벳 순서를 따른다. 소문자보다 대문자를 우선한다.

 

문자열 길이 순서로 정렬이 하고 싶다면 ?
정렬에 이용하는 키(key)를 지정한다. (lambda사용)

L = ['abcd', 'xyz', 'spam']
sorted(L, key = lambda x: len(x))
=>['xyz', 'spam', 'abcd']

 

키를 지정하는 또 다른 예(사전)
L = [{'name':'John', 'score':83},
{'name':'Paul', 'score':92}]

 

이름 순서대로 정렬
L.sort(key = lambda x:x['name'])
[{'name': 'John', 'score': 83}, {'name': 'Paul', 'score': 92}]

 

높은 점수순으로 정렬
L.sort(key = lambda x:x['score'], reverse = True)
[{'name': 'Paul', 'score': 92}, {'name': 'John', 'score': 83}]

탐색 알고리즘

1. 선형 탐색 - 순서대로 탐색
리스트의 길이에 비례하는 시간 소요 O(n)
최악의 경우 : 모든 원소를 다 비교하게 된다.

 

2. 이진 탐색
크기순으로 정렬되어 있다는 성질 이용하기 때문에 리스트가 반드시 이미 정렬이 되어 있어야만 한다.
반으로 잘라 찾는 값보다 작은 부분 또는 큰 부분 버리는 방법을 반복한다.

lower = 0
upper = len(L)-1
idx = -1

while lower<=upper :
iddle = (lower+upper) // 2
if L[middle] == target :
return middle
elif L[middle] < target :
lower = middle+1
else : upper = middle-1

 

한 번 비교가 일어날 때마다 리스트의 반씩 줄인다.
O(log n)의 시간 소요

 

재귀 알고리즘(Recursive Algorithm)

재귀 함수 : 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것.
ex) 이진트리, 자연수의 합 구하기

def sum(n) :
if n<=1 :
return n
else :
return n+sum(n-1)

 

재귀호출은 무한으로 재귀되기 때문에 종결조건이 반드시 필요하다 !
재귀함수 사용시 시간효율성도 고려해야한다 !
ex)피보나치 수열,하노이의 탑

알고리즘의 복잡도

시간 복잡도(Time Complexity) : 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계

 

공간 복잡도(Space Complexity) : 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

 

평균 시간 복잡도 : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

 

최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

 

Big-O Notation : 점근 표기법의 하나이다.
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현한다. 계수는 크게 중요하지 않다.

ex) O(log n), O(n) 등

 

선형 시간 알고리즘 - O(n)
ex) n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용

(처음부터 끝까지 모든 원소를 살펴봄)

 

로그 시간 알고리즘 - O(log n)
ex) n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용

 

이차 시간 알고리즘 - O(n^2)
ex) 삽입 정렬 Best-O(n), Worst-O(n^2)

 

더 낮은 복잡도를 가지는 정렬 알고리즘
ex) 병렬 알고리즘 - O(nlog n)
정렬 문제에서 O(nlog n)보다 낮은 복잡도를 갖는 알고리즘은 존재 할 수 없음이 수학적으로 증명이 됨.

느낀 점

첫 날이라 떨리고 많이 설레었다.
기본기에 대해서 복습하면서 더 탄탄한 기초를 다졌다.
재귀함수의 응용과 활용 및 장,단점을 배울 수 있었다.
코딩 테스트를 볼 때 단순히 문제통과를 위한 조건으로 시간복잡도를 고민했지만, 이번 강의를 통해 시간효율성의 중요성을 한 번더 깨달았고, 정렬 문제에서 시간 효율성을 더 향상 시킬 방법들을 알 수 있는 유익한 시간이었다.