[TIL] 복잡도, 그리디 알고리즘

이지예·2022년 4월 16일

알고리즘

목록 보기

1/8

백준 사이트에서 문제를 풀다보니 알고리즘에 대한 공부가 더 필요할 것 같아서 추가로 공부한 내용을 정리했다. 유튜브에서 (이코테)이것이 취업을 위한 코딩 테스타다 라는 강의를 참고했다.

특정한 알고리즘의 성능을 분석하기 위해서 시간복잡도와 공간복잡도 두가지를 분석하는데,

시간복잡도 : 특정한 크기의 입력에 대해서 알고리즘의 수행시간 분석용
공간복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석을 목적

동일한 기능을 수행하는 알고리즘이 있으면 복잡도가 낮을수록 더 좋은 알고리즘이다.
복잡도가 높다고 하는것은 시간이나 메모리가 많이 필요하다고 할 수 있다.

가장 빠르게 증가하는 항만을 고려하는 표기법
함수의 상한(가장 큰 항)만을 고려한다. 극한의 개념으로 생각하면 편하다.
빅오표기법 순위와 명칭으로는 좋음에서 나쁨순으로 정리하면 다음과 같다.

1(상수 시간) - lonN(로그 시간) - N(선형 시간) - NlogN(로그 선형 시간) - N^2(이차 시간) - N^3(삼차 시간) - 2^n(지수 시간)

상수시간 : 반복문 1개
이차시간 : 2중 반복문

문제에서 가장 먼저 확인해야 할 내용은 시간제한(수행시간 요구사항)이다.
<수행시간 측정 코드 >

import time
start_time=time.time()#측정 시작
#프로그램 소스 코드
end_time=time.time()#측정 종료
print("time:",end_time-start_time

현재 상황에서 가장 좋은 것을 고르는 방법
단순히 가장 좋아 보이는 것을 선택해도 최적의 해를 구할 수 있는지 검토하는 정당성 분석이 중요하다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을때가 많다.

하지만 코딩테스트로 나온 그리디알고리즘문제에서는 탐욕법으로 얻은해가 최적의 해가 되는경우에 한해서문제를 출제하는경우가 많다.

예) 동전 종류가 주어지고, 최소 동전으로 돈 지불하는 문제

해결법 : 큰단위부터 거슬러준다.
정당성 분석 : 큰 단위가 작은 단위의 동전의 배수이므로 큰단위부터 거슬러주게 되면 지불해야하는 동전 숫자가 줄어든다.
화폐 종류가 K라고 할 때 코드의 시간복잡도는 O(K)이다.

문제1) N을 1이 될때까지 1로 빼거나 K로 나눈다. 최소횟수를 구하여라

해결법 : N이 최대한 많이 나누기를 하면 된다.
정당성 분석 : N의 크기를 줄일때 1로 빼는것보다 2이상의 수로 나누는것이 더 효과적이다
코드 : 입력받은 값N이 K로 나누어 떨어지게 만들기 위해서 입력값//k*k로 나누어 떨어지는 수를 만들고 n과의 차이는 1을 뺀 횟수로 치고 count에 더한다. 나누어떨어지는 수로 만든것을 k로 나누고 count+=1 이 방법을 n이 1이 될때까지 반복한다. 반복문으로 n을 줄이는 방법은 한번 반복할때마다 n씩 나누게 돼서, 매번 k로 나누어떨어지는지 확인해서 1을 빼거나 나누는 방법보다 시간복잡도가 더 낮은 로그복잡도가 나올 수 있다.