알고리즘 - 들어가기 앞서

Hyeseong·2021년 3월 27일

기본 라이브러리 빅오표기법 이코테 자료형

알고리즘

목록 보기

1/9

들어가기 앞서

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

해외

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

국내

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

알아 둬야할 알고리즘 유형

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

복잡도(Complexity)

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

시간 복잡도 : 알고리즘의 수행시간 분석

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

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

빅오 표기법(Big-O Notation)

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

함수의 상한만을 나타냄

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

빅오 표기법에서는 차수가 가장 큰 항만 남기므로 $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( $N^2$ ): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
O( $2N^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( $N^2$ )
사실 모든 2중 반복문의 시간 복잡도가 O( $N^2$ ) 인 것은 아닙니다.

알고리즘 설계 팁

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

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

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

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

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

튜플을 사용하면 좋은 경우

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

사전 자료형

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

집합 자료형

특징
- 중복 노우!
- 순서 없음
집합은 리스트 또는 문자열을 이용해서 초기화가능
- 이때 set()함수를 이용
중괄호({})안에 각 원소를 콤마를 기준으로 구분하여 삽입함으로써 초기화 가능
데이터의 조회 및 수정에 있어서 $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)$ 의 시간 복잡도로 조회합니다.

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

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)) # 최대 공약수 계산

Hyeseong

어제보다 오늘 그리고 오늘 보다 내일...

다음 포스트