알고리즘 중간고사 대비 겸 개발을 위한 CS 준비 겸 알고리즘 배우는 내용을 벨로그에 정리하려고 한다. A+ 가보자고 (모든 코드는 python으로 진행된다.)
1. 시간복잡도와 공간복잡도
✅알고리즘이란?
- 주어진 문제를 해결하기 위한 절차 혹은 방법
- 모호성이 없고 실행 가능하며 종결이 이루어지는 절차의 집합
같은 문제라도 더욱 효율적인 코드를 짜기 위해서는 알고리즘에 대한 이해가 필요하다!
⚠️자연수 n을 입력받아서, n이 소수인지 아닌지 판단하는 Python 프로그램을 작성해봐.
1번 해답
n = input()
n = int(n)
last_number = n - 1
for i in range(2, last_number + 1) :
if (n % i) == 0:
print('소수가 아닙니다.')
break
else:
print('소수입니다.')2번 해답
n = input()
n = int(n)
last_number = int(n ** 0.5)
for i in range(2, last_number + 1) :
if (n % i) == 0:
print('소수가 아닙니다.')
break
else:
print('소수입니다.')1번보다는 2번이 더 효율적으로 작동하는 코드다.
만약 n = 17 이라면
1번 코드는 2부터 16까지의 숫자를 하나하나 대입해보아야 하지만
2번 코드는 17의 루트 값 4.xx의 값보다 작은 2, 3으로만 나누면 되기 때문이다.
✅시간 복잡도란? (Time Complexity)
- 어떤 프로그램이 소요하는 시간을 나타내는 개념
- (시간복잡도)TC = (컴파일 시간)c + (실행 시간)T(n)
- 컴파일 시간은 프로그램을 만드는 데 소요되는 시간, 실행 시간은 프로그램이 돌아가는 데 소요되는 시간이다.
- 프로그램 분석에서는 컴파일 시간 < 실행 시간
📍공간복잡도(메모리 차지 정도)를 덜 중요하게 여기는 이유는 기술 발달에 따라 큰 문제가 되지 않기 때문이다.
✅중요한 것은 실행시간, 우리가 집중해야 할 것은?
n = input()
n = int(n)
last_number = n - 1
-----------------------
for i in range(2, last_number + 1) :
if (n % i) == 0:
print('소수가 아닙니다.')
break
else:
print('소수입니다.')- 변수 선언 과정은 무시(구분선 위)할 때 연산 실행 횟수(구분선 아래)에 집중한다.
- 해당 코드에서 % 연산과 == 연산이 (n-2)번씩 실행되기 때문에 여기서의 시간복잡도는 T(n) = 2n -4이다.
➡️ 2, 3, ... (n-1)까지 계산 -> (n-2)개 *2번 -> 2n - 4
2. Big-O와 시간복잡도의 표현
✅Big-O notation이란?
다음 명제가 참인 경우, T(n) = O(g(n))이라 할 수 있음
➡️모든 n >= n에 대하여, T(n) <= cg(n)이 되게 하는 c와 n이 존재
여기서 n은 측정값이며 이를 구하기 위해서는 c와 n을 찾으면 된다.
✅이 명제를 앞선 시간복잡도에 적용해보자
모든 n >= n에 대하여, T(n) <= cg(n)이 되게 하는 c와 n이 존재하면 T(n) = O(g(n))
연산을 쉽게 하기 위해 g(n) = n이라 한다.
n = input()
n = int(n)
last_number = n - 1
for i in range(2, last_number + 1) :
if (n % i) == 0:
print('소수가 아닙니다.')
break
else:
print('소수입니다.')T(n) = 2n -4인데,
모든 n >= n*에 대해서, T(n) = 2n -4 <= cn
위 식에서 n*=1, c = 2이라면 모든 경우를 만족한다.
따라서, 시간복잡도 T(n) = O(n)이라고 정리할 수 있다.
✅직관적인 Big-O 해석을 위해 숙지해야 할 규칙
1. 가장 중요한 항 이외에는 시간복잡도에서 무시된다.
만약 빚이 7억 50만원이 있다고 치자. 그렇다면 사람들은 "나 빚이 7억 있어."라고 말하지 "나 빚 7억 50만원 있어" 라고 하지 않을 것이다. 50만원은 7억에 비해서 미미한 영향을 가지기 때문이다.
이와 같이 시간복잡도에서도 큰 영향을 주지 않는 수는 무시된다.
📍시간복잡도 T(n) = 2n -4 라면
상수항 4는 영향을 주지 못하므로 T(n) = O(2n)으로 정리한다.
2. 상수 하나 곱한다고 시간 복잡도에 영향을 줄 수 없다.
이것도 1번과 비슷하게 큰 영향을 주지 못하면 시간복잡도에서 무시된다. 상수항의 곱도 큰 영향을 주지 못하므로 시간복잡도에서 무시한다.
Big-O Notation의 정의를 보면 g(n)의 상수항 곱인 c가 영향을 주지 못해제외되는 것을 볼 수 있다.
모든 n >= n에 대하여, T(n) <= cg(n)이 되게 하는 c와 n이 존재하면 T(n) = O(g(n))
📍그렇기 때문에 O(2n) => O(n)으로 표기하는 것이 타당하다.
t(n) = 30n2 + 45n + 15 -> O(n2)
3. 일단 최대한 단순화해 놓고, 비교하기 편한 것부터 보자
여기까지 봤을 때 시간복잡도는 최대한 덜어놓을 것 다 덜어놓고 큼직한 요소만 본다는 느낌이 든다. 그래서 식을 최~~~대한 단순화 시켜놓고 비교를 한다.
만약 아래의 세 식을 비교한다면
1️⃣ T1(n) = 5n2 + 2n + 10 => O(n2)
2️⃣ T2(n) = (n+1)logn = nlogn + logn(상수) => O(nlogn)
3️⃣ T3(n) = 125(n) + 350 => O(n)
O(n2) > O(nlogn) > O(n)
4. n*하나만 찾으면 되니 n이 한없이 커질 때를 생각하자
시간복잡도의 비교를 위해서는 n값을 비교해야 한다. 비교하는 가장 쉬운 방법은 n이 한없이 커지는 경우를 생각하는 것이다.
만약 2**n과 n**2를 비교한다면,
2**n은 n+1가 되면 2배씩 커지지만
n**2는 n+1가 되면 1. 0000x배가 커지기 때문에 2**n이 훨씬 크다는 것을 알 수 있다.
3. 여러 가지 점근적 표기법
❓Big-O 표기법에 한계가 있다
Big-O 정의를 생각한다면 T(n) = 2n 4 -> 모든 자연수 n에 대해 T(n) <= n**777은 성립힌다.
그러므로 T(n) = O(n**777)이다 (???)
이 한계를 극복하기 위해
✅Big-Omega Notation
다음 명제가 참인 경우, T(n) = 오메가(g(n))이라고 할 수 있다.
-> 모든 n >= n에 대하여, T(n) >= cg(n)이 되게 하는 c와 n이 존재
Big-O와 부등호 방향이 반대!(보다 큰 것을 찾는 것) -> 니보다 연산이 적다!
오메가는 보다 작은 것을 찾는 것 -> 니보다 연산이 많다!
✅Big-Theta Notation
다음 명제가 참인 경우, T(n) = 빅세타(g(n))이라고 할 수 있다.
-> 모든 n >= n에 대하여, c1g(n) <= T(n) <= c2g(n)이 되게 하는 c와 n이 존재
사이 값을 찾는 것 (샌드위치)
📍T(n) = 4n4 +8
= O(n4) = O(n5) = O(n6) = O(n7)
= 오메가(n4)** = 오메가(n3) = 오메가(n2) = 오메가(n1)
= 빅세타(n4)
빅세타와 오메가가 겹치는 부분이 n4이기 때문에 빅세타 (n4)가 되는 것이다.
🧩문제 1
다음은 T(n) = 5n3 + 2n - 100의 시간복잡도 표현을 도출해내는 과정이다.
두 빈칸에 들어갈 기호 혹은 식은?
2보다 큰 임의의 자연수 n에 대하여, 다음이 성립한다.
n3 _ 5n3 + 2n - 100
따라서, 준식 T(n) = ____(n3)으로 나타낼 수 있다.
답: <, 오메가
오메가는 니보다 연산이 많다!! 오메가(n3)은 n3보다 연산이 많다!!!
🧩문제 2
다음 다섯가지 알고리즘의 수행시간 복잡도를 각각 Big-Theta 표현으로 바꾸어 나타냈을 때, 수행시간 효율이 두 번째로 좋은 것은?
1️⃣ (2n+3)log7n
2️⃣ n + n2 + n4 + n8
3️⃣ log1.001n
4️⃣ 5n + n5
5️⃣ 2n0.5 + 7n - 100
- 빅세타(nlogn)
- 빅세타(n8)
- 빅세타(logn)
- 빅세타(5**n)
- 빅세타(n)
=> 4 > 2 > 1 > 5 > 3
📍로그의 밑은 중요하지 않다. -> 상수이기 때문
시간복잡도 최악과 최고, 평균
n = input()
n = int(n)
last_number = n - 1
for i in range(2, last_number + 1) :
if (n % i) == 0:
print('소수가 아닙니다.')
break
else:
print('소수입니다.')📍최악인 경우 시간복잡도는 빅세타(n)
ex) n = 13, 29, 311
2부터 n-1까지의 연산을 모두 수행해야 함
📍최고인 경우 시간복잡도는 빅세타(1)
ex) n = 124, 280, 3972
if (n % i) == 0:
print('소수가 아닙니다.')여기에서 끝
4. Brute-Force와 시간복잡도
✅Brute Force란?
- 가능한 모든 경우를 시도하여 원하는 답을 찾아내는 알고리즘 -> 다해본다, 노가다...
- 직관적이며 적용하기 쉬우나 과정이 매우 느릴 수 있음
Brute Force를 적용할 수 있는 사례
세 자리 자연수 337을 구성하는 자릿수는 3, 3, 7의 세 개이며 337 + 3 + 3 + 7 = 350이다. 이처럼, 어떤 수와 자릿수를 모두 더했을 대 수를 '대장 수'라 하고 원래의 수를 '졸병 수'라 하자. 이를 테면, 대장 수가 350일 때 337은 졸병 수가 되는 것이다.
대장 수를 입력받았을 때, 졸병 수를 출력하는 Python 프로그램을 작성하면?
졸병 수가 여럿 존재할 경우 가장 작은 값 하나만 출력해야 하며, 졸병 수가 없는 경우 NONE을 출력해야 한다.
📍입력받은 대장 수를 N이라 할 대, 졸병 수는 기껏해야 1부터 N 사이에 존재할 수밖에 없다.
📍1부터 N까지 모든 수에 대해 반복문을 적용, 각각의 수가 졸병 수의 조건을 충족하는지 살펴본다.
def digit_sum(n) :
sum = n
while (n > 0) :
sum = sum + (n % 10) <!--n의 자릿수만큼 반복-->
n = n // 10
return sum
N = input()
N = int(N)
for i in range(1, N+1) : <!--N회 반복-->
if digit_sum(i) == N:
print(i)
break
else :
print('NONE')📍파이썬에서
n // 10은 몫을 구하는 것이고
n % 10은 나머지를 구하는 것이다.
📍시간복잡도
1. digit_sum 함수: n의 자릿수만큼 반복
=> log10N * N = NlogN
(로그의 밑은 무시)
2. for문을 돌면서 1부터 N까지의 모든 수를 졸병의 후보로 설정 : Nghl
T(n) = NlogN + N
📍최악의 경우 시간복잡도를 빅세타로 Big-Theta 표기법으로 나타낸다면?
T(N) = NlogN + N
빅세타(NlogN)
🧩문제 3
N개의 자연수가 주어졌을 때, 이들 중 셋 이상의 배수인 최소의 자연수를 출력하는 Python 프로그램을 작성하시오. 입력 창에 N개의 자연수가 중복 없이 띄어쓰기로 구분되어 입력된다.
N의 값은 3 이상 40 미만이며, N개의 수 각각의 값은 1이상 500 미만이다.
입력 예시: 30 20 40 10
출력 예시: 40
📍500 500 500. 1부터 1억2만5천 사이에 무조건 세 개 곱배수 하나는 튀어나온다.
numbers = input()
numbers = numbers.split()
for i in range(0, len(numbers)) :
numbers[i] = int(numbers[i])
max_tagert = 500 * 500 * 500
for i in range(1, max_tagert) :
count = 0
for each_number in numbers :
if (i % each_number) == 0:
count = count + 1
if (count >= 3) :
print(i)
break
