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

해당 포스팅은 바킹독님의 바킹독의 실전 알고리즘 에 뿌리를 두고 있으며
사진 및 자료는 바킹독님의 블로그에서 가져왔습니다.
개인적인 복습 및 정리를 위한 용도로만 사용됩니다.

시간, 공간 복잡도

해당 주어진 문제를 생각해보자.
시간 제한이 1초인데, 컴퓨터는 1초에 대략 3-5억개의 연산을 처리할 수 있다.
물론 어떤 연산인지에 따라 그 차이는 있을 수 있겠지만, 대략 그 쯤이다.
근데 3-5억개를 처리한다 해 봤자 잘 와닿지는 않는다.

주어진 func1에 대해 최대 몇 번의 연산이 필요한지 생각해보자.

먼저 int cnt = 0에서 1번의 연산과 for문에서 int i = 0에서 1번의 연산 (2)
i < n 과 arr[i] % 5 연산한 후 그 결과값을 == 0인지를 검사하는 연산 (3n)
i++를 해 주는 연산과 (n)
최대 연산이므로 모든 경우에서 조건문이 참이라 cnt++을 진행하는 연산 (n)
그리고 마지막으로 cnt를 return하는 연산 (1)

이므로 해당 값들을 모두 더하면 최대 5n+3의 연산이 필요하다는 걸 알 수 있다.

따라서 이 func1은 5n+3 < 3~5억을 만족하는 n에 대해서
대충 1초 안에 돌아간다고 생각할 수 있는 것이다.

그리고 이렇게 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 시간 복잡도라고 한다.

다음은 빅오 표기법인데, 이는 시간복잡도에서 가장 큰 대표항만을 남겨서 나타내는 방법이다.
예를 들어 시간복잡도가 5N + 3으로 나타내진다면, N이 커지면 커질수록 가장 큰 대표항인 5N의 영향만 커지므로 3을 지워 5N만 남기는 식이다.

다음은 시간 복잡도를 그래프로 나타낸 것이다.
참고로 12!이 거의 5억이라서 11!까지는 dfs 종류 문제의 1초 시간제한을 통과할 수 있는 것처럼 보인다.
라고 생각을 했는데 바로 다음 슬라이드에 해당 부분을 정리한 표가 등장했다.

물론 절대적인 기준은 아니지만, 대충 이 정도라고 생각하면 된다.
따라서 문제를 구현하기 전에 구현법의 빅 오를 생각해서 이렇게 구현하면 시간 복잡도에 걸리지 않는지 생각해봐야 한다.
아니 근데 그러면 구현법의 빅 오는 대체 어떻게 구하는데? 라는 분들을 위한 예제 타임이다.

int func1(int N) {
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    return sum;
}

뭐 이런 식으로 짤 수 있을 테고, 입력 N에 대해서 i가 1부터 N까지 돌아가면서
i%3 == 0과 i%5 == 0의 연산을 진행하니
정확한 시간복잡도는 몰라도 빅 오가 O(N)이란 건 쉽게 알 수 있다.

int func2(int arr[], int N) {
	int flag = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (arr[i] + arr[j] == 100) {
				flag = 1;
				break;
			}
		}
	}
	return flag;
}

이런 식으로 짤 수 있을 테고, N에 대한 2중 for문이니 빅 오가 O(N^2)일 것이다.
정확한 시간 복잡도는 1 ~ N-1까지의 합을 구하면 된다.

사실 O(N) 풀이가 존재한다는데,
그걸 아는 사람이라면 지금 이 강의를 듣고 있지 않을 것이다. 라고 생각한다

int func3(int N) {
	for (int i = 1; i <= sqrt(N); i++) {
		if (i * i == N) {
			return 1;
		}
	}
	return 0;
}

뭐 대충 이런 식으로 짤 수 있을 것이다.
그리고 이건 i가 1부터 루트 N까지 진행되니 시간복잡도는 O(루트N)이 될 것이다.

int func4(int N) {
	int r = 1;
	for (int i = 2; i <= N; i *= 2) {
		r = i;
	}
	return r;
}

이런 식으로 짜봤는데 모범답안처럼 while문이 더 나은거같기도 하다.
시간복잡도는 당연히 지수 관련 문제니까 O(lg N)으로 생각할 수 있다.
여기까지가 시간복잡도 관련 예제였고, 다음은 공간복잡도 설명이다.

근데 솔직히 공간복잡도의 경우 발목잡힌적이 음...가끔 DP 풀 때? 말곤 없었던 것 같다.
크게 신경 말고 512MB가 int가 4byte니까 1억개쯤 쓸 수 있다는 개념정도만 있으면 된다고 한다.

정수 자료형

대강 이미 아는 얘기라서 간단하게만 정리한다.
보는 것처럼 signed에서는 최상위 비트가 1이면 -로 적용된다는 그런 뜻이다.

컴퓨터는 이런 시스템으로 정수를 표현하기 때문에 다음 그림같이 오버플로우가 발생하는 것이다.

그러므로 항상 정수 자료형을 다룰 때는 값의 범위를 확인하여 오버플로우를 주의하자.

실수 자료형

정수와 달리 실수는 다음 그림같은 방식으로 나타낸다.

자세한 이야기는 컴퓨터구조나 그런 쪽을 찾아보고... 어쨌던 지수부와 실수부를 통해 나타낸다.
당연히 이런 식으로 담으니만큼 0.1과 같은 친구들을 표현할 때 0.1이 담기는 것이 아니라 0.1에 엄청나게 가까운 무언가가 담긴다.
따라서 다음과 실수 표현에서 같은 오차가 발생한다.

또 당연히 실수와 정수를 표현하는 방식이 다르니만큼 함수로 실수->정수로 옮기면 곤란한다.
왜냐하면 double의 경우 위에서도 본 것처럼 유효숫자가 15자리인데 long long은 최대 19자리이므로 오차가 발생할 수 있기 때문이다.
double -> int의 경우는 문제가 없다고 한다.

그리고 위에서도 보았듯 실수 비교에서는 등호를 사용하면 안되고, 오차 내에서의 비교를 진행해야 한다.