이코테 강의 정리 - 복잡도와 파이썬 문법

이예슬·2022년 4월 10일
이코테코테파이썬
0

코테

목록 보기
1/6

복잡도 (Complexity)

  • 복잡도는 알고리즘의 성능을 나타내는 척도이다.
    • 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
    • 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

→ 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

  • Big-O notation

    • 가장 빠르게 증가하는 항만을 고려하는 표기법
      • 함수의 상한만을 나타냄
    • 연산횟수가 3N^3 + 5N^2 + 1000 인 알고리즘이 있으면 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3) 으로 표현됨

  • 요구사항에 따라 적절한 알고리즘 설계하기

  • 시간제한이 1초인 문제를 만났을 때 일반적인 기준은 다음과 같다

    • N의 범위가 500인 경우 : 시간 복잡도가 O(N^3) 인 알고리즘을 설계하면 문제를 풀 수 있음
    • N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2) 인 알고리즘을 설계하면 문제를 풀 수 있음
    • N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN) 인 알고리즘을 설계하면 문제를 풀 수 있음
    • N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N) 인 알고리즘을 설계하면 문제를 풀 수 있음

  • 일반적인 알고리즘 문제 해결 과정

    1. 지문 읽기 및 컴퓨터적 사고

    2. 요구사항(복잡도) 분석

    3. 문제 해결을 위한 아이디어 찾기

    4. 소스코드 설계 및 코딩 

      import time 
start_titme = time.time() # 측정 종료 

# 프로그램 소스코드 

end_time = time.time() # 측정 종료
print('time:', end_time - start_time) # 수행시간 출력

파이썬 문법

  • 리스트 컴프리헨션

    • 리스트를 초기화하는 방법 중 하나

    • 대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화할 수 있다.

      array = [i forn i in range(10)]
print(array) 
# {0,1,2,3,4,5,6,7,8,9]

array = [ in for i in range(20) if i % 2 == 1] 
array = [i * i for i in range(20)]

    • 리스트 컴프리헨션을 2차원 리스트를 초기화할 때 효과적으로 사용됨

    • 특히 N * M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 유용

      ex. array = [[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)

  • 튜플을 사용하면 좋은 경우

    • 서로 다른 성질의 데이터를 묶어서 관리해야 할 때
      • 최단 경로 알고리즘에서는 (비용, 노드 번호) 의 형태로 튜플 자료형을 자주 사용
    • 데이터의 나영을 해싱(Hashing)의 키 값으로 사용해야 할 때
      • 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있음
    • 리스트보다 메모리를 효율적으로 사용해야 할 때

  • 자주 사용되는 표준 입력 방법

    • input() 함수는 한 줄의 문자열을 입력 받는 함수

    • map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용

      ex. 공백을 기준으로 구분된 데이터를 입력 받을 때는 다음과 같이 사용

      list(map(int, input().split()))

      ex. 공백을 기준으로 구분된 데이터의 개수가 많지 않다면 다음과 같이 사용

      a, b, c = map(int, input().split())

    • 빠르게 입력 받기

      • 사용자로부터 입력을 최대한 빠르게 받아야 하는 경우 sys 라이브러리에 정의되어 있는 sys.stdin.readline() 메서드를 이용 → 단 입력 후 엔터가 줄 바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용

    • 파이썬에서 기본 출력은 print() 함수를 이용

      • 각 변수를 콤마(,)를 이용하여 띄어쓰기로 구분하여 출력할 수 있음

    • print()는 기본적으로 출력 이후에 줄 바꿈을 수행

      줄 바꿈을 원치 않는 경우 ‘end’ 속성을 이용 가능

    • f-string : 중괄호 안에 변수명을 기입하여 간단히 문자열과 정수를 함께 넣을 수 있음

      n = int(input())

data = list(map(int, input().split()))

data.sort(reverse=True)
print(data)

#빠르게 입력받기 
import sys 

data = sys.stdin.readline().rstrip()
print(data)

a = 1 
b = 2 
print(a, b)
print(7, end=' ')
print(8, end=' ')

answer = 7 
print('answer is ' + str(answer) )

#f-string
print(f'answer is {answer}')
  • 파이썬의 기타 연산자
    • 다수의 데이터를 담는 자료형을 위해 in 연산자와 not in 연산자가 제공

      • 리스트 튜플, 문자열, 딕셔너리 모두에서 사용 가능

        in 연산자와 not in 연산자설명
        x in 리스트리스트 안에 x가 들어가 있을 때 True
        x not in 문자열문자열 안에 x가 들어가 있지 않을 때 True
    • 아무것도 처리하고 싶지 않을 때 pass 키워드 사용
      • 디버깅 과정에서 일단 조건문의 형태만 만들어 놓고 조건문을 처리하는 부분은 비워놓고 싶은 경우
  • 조건문의 간소화

    • 조건문에서 실행될 소스코드가 한 줄인 경우 굳이 줄 바꿈을 하지 않고도 간략하게 표현할 수 있다.

      score = 85 

if score >= 80: result = 'Success' 
else: result = 'Fail'

    • 조건부 표현식(conditional expression) : if ~ else 문을 한 줄에 작성

      score = 85 
# 만약 score가 80점 이상이면 성공 아니면 실패 
result = 'Success' if score >= 80 else 'Fail' 

print(result)
  • 파이썬에서 유용한 표준 라이브러리
    • 내장 함수
    • itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공 → 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용
    • heapq: 힙 자료구조를 제공 → 일반적으로 우선순위 큐 기능을 구현하기 위해 사용
    • bisect : 이진탐색(Binary Search)기능을 제공
    • collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함
    • math : 필수적인 수학적 기능을 제공 → 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이와 같은 상수를 포함
    • 순열과 조합

      • 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열

        nPr = n (n-1) (n-2) ... (n-r+1)

      • 조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택

        nCr = n * (n-1) * (n-2) * ... * (n-r+1) / r!
        from itertools import permutations 

data = ['A', 'B', 'C']

#모든 순열 구하기 
result1 = list(permutations(data, 3))
# 2개를 뽑는 모든 조합 구하기  
result2 = list(combinations(data, 2))

from itertools import product
data = ['A', 'B', 'C']

#2개를 뽑는 모든 순열 구하기 (중복 허용)
result = list(product(data, repeat=2))
print(result)

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

#2개를 뽑는 모든 조합 구하기(중복 허용)
result = list(combinations_with_replacement(data, 2))
print(result)
    • counter
      • 파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능 제공
      • 리스트와 같은 iterable 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지 알려줌
profile
이예슬
꾸준히 열심히!
다음 포스트

이코테 강의 정리 - 그리디 & 구현

0개의 댓글