알고리즘

1. 알고리즘이란?

알고리즘이란 문제 해결 방법이다

문제상황

3, 5, 1, 2, 4 라는 다섯개의 숫자를 오름차순 정렬하려고 한다. 

해결방법

1. 가장 작은 숫자를 맨앞에 둔다.

2. 나머지 숫자에서 작은 숫자를 두번째에 둔다

... 반복한다. 이때 해결방법이 알고리즘에 해당한다.

2. 실행시간(러닝타임)

우리가 작성한 코드를 컴퓨터로 실행시켰을 때의 시간

2-1. 예시

sum = 0      // 3ns

for i in range(1,100): // 3ns
	sum += i		// 2ns
    
print(sum)

이런 코드가 있다고 가정했을 때 주석처럼 한줄당 시간이 걸리고 반복문이었을 때, 반복문의 수만큼 곱하는 시간이 걸린다

즉,

sum = 0      // 3ns

for i in range(1,100): // 3ns X 100 = 300
	sum += i		// 2ns X 100 = 200
    
print(sum)

반복문의 코드 줄은 각각 200ns의 시간이 걸리게 된다. 즉 이 코드의 실행 시간은 530ns이고 만약 반복문에 1000번 이라면 실행시간도 10배 늘어나서 5030ns가 된다. 만약 반복문의 횟수가 n번이라면? 총 5n의 시간이 걸리게 된다. 이중반복문이라면 5n의 시간이 걸리는 코드를 n번 반복하기 때문에 3nX5n^2의 시간이 걸리게 된다.

그렇다면 지금까지 총 시간은 5n^2 + 3n + 30ns가 된다.(문제를 입출력하는 코드를 포함했을 시) 이것들을 시간복잡도 라고한다.

2-2. 시간 복잡도

위처럼 복잡한 식을 간편하게 사용하기 위헤서 Big-O표기법을 사용한다

2-2-1. Big-O

최고 차수만을 이용해서 표현한다 예를 들자면

T(n) = 5n^2 + 3n + 30ns 이라는 시간 복잡도가 있다면 최고차수은 n^2을 이용해서 O(n2)이라고 한다.

만약 최고차수가 n^2이 이하라면 전부 O(n)이라고 표기하고 상수밖에 없다면 O(1)이라고 표기한다

3. Case

• Best case
• Average case
• Worst case

처음에 했던 숫자 다섯개를 정렬할때는 정렬이 어떻게 되어있냐에 따라서 시간복잡도가 달라진다.(역순일때 가장 높다)

이때 가장 높은 시간복잡도를 Worst case 가장 낮은 시간 복잡도를 Best case라고 한다. 평균값을 Average case 라고 한다. 대부분 Worst 와 Average의 시간 복잡도가 같은 경우가 많아서 Worst case로 시간복잡도를 구한다.

4. 코딩테스트를 위한 시간복잡도

4-1. 코테를 푸는 순서

1. 문제 이해하기

2. 접근방법

3. 코드 설계

4. 코드 구현

4-2. 시간 복잡도 활용법

1. 시간복잡도 이해하고 외우기

2. 제한 조건 보는 법(이번시간)

3. 다양한 접근

4-2. 제약조건 보는법

코테를 풀다보면 이런 제약 조건들이 나온다.

1 <= n <= 10^5

이런 것들은 실행 시간이 작은 알고리즘을 생각해 내는지를 물어보는 문제이다. 보통 코딩테스트 에서는 10^8을 넘지 않게 풀어야한다.

실제로는 컴퓨터 마다 다르다!

4-2-1. 시간 복잡도의 순서

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^5)

4-2-2. 제약조건 계산법

예1) 1 <= n <= 10^5 이라면 O(n^2)을 했을 때 10^10의 시간복잡도가 나오고 10^8을 넘어감으로 쓰면 시간제한을 초과한다

예2) 1 <= n <= 10^4 같은 경우는 O(n^2)을 했을 때 10^8이기 때문에 간당간당 하다.

예) 1 <= n <= 7 같은 경우는 그냥 풀기만 하면 된다

5. 시간복잡도가 들어가는 문제

5-1. Tow sum

문제

정수가 저장된 배열 nums이 주어졌을 때, nums의 원소중 두 숫자를 더해서 target이 될 수 있으면 True 불가능하면 False를 반환하세요. 같은 원소를 두 번 사용할 수 없습니다.

제약조건 : 여기에서 어떤게 n인지 생각해야함

2 <= nums.length <= 10^4 : length 가 길어질수록 시간복잡도가 오래걸리지만 시간 복잡도를 건드릴 수 있음(당첨)

-10^9 <= nums[i] <= 10^9 : 시간복잡도 매우 낮아야함

-10^9 <= target <= 10^9 : target은 시간복잡도에 영향을 주지 않음

입출력

input : nums = {4,1,9,7,5,3,16}, target : 14
output : True

input : nums = {2,1,5,7}, target : 4
output : False

풀이

def towSum(nums, target):
    n = len(nums)
    print(n)

    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return True
    return False

완전탐색으로 풀었고(숫자 하나하나씩 다 계산하는 방법) O(n^2)의 시간이 걸린다.