[바킹독: 알고리즘] 기초 코드 작성 요령 1 - (1)

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다.

비상업적 목적임을 다시 알려드리며, 출처는 아래 링크와 같습니다.

 

[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

출처: blog.encrypted.gg/922?category=773649

---

시간/공간 복잡도

컴퓨터는 1초당 3 - 5억 번의 연산을 수행합니다. ( 더하기, 나누기 등의 연산도 고려하자면 추정치라 생각하자.)  만약 주어진 문제의 제한시간이 1초라면, 3 - 5억 번의 연산 안으로 모든 연산을 끝내야 한다는 것과 유사합니다.

 

예제를 살피겠습니다.

 

배열의 요소에 5의 배수가 몇 개 들어있는지 출력하세요.

 

 

이 메서드의 연산 횟수를 계산해보겠습니다.

 

• 15번 : 변수를 선언하고 0으로 초기화    -->   1번
  
  
• 16번 : 변수 i를 선언하고 0으로 초기화  -->  1번
  
  
• 16번 : n번에 걸쳐 반복문 수행
            i가 n보다 작은지 확인 후, 작을 경우 i 증가  -->  2번
  
  
• 17번 : 5로 나누고, 0과 일치하는지 확인 --> 2번
  
  
• 17번 : 조건 만족시 cnt를 1을 증가시킴   --> 1번
  
  
• 19번 : cnt 반환

총  [ 1+1+n*( 2+2+1 ) + 1  = 5n + 3 ] 번의 연산이 수행됩니다. 하지만 사람이 무수한 연산을 모두 게산할 수 없으니, 상수를 제외하고 n번의 연산이 필요하다고 합니다. 즉, n에 비례한다고 이야기합니다.

 

여러 번의 연산을 수행하며, n을 기준으로 연산횟수가 계산되기에 n에 비례한다고 판단할 수 있습니다.

 

무언가를 찾을 때, 앞에서부터 찾는다고 해보겠습니다. 이때, 하나 하나 체크하는 시간이 1초라고 가정하겠습니다. n개의 데이터가 있다고 했을 때, 마지막에 찾는 값이 존재한다고 했을 때, n초의 시간이 발생합니다. 만약 맨 처음 위치에 값이 존재한다면 1초가 걸릴 것입니다. 평균적으로 n/2초가 걸릴 것이고요.

 

그런데 만약 위 문제에서 순서대로 정렬되어 있다면 얼마만큼의 시간이 발생할까요? 업다운 게임을 생각해보겠습니다. 50까지 숫자 중 첫 숫자를 부르는 사람은 보통 가운데 숫자인 25를 이야기합니다. 경우의 수를 절반으로 줄이는 것이지요. 이것처럼 중간 값을 기준으로 찾고자 하는 값이 중간 값보다 큰지, 작은지 판단하여 찾고자 하는 범위를 줄여갈 수 있습니다.

이때 최선의 경우는 중간 값이 바로 찾고자 하는 경우이며, 최악의 경우는 단 하나의 값이 남을 때까지 절반으로 값을 계속 쪼개어 나가는 것입니다.

 

사람을 찾는다 했을때, 16명이면 4번, 32명이면 5번과 같이 시간이 걸립니다. 이때 log N에 비례합니다.

 

자, 그런데 앞서 바로 찾고자 하는 데이터를 한 번에 찾으면 소요되는 시간은 1초 입니다. 허나, 최악의 경우는 log N이라하였는데 그 이유는 무엇일까요? 계속 반으로 쪼개어가며 값을 찾기 때문입니다.

 

---

 

시간복잡도(Time Complexity) : 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

빅오표기법(Big-O Notation) : 주어진 식을 값이 가장 큰 대표항만 남겨 나타내는 방법

 

위 내용은 무슨 뜻일까요?

앞서 무언가를 찾는 일에 맨 앞부터 확인할 경우 n초, 쪼개어가며 확인할 경우 log N초가 발생합니다. 이 n초와 log N초가 각 문제의 시간복잡도 입니다.

 

빅오표기법은 그렇다면 무엇일까요?

빅오표기법 외에 다른 개념도 존재합니다. 간단한 설명에 보면 [ 주어진 식을 값이 가장 큰 대표항만 남겨 나타내는 방법 ]이라고 정의되어 있습니다.

 

O(N) : 5N + 3, 2N + 10logN, 10N

앞선 예제에서 'n에 비례한다', 'log N에 비례한다'고 이야기했습니다. 이러한 표현이 빅오표기법에서 하는 일인데요. 위 예제로 이야기해보겠습니다.

 

[ 5N + 3 ]을 보았을 때, N이 커지면 커질수록 식에 존재하는 상수인 3보다 수가 훨씬 커집니다. 그래서 3을 버리고 5N만 처음에 남기지만, 빅오표기법은 5N에 있는 상수 5조차 떼어버립니다.

 

결국 [ 5N + 3 : O(N) ]이 되는 것이지요.

 

[ 2N + 10 log N ]식 또한 마찬가지 입니다. N이 커지면 커질수록 10 log N 보다 2N이 더 커집니다.  2N을 빼고 상수를 빼내어, O(N)만 남기는 것입니다.

 

 

O(N²) : N² + 2N + 4, 6N² + 20N + 10 log N

[ N² + 2N + 4 ]를 살피겠습니다. N²이 2N과 4보다 훨씬 크기에 O(N²)이 되는 것입니다.

 

 

O(N log N) : N log N + 30N + 10, 5 log N + 6

마찬가지로 N을 대입했을 때, 30N보다 N log N이 더 크기에 빅오표기법은 O(N log N)이 되는 것입니다.

 

 

O(1) : 3, 5, 10

반면에 값이 단순히 상수일 경우에는 O(1)이 되는 것입니다.

 

---

 

보통 시간복잡도를 표기할 때, 빅오표기법의 형태로 표기합니다. (그래프는 영상 내 PPT 자료를 참고해주세요. )

 

N의 크기에 따라 시간복잡도. 즉 수행시간에 큰 영향을 준다는 것을 알 수 있습니다. 시간복잡도에 따른 수행시간의 비교입니다.

 

빠름                                                                             오래 걸림

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!)

 

• O(log N) : 로그 시간
• O(N) : 선형 시간
• O(log N) ~ O(N²) : log N 혹은 N의 거듭제곱끼리의 곱으로 시간복잡도가 나타내질 경우 = 다항 시간
• O(2^N) : 지수 시간 ( N <= 25일 경우가 아니면 시간 제한을 통과하기 어려움 )
• O(N!) : N 팩토리얼, 지수 시간보다 가파르게 올라감

 

그렇다면 시간복잡도는 코딩테스트에서 어떻게 쓰일까요? 입력되는 값의 범위를 보고 문제에서 요구하는 시간복잡도가 어느 정도인지 파악할 수 있습니다. 

 

N의 크기에 따른 허용 시간복잡도는 다음과 같습니다.

 

N의 크기	허용 시간복잡도
N <= 11	O(N!)
N <= 25	O(2N)
N <= 100	O(N4)
N <= 500	O(N3)
N <= 3,000	O(N2 log N)
N <= 5,000	O(N2)
N <= 1,000,000	O(N log N)
N <= 10,000,000	O(N)
그 이상	O(log N), O(1)

 

이 기준이 절대적인 것은 아니기에 위 표로 대략적으로 기억하면 될듯합니다.

 

---

 

이로 문제를 풀이할 때, 유의할 사항 한 가지를 더 알게된 것입니다. 풀이를 떠올린 뒤, 나의 알고리즘이 시간복잡도 내로 해낼 수 있는지 말입니다.

 

그렇다면 나의 풀이의 시간복잡도는 어떻게 알 수 있을까요? 문제를 풀며 해봅시다.

 

---

 

 

공간복잡도(Space Complexity)

입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 

 

 

예시를 들어보겠습니다. 크기 N의 2차원 배열이 필요하면 O(N2)이고, 따로 배열이 필요 없으면, O(1)이 됩니다. ( 하지만 코딩테스트에서 시간복잡도때문에 문제를 틀리는 경우가 더 많습니다. )

하지만! 기억해두어야 할 사항이 있습니다. 메모리 제한이 만약 512MB일 때, int 변수를 대략 1.2억개 정도 선언할 수 있다는 것을 기억하는 것이 중요합니다. 이는 자료형의 크기로 계산할 수 있습니다.

 

 

 

[바킹독: 알고리즘] 기초 코드 작성 요령 1 - (2) 자료형