- 1일차 기초 코드 작성 요령 (시.공간복잡도,실수)

해당 포스터는 파킹독님의 유튜브를 보고 작성되는 점 참고해주세요.

https://www.youtube.com/watch?v=9MMKsrvRiw4

시간복잡도

---

1. 컴퓨터는 1초에 대략 3~5억 개 정도의 연산이 가능하다.(횟수차이존재)
   1. 단순한 연산(and, or, +, -)
   2. 복잡한 연산(*, /, function call, =)

 

그럼 아래의 소스코드를 한 번 해석해보자. (스스로 한 번 진행해보자)

int func1(int arr, int n){
    int cnt=0;
    for(int i=0;i<n;i++){
      if(arr[i] % 5 == 0)cnt++;
    }
    return cnt;
}

1. cnt 변수에 대입 한 번
2. for문에서 i 초깃값 대입 한 번 그리고 총 n번 반복
   1.  반복 되는 동안 if문을 통해서 arr[i]에 접근 한 번
   2. 그 값이 5로 나뉘고 0과 같은지 판별 한 번(2번 연산)
   3. 그랬을 시 cnt값 증가
   4. i가 n보다 작은지 판별
   5. i가 하나 증가
3. 마지막에 cnt 값 리턴

총 1 + 1 + n*(2+3+1)+1 = 6n+3 이라고 할 수 있겠네요.

 

• if n==1억 =>최대 2초 정도 시간 소요
• if n==10억 => 최대 20초 정도 시간 소요

 

하지만 매번 이런 식으로 연산의 모든 횟수를 따져보면서 시간복잡도를 계산하면 매우 힘들 것이다.

 

그렇기에 우리는 Big - O 표기법을 이용하여 코드의 수행 시간을 계산한다.

여기서는 Big - O 표기법에 대해 자세하게 서술하지는 않겠다.

Big - O 표기법은 간단하게 얘기해서 연산 횟수의 최고 차항만 갖고 와서 표기하는 것이다.

위의 예시를 봐보자. 6n+3 일 때는 O(n) 이라고 표현할 수 있겠다.

그럼 6n^2 + 3n + 2 라고 하면 O(n^2) 이라고 표편할 수 있다.

Big - O 표기법에서 그래프는 크게 위의 그림처럼 나뉘게 된다.

O(1) <= O(lgn) <= O(n) <= O(nlgn) <= O(n^2) <= O(2^n)

 

이렇게 나타낼 수 있겠다.

 

그럼 우리는 문제의 제한 정도 + 시간제한을 보고 이 문제가 어떤 시간복잡도를 써야 가능하겠다를 생각할 수 있다.

 

예를 들어 모든 수행은 1초 안에 끝나야 된다는 것을 전제로 하자면

N<=25라면 O(2^n)의 시간복잡도로 가능할 것이다.

N<=100라면 O(n^4)의 시간복잡도로 가능할 것이다.

 

n의 크기에 따른 허용된 시간복잡도 (수행시간 1초)

이렇듯이 우리는 제한 시간과 값의 제한 범위를 보고 어떤 시간복잡도의 알고리즘을 사용해야 문제를 풀 수 있는지 추측할 수 있다!

 

 

공간복잡도

---

공간 복잡도를 초과하는 문제는 웬만해서는 잘 안 나온다.

공간 복잡도는 자신의 코드에서 사용하는 총 메모리의 크기를 말하는 것이다.

예를 들어)

int main(){
    int i;
}

위와 같은 코드가 있다고 해보자. 그러면 int 자료형 i 변수가 하나가 선언되었기에 총 4byte의 공간을 차지하고 있는 것이다.

 

이것은 쉽게 계산할 수 있고 문제의 제한도 그리 빡빡하지 않기에 이것만 기억하고 가자.

 

만약 문제가 총 512MB의 메모리 제한이 있다면 1.2억개의 int 형 변수를 선언할 수 있다!

 

실수의 값 오차

---

이번에 얘기할 것은 실수의 값 오차에 대해 얘기해볼 것이다. 실수 값은 부동소숫점을 통해 값을 저장하기에 온전히 값을 저장할 수가 없다.

그래서 연산하는 과정에서 오차가 생길 수 있다.

 

이 부분에서 내가 얘기해주고 싶은 것은 오차가 생길 수 있으니 주의하며 사용할 것과 자료형에 따른 유효범위에 대해서 말해보겠다.

 

1. 실수는 float, double의 형태가 있다
   1. float는 4byte이고 double은 8byte이다.
   2. 값을 저장할 때는 당연히 double 자료형이 float보다 정밀하게 값을 저장할 수 있다.
   3. double은 15자리까지는 유효하게 계산가능하며 float는 6자리까지만 유효하게 계산 가능하다는 것이다.
   4. double에 long long을 함부로 저장하면 값의 오차 때문에 제대로 저장이 안 될 수 있다는 점. 
2. 실수의 값은 오차가 무조건 발생하게 된다.
   1. 값이 저장될 때는 2의 거듭제곱꼴로 저장되니 오차 발생이 가능함.(부동소숫점을 찾아보면 좋음)
   2. 그러기에 함부로 실수연산에서는 같다의 등호를 쓰면 큰일난다.

 

언제든지 댓글로 조언, 피드백 환영입니다.