출처:바킹독의 실전 알고리즘
0x00 시간, 공간 복잡도
int func(int arr[], int n) {
int cnt = 0; // cnt = 0에서 1번
for (int i = 0; i < n; i++) // i = 0에서 1번 // i < n에서 1번, i++ 1번
if(arr[i] % 5 == 0) cnt++; // % 5 에서 한 번, == 0에서 한번 // cnt에서 한 번
return cnt; // cnt 반환 연산 1번
}※컴퓨터는 1초에 대략 3-5억개 연산 처리
연산 회수 = 1 + 1 + n x ( 2 + 2 + 1 ) + 1 = 5n + 3
※n이 10억일 경우 50억번의 연산이 필요하니 1초안에 다 돌 수 없음
5n + 3 -> ★n에 비례한다.★
Q.
N명의 사람. 이름이 '가나다'인 사람을 찾음. 묻고답하는데 1초가 걸린다면 얼마만큼의 시간?
A.
최악 N초, 최선 1초, 평균 N/2초 -> 걸리는 시간은 N에 비례
Q.
N명의 사람. 이름이 '가나다'인 사람을 찾음. 사람들은 이름 순으로 서있음. 묻고답하는데 1초가 걸린다면 얼마만큼의 시간?
A.
업다운 게임하듯 중간 사람에게 계속 물어봄(계속 '반'으로 범위를 좁힘). 최악 lgN초, 최선 1초, 평균 lgN초( (1-1/N)lgN ->1/N은 커질수록 0에 가까워짐) -> 걸리는 시간은 lgN에 비례
(log의 밑이 2인 경우이므로 계속 절반)
시간 복잡도(Time Complexity)
입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
빅오표기법(Big-O Notation)
주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
O(N): '5N' + 3, '2N' + 10lgN, '10N'
O(N^2): 'N^2' + 2N + 4, '6N^2' + 20N + 10lgN
O(NlgN): 'NlgN' + 30N + 10, '5NlgN' + 6
O(1): 5, 16, 36 // 값이 상수
O(lgN)은 로그 시간
O(N)은 선형 시간
O(NlgN), O(N^2) 은 다항 시간
O(2^n)은 지수시간 // N이 25이하 정도로 굉장히 작은 경우만 시간 제한 통과
O(N!)은 N 팩토리알 // N이 11이하 정도로 굉장히 작은 경우만 시간 제한 통과
표를 통해 대략적인 느낌만 가져가자
Q.
N이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 10만 이하의 자연수이다.
func1(16) = 60,
func1(34567) = 278812814,
func1(27639) = 178254968
A.
int func1(int N) {
int sum = 0;
for( int i = 1; i <= N; i++) { // 시간복잡도 O(N)
if( (i % 3 == 0) || (i % 5 == 0) )
sum += i;
}
return sum;
}Q.
주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[]. int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
func2({1, 52, 48}, 3) = 1,
func2({50, 42}, 2) = 0,
func2({4 ,13, 63, 87}, 4) = 1
A.
int func2(int arr[], int N) {
for(int i = 0, i < N - 1, i++) { // N으로 놔도 무방
for( int j = i + 1; j < N; j++) // 시간복잡도 O(N^2)
if( arr[i] + arr[j] == 100 )
return 1;
}
return 0
}Q.
N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.
func3(9) = 1,
func3(693953651) = 0,
func3(756580036) = 1
A.
int func3(int N) {
for(int i = 1; i <= N ; i++) // 시간복잡도 O(루트N)
if( i * i == N)
return 1;
return 0;
}Q.
N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.
func4(5) = 4,
func4(97615282) = 67108864,
func4(1024) = 1024
A.
//My solution
int func4(int N) {
int i = 0;
for ( i = 2, i <= N; i *= 2 ) ;
return i / 2;
}
//Bak's Solution
int func4(int N) {
int val = 1;
while (2 * val <= N) val *= 2; // val값 보존? // N 이 2^k이상 2^(k+1) 미만이라고 할 때 시간복잡도 O(k) = O(lgN) (k 는 lgN)
return val;공간 복잡도(Space Complexity)
입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
공간 복잡도는 이것하나만 기억해두자
※메모리 제한이 512MB = 1.2억개의 int
※참고
https://imdk.tistory.com/23
0x01 정수 자료형
signed의 경우는 2^7자리만 '-'
int의 자료형의 범위를 벗어나는 경우 long long 을 사용
func3은 a가 10^9일 때 여기서 10이 곱해지는 순간 int의 최대 범위를 넘어섬 -> a의 자료형을 long long or Line7 10 -> 10ll or (long long)10
0x02 실수 자료형
접기/펼치기 버튼
정수부는 그냥 정수 변환하는 거랑 똑같이, 소수부가 문제
정수부 변환의 정반대로 하면 된다. 즉 정수부에선 10진수를 2로 나눠가면서 1이나 0을 뽑았다면 소수부는 10진수에 2를 곱해가면서 1이나 0을 뽑아낸다. 그리고 정수부 변환할 때는 1이 나오면 종료했다면 여기서는 0이 나오면 종료하고, 결과를 밑에서부터가 아니라 위에서부터 읽어준다.
0.625를 이진수로 변환하는 예시를 보자.
0.625 * 2 = 1.25 -> 1을 빼내고 나머지 0.25
0.25 * 2 = 0.5 -> 0을 빼내고 나머지 0.5
0.5 * 2 = 1.0 -> 1을 빼내고 나머지 0
나머지 0이 나왔으니 변환을 종료하고 빼낸 숫자들을 위에서부터 읽어주면 된다. 즉 0.625 -> 0.101
1/3은 무한소수
과학적 표기법
IEEE-754 format(부동소수점수, sign exponent fraction)
실수 자료형은 double사용! // 유효숫자 15자리는 상대오차 10^-15까지 안전하다는 소리. 즉,원래 참값이 1이라고 할 때, 1-10^-15 에서 1+10^-15 사이의 값이 보장
실수 자료형은 필연적으로 오차가 있으니까, 실수 자료형이 필요한 문제는 문제에서 절대/상대 오차를 허용한다는 단서를 줌. 만약 이러한 표현이 없다면 열에 아홉은 실수를 안 쓰고 정수로 해결 가능
long long은 유효숫자 19자리 // double은 유효숫자 15자리
10^18 + 1과 10^18을 구분할 수 없고 같은 값으로 저장
double에 long long 범위의 정수를 담을 경우 오차가 섞인 값이 저장
int는 최대 21억이기 때문에 double에 담아도 오차 x
두 값의 차가 아주 작은 값. 대략 10^-12(1e-12) 이하면 동일하다고 처리를 하는 게 안전
'Programming > Problem Solving' 카테고리의 다른 글
| [코드업] 기초 100제(C) (0) | 2020.07.17 |
|---|
댓글