난 큰 인물이 되고 싶긴 때문에 일단 사진 하나 박는다..
바킹독님 강의 오늘부터 하나씩 파헤칩니다...
그럼 시작!
🖐️시간 복잡도
-문제 1번-
(문제 설명) N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 10만 이하의 자연수이다.
int func1(int N){
int sum = 0;
for(int i=N; i>=3; i--){
if(i%3 == 0 || i%5 == 0){
sum += i;
}
}
return sum;
}내가 만든 func1 함수는 O(n)의 시간복잡도를 가진다.
-문제 2번-
(문제 설명) 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
int fun2(int arr[], int N){
for(int i=0; i<=N; i++){
for(int j=i+1; j<=N; j++){
if(arr[i]+arr[j] == 100 && i != j){
return 1;
}
}
}
return 0;
}내가 짠 코드이다. O(n2)의 시간복잡도. (생각해보니 if문에 i != j 조건 필요없네..)
3강에서 O(n)으로 푸는 방법을 소개한다고 함.
O(n2)인 이유는 이중for문이니까...라고 간단히 생각하겠지만 그래도 자세히 들여다보면..
i=0일 때 n-1개의 수에 대해 합을 100과 비교하고, i=1일 때 n-2개의 수에 대해 합을 100과 비교하고 이렇게 반복하니... (n-1) + (n-2) + ... + 3 + 2+ 1 = (n2-n)/2이므로 O(n2)이다.
-문제 3번-
(문제 설명) N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. n은 10억 이하의 자연수이다.
int func3(int N){
for(int i=2; i<N; i++){
if(i*i == N){
return 1;
}
}
}내가 짠 코드는 이렇다. O(n)...
int func3(int n){
for(int i=1; i*i <= n; i++){
if(i*i == N) return 1;
}
}바킹독님 코드.. O(√n)이므로 내가 짠 코드보다 훨씬 더 빨리 돌아간다. 바로 i*i <= n인지 확인하는 부분이 있기 때문에!!
(->작은 부분이지만 큰 차이를 만든다!! 꼼꼼하게 코딩하기!!!)
-문제 4번-
(문제 설명) N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.
int func4(int N){
int i = 2;
while(i*2 <= N){
i *= 2;
}
return i;
}내가 짠 코드...
시간 복잡도는... 음....
아래는 바킹독님 코드.. 똑같이 짰다....!
int func4(int N){
int val = 1;
while(2*val <= n) val *= 2;
return val;
}이렇게하면 N이 2k 이상 2k+1 미만이라고 할 때 while문 안에서 val은 최대 k번만 2배로 커진다.(2의 거듭제곱이니까) 그러고나면 val은 2k가 되고, 이후 while문 안의 2*val <= N이 거짓이 되어 탈출한다. 따라서 N이 2k 이상 2k+1 미만이라고 할 때 시간복잡도가 O(k)인데 k는 결국 log이니 O(logN)이 된다.
🖐️공간복잡도
코테에서 신경 써야하는 복잡도는 대체로 시간 복잡도를 의미한다.
공간복잡도와 관련하여서는 메모리 제한이 있을 경우가 있다.
> 512MB = 1.2억개의 int
메모리 제한이 512MB일 때 int 변수를 약 1.2억개 선언할 수 있다. 이 부분은 기억하면 좋다.
🖐️정수 자료형
정수 자료형과 각각 표현할 수 있는 수의 최댓값은 다음과 같다.
short(2byte) ---------> 215-1(=32767)
int(4byte) ------------> 231-1(=2.1*109) (대략 21억)
long long(8byte) ----> 263-1(=9.2*1018)
이 범위를 넘어서는 수를 저장하게 되면 integer overflow가 발생한다. integer overflow는 int의 자료형 범위를 까먹어 자주 발생할 수 있다. 이를 해결하고자 전부 다 long long 형으로 선언하는 방법도 있다. (좋은 습관은 아니지만..?)
unsigned long long 범위를 넘어서는 수를 저장하길 요구하는 문제를 만나면 string으로 선언해야한다. 그런 문제가 굳이굳이 나온다면 c++로 구현하는 건 너무 어려우니 파이썬으로 하는 게 낫다고 함..
🖐️실수 자료형
(1) 실수 자료형은 double을 써야 한다!
실수 자료형은 float(4byte), double(8byte) 이렇게 2가지가 있는데 실수의 특성상 실수의 저장/연산 과정에서 오차가 생길 수 밖에 없다. 그러니 실수 자료형이 필요할 때는 double을 써야한다.
float은 유효숫자가 6자리인데 반해 double은 유효숫자가 15자리이다. 이것은 double이 상대오차 10-15까지 안전하다는 것을 의미한다. float이 메모리를 적게 쓰긴 하지만 어찌됐든 실수가 필요할 때는 무조건 double을 쓸 것!
예를 들어 문제에서 '절대/상대 오차는 10-6까지 허용한다.'고 제시되면 이것은 실수 자료형 문제이므로 double을 쓰면 된다. 이것은 실수 자료형은 필연적으로 오차가 있으니까 제시되는 단서이다. 따로 이렇게 제시되지 않으면 열에 아홉은 정수형으로 해결가능한 문제이다.
(2) double에 long long 범위의 정수를 담으면 안된다!
double은 유효숫자가 15자리인데 long long은 최대 19자리니까 안된다. int는 최대 21억이므로 double에 담아도 오차가 생기지 않는다..
(3) 실수를 비교할 때 등호를 사용하면 안된다!
오차 때문에 실수가 같은지를 확인하고 싶을 땐 둘의 차이가 아주 작은 값대략 10-12(=1e-12) 이하면 동일하다고 처리하는 게 안전..
