[이코테 2021 강의] 코딩테스트 및 파이썬 문법 부수기

강의를 참고하여 글을 작성했습니다 ! 

 

1. 알고리즘 성능 평가

💡복잡도(Complexity)

• 복잡도는 알고리즘의 성능을 나타내는 척도
• 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘 !
  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 

💡빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 시간 복잡도에서 최악의 경우를 계산하는 방식 

 

시간 복잡도 그래프 

시간 복잡도 그래프

• N은 입력되는 데이터를 의미
• O(1) 상수 시간(Constant)
  • 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.
  • 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않음
• O(logn) 로그 시간(Logarithmic)
  • 입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘.
  • 예를 들어 데이터가 10배가 되면 처리 시간은 2배가 됨.
  • 대표적으로 이진탐색이 있고, 재귀가 순기능으로 이루어지는 경우도 해당
• O(n) 선형 시간(Linear)
  • 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘.
  • 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됨.
  • 1차원 for문
• O(nlogn) 로그 선형 시간(Linear-Logarithmic)
  • 데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘.
  • 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 됨.
  • 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적.
• O(n²) 이차 시간(quadratic)
  
  • 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘.
  • 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다.
  • 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직.
• O(2ⁿ) 지수 시간(Exponential)
  
  • 데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘.
  • 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당.

빅오 표기법 예제

1. O(1) : 스택의 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2ⁿ) : 피보나치 수열

💡알고리즘 설계 Tip

• 코딩 테스트 문제에서 시간 제한은 통상 1 ~ 5초가량이라는 점에 유의(문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적)
• 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)입니다.
• 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다.
  • N의 범위가 500인 경우: 시간 복잡도가 O(N3)인 알고리즘을 설계하면 문제를 풀 수 있습니다.
  • N의 범위가 2,000인 경우: 시간 복잡도가 O(N2)인 알고리즘을 설계하면 문제를 풀 수 있습니다.
  • N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있습니다.
  • N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있습니다.
• 수행 시간 측정 소스코드 예제 

import time
start_time = time.time() # 측정 시작

# 프로그램 소스 코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

 

2. 리스트 자료형

💡리스트 컴프리헨션 

• 리스트를 초기화하는 방법 중 하나로, 대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화함
• 2차원 리스트를 초기화할 때 효과적으로 사용

n = 4
m = 3

arr = [[0] * m for _ in range(n)]

 

• 파이썬에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바를 자주 사용

 

💡리스트 관련 기타 메서드 

 

💡리스트에서 특정 값을 가지는 원소를 모두 제거하기

# 리스트에서 특정 값을 가지는 원소를 모두 제거하기
a = [1, 2, 3, 4, 5, 5, 5]
remove_set = {3, 5} #집합 자료형 

# remove_list에 포함되지 않은 값만을 저장
result = [i for i in a if i not in remove_set]
print(result)

 

3. 기본입출력 

💡빠르게 입력받기 

import sys

# 문자열 입력 받기
data = sys.stdin.readline().rstrip()
print(data)

• 사용자로부터 입력을 최대한 빠르게 입력받아야 하는 경우
• 입력의 개수가 매우 많은 경우, 입력에서 시간 초과를 방지하기 위해 사용하는 방법
• 이진탐색, 정렬, 그래프 관련 문제에서 자주 사용됨 

3. 조건문

💡기타 연산자

x in list_name # 리스트 안에 x가 들어있을 때 True
x not in list_name # 리스트 안에 x가 들어있지 않을 때 True

 

💡조건문의 간소화 

score = 85
result = "Pass" if score >= 80 else "Fail"

print(result)

• if ~ else 문을 한 줄에 작성 

4. 자주 사용되는 표준 라이브러리 

💡실전에서 유용한 표준 라이브러리

• 내장 함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공
  • 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함
• itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공
  • 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용됨
• heapq: 힙(Heap) 자료구조를 제공
  • 일반적으로 우선순위 큐 기능을 구현하기 위해 사용
• bisect: 이진 탐색(Binary Search) 기능을 제공 
• collections: 덱(deque), 카운터(Conter) 등의 유용한 자료구조를 포함
• math: 필수적인 수학적 기능을 제공
  • 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파(pi)와 같은 상수를 포함

 

💡자주 사용되는 내장 함수

# sorted()
result = sorted ([19, 1, 8, 5, 41]) # 오름차순 정렬
reverse_result = sorted([9, 1, 8, 5, 4], reverse=True) # 내림차순 정렬
print (result) # [1, 5, 8, 19, 41]
print (reverse_result) # [9, 8, 5, 4, 1]

# sorted() with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted (array, key=lambda x: x[1], reverse=True)
print (result) # [('이순신', 75), ('아무개', 50), ('홍길동', 35)]

 

💡Counter

• 내부의 원소가 몇 번 등장했는지 횟수를 세는 기능을 제공

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])

print(counter['blue']) #'blue'가 등장한 횟수 출력 # 3
print(counter['green']) # 'green'이 등장한 횟수 출력 # 1 
print(dict(counter)) # 사전 자료형으로 반환 # {'red': 2, 'blue': 3, 'green': 1}

 

💡최대 공약수와 최소 공배수

• 내부의 원소가 몇 번 등장했는지 횟수를 세는 기능을 제공

import math

# 최소 공배수(LCM)를 구하는 함수
def lcm(a, b):
  return a * b // math.gcd(a, b)

a = 21
b = 14

print(math.gcd(21, 14)) # 최대 공약수(GCD) 계산 # 7
print(lcm(21, 14)) # 최소 공배수(LCM) 계산 # 42

 

 

참고 사이트:

https://velog.io/@cha-suyeon/Algorithm-시간-복잡도-공간-복잡도

[Algorithm] 시간 복잡도, 공간 복잡도