[TIL_2023.10.16] 자료구조와 알고리즘 (1) : 선형배열, 정렬/탐색, 재귀 알고리즘, 복잡도

1주차 월요일, 1일차 Today I Learned

 

 

자료구조와 알고리즘 (1)
: 선형배열, 정렬/탐색, 재귀 알고리즘, 복잡도

 

반응형

 

✏️ 학습 내용

1. 선형 배열

선형 배열 Linear Arrays : 데이터들이 선처럼 일렬로 늘어선 형태이다.

 

선형 시간 (리스트 길이에 비례하여 걸리는 시간) : O(n)

 

참고로 리스트랑 배열은 엄연히 다른데, 리스트는 요소들이 각각 다른 데이터 타입을 가져도 되지만 배열은 모든 요소의 데이터 타입이 같아야 한다.

 

리스트의 길이에 따라서 실행 시간이 달라지는 연산과 길이에 관계 없이 일정하게 빠른 속도로 실행되는 연산이 있다.

 

- 길이에 상관 없이 빠른 실행을 하는 연산 : append(), pop()

- 길이에 따라 실행 시간이 다른 연산 : insert(), del()

 

이렇게 구분할 수 있다.

 

L = [10, 20, 40]

# 빠르게!
L.append(50)   # 마지막에 요소(50)를 추가한다.
L.pop()        # 맨 끝 요소를 삭제한다.

# 시간 고려..
L.insert(2, 30)   # 2번 인덱스에 요소(30)를 추가한다.
del(10)           # 요소 10을 삭제한다.

# 그 외
L.index(20)   # 요소 20의 인덱스를 출력한다.

 

 

 

2. 정렬과 탐색

정렬 Sort : 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업이다.

 

정렬의 대표적인 2가지 방법은 아래와 같다.

파이썬 내장 함수 sorted()

리스트 메서드 .sort()

 

내장 함수 sorted()는 정렬된 새로운 리스트를 만들어낸다.

반면 메서드 sort()는 리스트 자체를 정렬시킨다.

 

정렬 순서는 오름차순(기본, reverse=False), 내림차순(reverse=True)으로 조정 가능하다.

 

숫자가 아닌 문자열로 이루어진 리스트의 경우, 사전 순서(알파벳 순서)에 따른다.

 

---

 

그리고 key에 lambda 함수를 이용하여 정렬을 원하는 대로 조정할 수도 있다.

 

# 문자열 길이에 따라 지정하기
L = ['abcd', 'efg', 'a']
sorted(L, key=lambda x: len(x))
>>> ['a', 'efg', 'abcd']

# 딕셔너리에서 이용하기
L = [{'name': 'jain', 'score': 80}, {'name': 'alex', 'score': 70}]
L.sort(key=lambda x: x['score'], reverse=True)
>>> 점수 높은 순으로 정렬

 

 

 

 

탐색 Search : 복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업이다.

 

탐색의 종류는 다양하지만 가장 기본적인 2가지는 아래와 같다.

선형 탐색 (linear search) = 순차 탐색 (sequential search)

이진 탐색 (binary search)

 

선형 탐색은 순차 탐색이라고도 하며, 순차적으로 모든 원소를 탐색하여 원하는 값을 찾아내는 방법이다. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우엔 배열에 있는 모든 원소를 전부 검사해야 할 수 있다.

 

반면 이진 탐색은 탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용할 수 있다. 배열의 가운데 원소와 찾으려 하는 값을 비교하면, 왼쪽이나 오른쪽 어디에 있을 지를 알 수 있다. 쉽게 말하면, 크기 순으로 정렬되어 있는 정렬을 반씩 제외하며 탐색하는 방법이다.

 

 

 

 

3. 재귀 알고리즘

재귀 알고리즘 Recursive Algorithms : 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘

 

 

 

 

 

4. 알고리즘의 복잡도

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

• 평균 시간 복잡도 Average Time Complexity : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
• 최악 시간 복잡도 Worst-case Time Complexity : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

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

 

점근 표기법 Asymptotic notation
- Big-O notation : 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현

 

 

 

---

 

☁️ 소감

아직 초반이라서 그런지 난이도가 쉽고, 강의 시간이 짧다. 그래서 일단 오늘은 대부분의 내용을 정리했는데 추후에 모르는 내용이 나왔을 때, 분량이 많을 때를 대비하여 어떻게 정리하여 작성하면 좋을 지를 고민해봐야 할 것 같다. 게다가 저작권 문제도 있어서 자세하게 코드를 적지는 못할 것 같다.

 

자료구조와 알고리즘은 공부한 적이 없는데 이전부터 공부해야겠다고 생각한 분야였다. 수업 진도에 잘 따라가려면 이 내용들을 더 자세하게 공부해놔야 될 것 같다.