알고리즘 - 들어가기 앞서

Hyeseong·2021년 3월 27일
기본 라이브러리빅오표기법이코테자료형
1

알고리즘

목록 보기
1/9
post-thumbnail

들어가기 앞서

온라인 알고리즘 저지 사이트

해외

  1. 코드포스 - codeforces.com
  2. 탑 코더 - topcoder.com
  3. 릿 코드 - leetcode.com
  4. 코드셰프 - codechef.com

국내

  1. 백준 - acmicpc.net
  2. 코드업 - codeup.kr | 첫 알고리즘 입문자에게 적절함
  3. 프로그래머스 - programmers.co.kr
  4. SW Expert Academy - swexpertacademy.com

알아 둬야할 알고리즘 유형

  • 구현
  • BFS/DFS
  • 그리디
  • 정렬
  • 이진탐색
  • 최단 경로
  • 다이나믹 프로그래밍
  • 그래프 이론

복잡도(Complexity)

복답도는 알고리즘의 성능을 나타내는 기준

  • 시간 복잡도 : 알고리즘의 수행시간 분석
  • 공간 복잡도 : 알고리즘의 메모리 사용량 분석

동일한 기능을 수행하는 알고리즘이 있다면, 일반적인 경우 복잡도가 낮을수록 좋은 알고리즘

빅오 표기법(Big-O Notation)

가장 빠르게 증가하는 항만을 고려하는 표기법

  • 함수의 상한만을 나타냄

예. 3N3+5N2+1,000,0003N^3 + 5N^2 + 1,000,000인 알고리즘이 존재

  • 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N3)O(N^3)로 표기

빅오 표기법(Big-O Notation) 성능 비교

왼쪽에서 오른쪽으로 갈수록 더 성능이 떨어져요.

(상수함수<로그함수<선형함수<다항함수<지수함수)

빅오 표기법 예시

빅오 표기법에서 실제 사용되는 로직들이 어떤게 있는지 간단한 예시만 볼게요.

  • O(1) : 스택에서 Push, Pop
  • O(log n) : 이진트리
  • O(n) : for 문
  • O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
  • O(N2N^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
  • O(2N22N^2) : 피보나치 수열

시간 복잡도 계산해보기

[예제1]

  • N개의 데이터의 합을 계산하는 프로그램 예제
arrary = [3,5,1,2,4]
summary = 0 

for x in array:
    summary += x
print(summary)
  • 수행 시간은 데이터의 개수 N에 비례함을 예측할 수 있음
  • 시간 복잡도: O(n) | 선형함수

[예제2]

  • 2중 반복문을 이용하는 프로그램
array = [3,5,1,2,4]

for i in array:
    for j in array:
        temp = i*j
        print(temp)
  • 시간 복잡도 : O(N2N^2)
  • 사실 모든 2중 반복문의 시간 복잡도가 O(N2N^2) 인 것은 아닙니다.

알고리즘 설계 팁

  • 일반적으로 CPU 기반의 개인용 컴퓨터는 연산횟수가 5억을 넘기는 경우
    • C언어 - 1 ~ 3초 소요
    • 파이썬 - 5 ~ 15초 소요
      • PyPy의 경우 때때로 C언어보다도 빠르게 동작하기도함
  • O(N3O(N^{3})의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까요?
  • 코딩 테스트 문제에서 시간제한은 통상 1~5초가량이라는점
    • 통상 퍼포먼스를 확인하는 경우 최대 5초라는점만 유의. 그 이상은 노우~!

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

  • 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)입니다.
  • 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같아요
    • N의 범위가 500인 경우 : 시간 복잡도가 O(N3O(N^{3})인 알고리즘 설계로 문제 해결 가능
    • N의 범위가 2,000인 경우 : 시간 복잡도가 O(N2O(N^{2})인 알고리즘 설계로 문제 해결 가능(예.이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort))
    • N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogNO(NlogN)인 알고리즘 설계로 문제 해결 가능(예. 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort))
    • N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(NO(N)인 알고리즘 설계로 문제 해결 가능(ex. 이진트리)

알고리즘 문제 해결 과정

하나. 지문읽기 및 컴퓨터적 사고
둘. 요구사항(복잡도) 분석
셋. 문제 해결을 위한 아이디어 찾기
넷 소스코드 설계 및 코딩

수행 시간 측정 소스코드 예제

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

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

자료형

  • 모든 프로그램은 결국 데이터를 다루는 행위
  • 파이썬의 자료형은 정수, 실수, 복소수, 문자열, 리스트, 튜플, 사전 등이 대표적입니다.

지수표현 방식

1억을 표기할때 통상 숫자를 100,000,000 이렇게 하드 코딩하는 경우가 있는데요. 지수 표현 방식을 이용하면 더 간단해요.

  • 바로 eorE를 이용하는 지수 표현 방식이 있어요.

  • 예. 1e9라고 입력하게 되면, 10의9제곱(1,000,000,000), 10억이 됩니다.

  • 지수 표현 방식은 임의의 큰 수를 표현하기 위해 자주 사용

  • 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단 거리를 무한(INF)로 설정

  • 이때 가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9를 이용

>>> 1e9
1000000000.0
>>> 75.25e1
752.5
>>> 3954e-3
3.954
>>>

실수형 더 알아보기

  • 오늘날 가정 널리 쓰이는 IEEE754 표준에서는 실수형을 저장하기 위해 4바이트, 또는 8바이트의 고정된 크기의 메모리를 할당하므로, 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가져요.
  • 예. 10진수에서 0.3+0.6= 0.9 떨어짐
  • 그러나 2진수에서는 표현방법이 없음
  • 컴퓨터는 최대한 0.9에 가깝게 표현하지만, 미세한 오류 발생
>>> a = 0.3+0.6
>>> a
0.8999999999999999
>>> if a ==0.9:
...     print('0.9입니다')
... else:
...     print('0.9가 아니라는데요?!')
... 
0.9가 아니라는데요?!
>>>
  • 개발 과정에서 실수 값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수 있음
  • 이럴 때는 round()함수를 이용!!
  • 예. 123.456을 소수 셋째자리에서 반올림 -> round(123.456,2)
    • 123.46 출력!
>>> a = 0.3+0.6
>>> round(a,4)
0.9
>>> if round(a,4) == 0.9:
...     print('0.9출력')
... else:
...     print('0.9아님')
... 
0.9출력
>>>

O(1)O(1) :
O(NlogN)O(NlogN) :
O(N)O(N) : for
O(n log n)
O(N2N^2):
O(2N22N^2)

리스트 자료형의 메서드 시간 복잡도

이름사용법시간복잡도
append변수명.append()O(1)
sort()변수명.sort()O(NlogN)O(NlogN)
sort()변수명.sort(reverse=True)O(N)O(N)
reverse()변수명.reverse()O(N)O(N)
insert()insert(삽입할 위치 인덱스, 삽입할 값)O(N)O(N)
count()변수명.count(특정값)O(N)O(N)
remove()변수명.remove(특정값)O(N)O(N)

튜플을 사용하면 좋은 경우

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

사전 자료형

  • 키-값의 쌍을 데이터로 가지는 자료형
  • 변경 불가능한(임뮤터블) 자료형을 키로 사용 할 수 있음
  • 파이썬의 사전 자료형은 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)O(1)의 시간에 처리 할 수 있음

집합 자료형

  • 특징
    • 중복 노우!
    • 순서 없음
  • 집합은 리스트 또는 문자열을 이용해서 초기화가능
    • 이때 set()함수를 이용
  • 중괄호({})안에 각 원소를 콤마를 기준으로 구분하여 삽입함으로써 초기화 가능
  • 데이터의 조회 및 수정에 있어서 O(1)O(1)의 시간에 처리할 수 있습니다.
# 집합자료 초기화 방법1
>>> data = set([1,1,1,1,1,1,1,2,3,4,5])
>>> data
{1, 2, 3, 4, 5}
# 집합 자료 초기화 방법2
>>> data = {1,1,1,1,1,1,1,1,1,2,3}
>>> data
{1, 2, 3}

사전 자료형과 집합 자료형의 특징

  • 리스트나 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있습니다.
  • 사전 자료형과 집합 자료형은 순서가 없기 때문에ㅐ 인덱싱으로 값을 얻을 수 없습니다.
    • 사전의 키 혹은 집합의 원소를 이용해 O(1)O(1)의 시간 복잡도로 조회합니다.

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

  • input() 함수는 한 줄의 문자열을 입력받는 함수
  • map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적요할 때 사용
    • ex. 공백을 기준으로 구분된 데이터를 입력 받을 때는 아래와 같이 사용
      • list(map(int, input().split()))
    • ex. 공백을 기준으로 구분된 데이터를 입력 받을 때는 아래와 같이 사용
      • a, b, c = map(int, input().split())

빠르게 입력 받기

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

data = sys.stdin.readline().rstrip() # 대부분 이렇게 묶음으로 사용합니다.
print(data)

조건문의 간소화

  • 조건문에서 실행될 소스코드가 한 줄인 경우, 굳이 줄 바꿈을 하지 않고도 간략하게 표현
score = 85

if score>=80: result = 'Success'
else: result = 'Fail'
  • 조건부 표현식(Conditional Expression)은 if~else문을 한줄에 작성 할 수 있게 해줘요.
score = 85
result = 'Success' if score >= 80 else 'Fail'

return으로 여러 개 반환하기

  • 파이썬에서 함수는 여러 개의 반환 값을 가질 수 있어요.
>>> def operator(a,b):
...     one   = a+b
...     two   = a-b
...     three = a*b
...     four  = a/b
...     return one, two, three, four
... 
>>> a,b,c,d = operator(7,3)
>>> print(a,b,c,d)
10 4 21 2.3333333333333335

람다 표현식

  • 람다 표현식은 함수보다 더 간단한 이용을 가능하게함
    • 특정 기능을 수행하는 함수를 한 줄에 작성한다는 점
def add(a,b):
    return a+b

print(add(3,7))

print((lambda a,b: a+b)(3,7))
print((lambda a,b: (a*b//math.gcd(a,b)) (3,4)

내장 함수에서 자주 사용되는 람다함수

>>> array = [('홍길동', 50),('홍길동', 50),('홍길동', 50) ]
>>> 
>>> def my_key(x):g
...     return x[1]
... 
>>> print(sorted(array, key=my_key))
[('홍길동', 50), ('홍길동', 50), ('홍길동', 50)]
>>> print(sorted(array, key=lambda x: x[1]))
[('홍길동', 50), ('홍길동', 50), ('홍길동', 50)]

여러 개의 리스트에 적용

>>> list1 = [1,2,3,4,5]
>>> list2 = [6,7,8,9,10]
>>> 
>>> result = map(lambda a,b: a+b, list1, list2)
>>> 
>>> print(list(result))
[7, 9, 11, 13, 15]
>>>

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

  • 내장함수 : 기본 입출력 함수부터 정렬함수까지 기본적인 함수들을 제공
    • 파이썬 프로그램 작성 시 필수적 기능 제공
  • itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 기능 제공
    • 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용
  • heapq ; 힙 자료구조 제공
  • bisect: 이진 탐색 기능 제공
  • collections: deque, Counter등의 유용한 자료구조 포함
  • math : 필수적인 수학 기능 제공
    • 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)같은 상수를 포함

순열과 조합

  • 순열: 서로 다른 n개에서 서로 다른 r 개를 선택하여 일렬로 나열하는 것
    • {'A','B','C'}에서 두 개를 선택하여 나열하는 경우 : 'ABC', 'ACB', 'BAC', 'BCA', 'CAB','CBA'
>>> from itertools import permutations
>>> 
>>> data = ['A','B','C'] # 데이터 준비
>>> 
>>> result = list(permutations(data, 3)) # 모든 순열 구하기
>>> print(result)
[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
  • 조합: 서로 다른 n개에서 순서에 상관 없이 서로 다른 r 개를 선택
    • {'A','B','C'}에서 순서를 고려하지 않고 두 개를 뽑는 경우 : 'AB', 'AC', 'BC'
>>> from itertools import combinations
>>> data = ['A','B','C'] # 데이터 준비
>>> result = list(combinations(data, 3)) # 2개를 뽑는 모든 조합 구하기
>>> print(result)
[('A', 'B', 'C')]

중복 순열과 중복 조합

from itertools import product

data = ['A','B','C'] # 데이터 준비
result = list(product(data, repeat=2)) # 2개를 뽑는 순열 구하기(중복 허용)
print(result)


from itertools import combinations_with_replacement

data = ['A','B','C'] # 데이터 준비
result = list(combinations_with_replacement(data, repeat=2)) # 2개를 뽑는 조합 구하기(중복 허용)
print(result)

Counter

  • 파이썬 collections라이브러리의 Counter는 등장 횟수를 세는 기능을 제공
  • 리스트와 같은 반복 가능한 객체가 주어졌을때 내부의 원소가 몇 번씩 등장했는지를 알려줍니다. 
>>> from collections import Counter
>>> 
>>> counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
>>> 
>>> print(counter['blue'])
3
>>> print(counter['green'])
1
>>> print(dict(counter))
{'red': 2, 'blue': 3, 'green': 1}

최대공약수(Greatest common divisor)와 최소 공배수(Least common multiple)

  • 최대 공약수를 구해야 할 때는 math 라이브러리 gcd() 함수를 이용할 수 있습니다. 
import math

def lcm(a,b):
    return a * b //math.gcd(a,b)

a = 2
b = 14

print(math.gcd(21,14)) # 최대 공약수 계산
print(lcm(21,14)) # 최대 공약수 계산
profile
Hyeseong
어제보다 오늘 그리고 오늘 보다 내일...
다음 포스트

알고리즘 - 그리디&구현

0개의 댓글

관련 채용 정보