Skip to content

Latest commit

 

History

History
131 lines (71 loc) · 5.47 KB

220726_Algorithm.md

File metadata and controls

131 lines (71 loc) · 5.47 KB

💻좋은 알고리즘이란 뭘까?

알고리즘의 목적은 원하는 output을 뽑아내기 위한 일련의 절차이다.

그렇기 때문에 좋은 시간과 공간이 한정되어 있는 상황에서 더 빠르고, 더 효율적으로 output을 도출해 내는 것이 궁극적인 목표이다. 즉, 좋은 알고리즘이란 짧은 시간으로 output을 뽑아내는 알고리즘이라고 할 수 있다.

하지만 이러한 알고리즘의 효율성을 어떻게 정량적으로 평가할까? 알고리즘의 소요 시간은 개인 컴퓨터 환경에 따라 영향을 받아서 객관적이지 않다... 그렇다면 어떻게 효율적으로 알고리즘의 성능을 측정하고 개선할 수 있을까?

🌟그래서 등장한 것이 시간복잡도(Time Complexity). 빅오(O(n))이다.

알고리즘에서의 시간은 진짜 시간이 아니라, 연산의 횟수이다. 왜냐? 앞서 말했듯이 알고리즘의 소요 시간은 개인 컴퓨터 환경에 따라 영향을 받아서 객관적이지 않기 때문이다!

기본연산의 총 횟수 == 알고리즘의 소요 시간

  • 시간 복잡도(Time Complex): 단순하게 알고리즘의 수행 시간을 의미한다.

    시간 복잡도가 높다 == 느린 알고리즘

    시간 복잡도가 낮다 == 빠른 알고리즘

💻빅오 표기법(Big - O):

입력 n이 무한대로 커진다고 가정하고 시간 복잡도를 간단하게 표시하는 것이다.

최고차항만 남기고 계수와 상수를 제거한다.

매 입력에 따라 정확한 수식을 구하는 것은 불필요하기 때문에, 최고차항만 비교한다.

시간복잡도를 오름차순으로 정렬하였다.

  • O(1): 단순 산술 계산(덧셈, 뺄셈, 나눗셈, 곱셈)

  • O(logN): 크기가 N인 리스트를 반절씩 순회/탐색 (이진 탐색, 분할 정복)

  • O(N): 크기가 N인 리스트를 순회 (1중 for문)

  • O(NlogN): 크기가 N인 리스트를 반절씩 탐색 * 순회 (높은 성능의 정렬: Merge, Quick, Heap Sort)

  • O(N^2): 크기 M, N인 2중 리스트를 순회 (2중 for문)

  • O(N^3): 3중 리스트를 순회 (3중 for문)

  • O(2^N): 크기 N 집합의 부분 집합

  • O(N!): 크기 N 리스트의 순열

파이썬 시간복잡도 공식 문서

Big-O Cheat Sheet를 활용해서 각 함수별 시간복잡도를 살펴보자.

💻리스트 (C를 기준으로)

사실 언어마다 자료 구조는 조금씩 다르나 많은 언어가 C에 기반하여 만들어졌기에 자료구조 또한 C에 기반하여 작성 및 공부하였다.

💻배열 vs 연결리스트

배열(Array): 여러 데이터들이 연속된 메모리 공간에 저장되어 있는 자료구조이다.

특징은:

  1. 인덱스를 통해서 빠르게 접근이 가능하다.

  2. 배열의 길이는 변경이 불가능하다. 길이를 변경하고 싶다면 새로 생성해야한다.

  3. 데이터 타입은 고정이다. 파이썬에서는 리스트가 배열과 매우 유사한데 완전 같지는 않다. 파이썬에서의 리스트는 사실 배열과 연결리스트의 개념을 모두 지닌다. 다른 언어에는 이런 리스트와 같은 기능이 없는 언어도 있다(파이썬 굿!).

연결 리스트(Linked List): 여러 데이터들이 연속된 메모리 공간에 저장되어 있는 자료구조이다.

그렇다면 배열과 뭐가 다른가?

연결리스트는 배열과는 다르게:

  1. 연결리스트의 길이를 자유롭게 변경할 수 있다. 삽입, 삭제가 편리하다 (배열은 길이 고정이다. 길이를 변경하고 싶다면 다시 생성해야 하는 번거로움이 있다)

  2. 다양한 데이터 타입을 저장할 수 있으며 데이터가 메모리에 연속적으로 저장되지 않는다 (배열의 데이터 타입은 고정이다)

💻파이썬 리스트 메서드들의 시간복잡도(Time Complexity)

  • .append() : O(1) (끝만 찾아서 입력하는 것이기 때문에)

특징: return 값이 없다. print(a.append()) 하면 출력되는 것이 없다.

  • .pop() : O(1) (끝만 찾아서 삭제하는 것이기 때문에)

특징: return 값이 있다. print(a.pop()) 하면 출력

  • .count() : O(N)

  • .index() : O(N)

  • .sort() : O(NlogN) (굉장히 시간을 많이 소요하는 메서드이다.)

  • .reverse() : O(N)

💻리스트 관련 내장함수

복습 느낌으로 다시 공부해보자.

len(iterable): 리스트의 원소 길이(갯수)를 반환

sum(iterable): 리스트의 모든 원소 합을 반환

max(iterable): 리스트의 최댓값을 반환

min(iterable): 리스트의 최솟값 반환

sorted(iterable): 오름차순으로 정렬된 새로운 리스트를 반환. 이 때 새로운 변수로 정의를 해주어야 한다.

reversed(iterable): 리스트를 거꾸로 뒤집은 새로운 객체 반환. 원본 리스트는 변화가 없다.

💻리스트 컴프리헨션(List Comprehension)

자주 헷갈리는 개념이니 확실하게 이해해두고 넘어가자.

List Comprehension이란: 리스트 내포라고도 불리며 코드 한 줄만으로 새로운 리스트를 만드는 방법이다.

# 일반적인 리스트 생성
numbers = []
for i in range(5):
    numbers.append(i)
print(numbers) # [0,1,2,3,4]

# 리스트 컴프리헨션 이용하여 리스트 생성
numbers = [i for i in range(5)]
print(numbers) # [0,1,2,3,4]

# if 문을 활용하여 필터링 또한 가능하다.
numbers = [i for i in range(5) if i % 2 == 0]
print(numbers) # [0,2,4]