[TIL 1일차] 데브코스 데이터엔지니어링

📚 오늘 공부한 내용

1. 자료 구조와 알고리즘

1) 자료 구조를 왜 알아야 하는가?

- 효과적으로 해결하고자 하는 문제가 무엇이냐에 따라 적합하게 사용되어야 하는 자료 구조가 다르고, 기본적으로 Python만이 제공하는 데이터 타입으로 해결할 수 없는 문제가 존재하기 때문이다.

- 만약 어떤 리스트의 최댓값을 구한다고 생각하자. 최댓값을 구하기 위해 모든 리스트의 원소를 확인할 수밖에 없다. 그렇게 되면 개수에 비례하는 만큼의 시간이 걸리지만 리스트가 아닌 다른 자료 구조를 사용한다면 더 효율적으로 풀 수 있다.

- 내가 이용하려고 하는 자료 구조가 어떤 성질을 가지는지 알아야 각 문제에 적합한 자료 구조를 사용할 수 있다.

2) 알고리즘이란?

- 주어진 문제의 해결을 위한 자료 구조와 연산 방법에 대한 선택 -> 이것을 알고리즘을 디자인한다고 표현

- 해결하고자 하는 문제에 따라 해법이 달라짐

2. 선형 배열

• 배열은 원소들을 순서대로 늘어놓은 것.
• Python에서는 따로 배열이 존재하지 않고, 리스트를 활용
• Python의 경우 아무런 타입의 데이터라도 배열에 줄을 세울 수 있음

1) 리스트 연산: O(1) - 상수시간

* 리스트의 길이와 무관하게 순식간에 할 수 있는 일

L = [20, 37, 58, 72 ,91]
# 1) 원소 삽입 
L.insert(3, 65)   #list.insert(index, value)  list의 index 위치에 value 삽입
# 2) 원소 삭제
del(L[2])         #del(value)  list에서 value 삭제
L.pop(2)          #list.pop(index)  list에서 해당 index의 값 삭제

** del과 pop의 차이: pop은 return 값이 존재하나 del은 return 값이 존재하지 않음

2) 리스트 연산: O(n) - 선형 시간

# 1) 원소 탐색하기
L.index(37)     
#list.index(value): list에 찾아야 하는 value의 index를 알려 줌. 

3. 정렬 (Sort)

1) 정렬 함수

a = [10, 50, 20, 19, 90]

b = sorted(a) #내장 함수 (built-in function), 정렬된 새로운 리스트를 얻어냄. 기존 리스트가 바뀌는 것이 아님.
a.sort() #리스트의 메소드(method), 해당 리스트를 정렬함으로 기존 리스트가 변함.

#정렬의 순서를 반대로 하려면 reverse = True 설정 (reverse 인자 추가)

2) 특정 키(key)를 이용한 정렬

# 문자열은 보통 사전 순으로 정렬되는데 길이 순으로 정렬을 하고 싶을 때 key를 길이로 지정하여 정렬한다.
s = sorted(L, key = lambda x: len(x))      #lambda를 통해 임의 key 지정

#보통 dictionary에서 특정 key 값의 value를 이용해 정렬하고 싶을 때도 이 방법을 사용함.
L = [{'name': 'John', 'score': 83}, {'name': 'Sam', 'score': 95}]
# score의 순서로 정렬
L.sort(key = lambda x: x['score'], reverse = True)  

4. 탐색 (Search)

1) 선형 탐색 (Linear Search)

1. 리스트의 원소를 순차적으로 탐색하는 것.

2. 리스트의 길이에 비례하는 시간이 소요됨. -> O(n)

3. 최악의 경우 모든 원소를 다 비교해 보아야 함.

2) 이진 탐색 (Binary Search)

1. 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능함.

2. 한 번 비교가 일어날 때마다 리스트를 반씩 줄임 (divide & conquer)

3. O(log n)

4. 이진 탐색 코드를 구현할 때는 lower와 upper 값을 무엇으로 설정할지 정해야 함.

# 실습 문제
# 리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때,
# x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 
# 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 
# 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 
# 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.
def binary_search(L, x):
    # L 안에 같은 값을 가지는 원소가 존재하지 않는 경우 그대로 -1을 return 해 주기 위해
    answer = -1       
    left = 0
    right = len(L) - 1
    while left <= right:
        mid = (left+right)//2   #mid 값 설정
        if L[mid] < x:
            left = mid + 1
        elif L[mid] == x:
            answer = mid
            break
        else: 
            right = mid - 1
    return answer

5. 재귀 알고리즘

1) 재귀 함수란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것. 생각보다 많은 종류의 문제가 재귀적으로 해결 가능함.

ex) 이진트리: 왼쪽 서브 트리의 원소들은 모두 작거나 같을 것, 오른쪽 서브 트리의 원소들은 모두 클 것 -> 재귀를 통해 트리 탐색함.

ex) 자연수의 합 구하기: 1부터 n까지의 모든 자연수의 합을 구하시오.

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

2) 재귀 알고리즘의 효율

재귀 알고리즘(Recursive version)은 n이 커지면 O(n), 반복 알고리즘(Iterative version)은 n이 커지면 O(n)

=> 재귀 알고리즘은 효율성이 떨어질 수 있으므로 사용할 때 항상 주의해야 함

3) 재귀 알고리즘으로 이진 탐색 구현 (실습)

def binary_search(L, x, left, right):
	if left > right:  #탐색 후 값이 없으면 더 이상 재귀 호출을 막음
    	return -1 
    mid = (left + right)//2
    if x == L[mid]:
    	return mid
    elif x < L[mid]:
    	return binary_search(L, x, left, mid-1) # x가 중앙값보다 작은 경우 right값을 수정하여 재귀 호출
	else: 
    	return binary_search(L, x, mid+1, right) # x가 중앙값보다 큰 경우 left 값을 수정하여 재귀 호출

6. 알고리즘의 복잡도

1) 복잡도란?

문제를 푸는 데 있어서 얼마큼의 자원을 요구하는가? 시간적, 공간적 자원을 얼마나 소요하는가?

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

공간 복잡도 (Space Complexity): 문제를 풀기 위해서 필요한 메모리 공간 사이의 관계

* 시간 복잡도는 데이터 입력이 랜덤한 패턴을 가진다고 했을 때 소요되는 시간의 평균을 말하는 평균 시간 복잡도와 가장 긴 시간을 소요하게 만드는 입력에 소요되는 시간인 최악 시간 복잡도가 있음.

2) Big-O Notation

• 점근 표기법의 하나 (asymptotic notation)
• O(logn), O(n), O(n^2)
• 입력의 크기가 커짐에 따라 얼마나 실행 시간이 증가하는가의 관계를 나타냄
• 계수는 그다지 중요하지 않음.

예시

선형 시간 알고리즘 O(n): 선형 탐색, 로그 시간 알고리즘 O(logn): 이진 탐색, 이차 시간 알고리즘 O(n^2): 삽입 정렬

✔ 특강 (코딩 테스트 & 코딩 인터뷰)

1. 코딩 테스트를 왜 하는가?

• 최소한의 문제 해결 능력을 검증
• 문제 분석과 해결 방법을 착안 (problem solving)
• 그리고 이것을 코드로 어떻게 구현하는가 (code implementation)

2. 코딩 문제의 종류

- Implementation : 제시된 흐름에 따라 실행하는 코드를 만들도록 요구 (알고리즘이 문제에 다 주어져 있고 그 알고리즘을 코드로 구현할 수 있는가.) -> 난이도가 낮은 문제

- Algorithm comprehension : 문제의 효과적/효율적 해법을 찾아내도록 요구 (효과적: 정확성, 효율적: 비용-> 시간이나 메모리 사용) 효과는 결과의 품질이 더 중요할 때 효율은 시간적인 비용적인 측면이 더 중요할 때

- Competency Test: 문제만 봤을 때는 어렵지만 특정한 자료 구조랑 알고리즘을 착안해서 하면 문제의 답을 낼 수 있는 것. 제출자가 명확한 의도를 가지고 내는 문제. -> 대회에서 주로 나오는 문제

기타: 특정한 언어 구문을 활용할 수 있는지. -> SQL 같은 언어

3. 코딩 테스트 대비 순서

1. 하나의 프로그래밍 언어를 구사할 수 있는 구현 능력을 갖춘다.

2. 기본적인 자료 구조를 이해한다.

3. 기초 알고리즘 및 시간/공간 복잡도를 이해한다.

4. 알고리즘 적용 해법 착안 사고 훈련, 제한 시간 내에 오류 없이 코드를 작성할 수 있는 훈련을 한다.

-> 꾸준한 연습이 필요함.

4. 문제 해결 과정

1) 문제 발생

2) 추상화: 문제의 본질을 이해하고 이를 정보 처리로 접근할 수 있는 핵심을 추려내는 것.

3) 해법 착안: 코드에 의해 해법을 구현하기 위한 자료 구조와 알고리즘의 어휘력이 필요함. 추상화와 해법 착안의 과정을 합쳐 Problem Solving의 과정이라고 봄.

4) 코드 구현: 추상화와 해법 착안을 통해 그린 방법을 코드로 쓰는 것. 이를 implementation이라고 함.

5. 빠지기 쉬운 함정

코드를 짧게 쓴다고 빨리 실행되는 것이 아님. 특히나 Python의 경우 짧게 표현되는 경우가 많음.

🔎 어려웠던 내용 & 새로 알게 된 내용

1. list.index(value)

- value가 여러 개일 경우 처음으로 나오는 value의 index만 return 됨.

- 만약 list에 value가 존재하지 않는다면 -> ValueError 발생

#ValueError 오류 처리 방법 
# 1.Try-Except문을 사용
a = [1, 2, 3, 4, 5]
try: 
	print(a.index(10))
except ValueError:
	print("10 is not in list")
# 2. if-else문을 이용
find_index = a.index(10) if 10 in a else - 1

2. append와 list 연산의 차이

L1 = [38, 45, 12, 20]
L1.append(y)  
L2 = L1 + [y] 

＊ append와 연산의 결과 값은 동일하지만 append의 경우 L1의 List에 y 원소를 하나만 추가하는 것임으로 O(1)이라는 상수 시간이 들지만 리스트 연산은 L2라는 새로운 리스트를 만들어 연산하므로 O(n)이 됨.

✍ 회고

어떠한 문제를 해결함에 있어 알고리즘과 자료 구조를 공부하는 것이 어떻게 도움이 되는지를 느낄 수 있었다. 알고리즘과 자료 구조는 문제를 해결하기 위한 도구라는 말이 와닿는다. 마냥 외우려고 하지 않고 문제를 보고 내가 이것을 어떻게 적용해야 할지 알 수 있을 정도로 개념과 성질을 공부해야 되겠다고 생각했다.