SLENDER ANKLES's 개발블로그

빅 오 분석법 O(n)

자신이 푼 코드의 시간효율과 공간복잡도에 대해서도 명확히 말할 수 있는 개발자가 진정한 개발자라고 생각한다. 

그런 의미에서는 시간 효율과 같은 경우에 대충 for문으로 때려 잡고 있던(사실 대개 반복문이 시간분석의 핵심이긴하다) 

나에게는 간단하지만, 정확하게 분석 할 수 있는 능력이 필요하다고 생각한다.

빅 오 분석법

"입력 값에 따라 무엇을 n으로 놓을지 결정하고 나면 n개의 입력된 값을 몇 번이나 확인해봐야 하는지를 n의 식으로 표현" 

여기서 확인하다??라는 것이 무엇인지 애매하다. 

일반적으로 입력된 값에 상수를 더한다거나 새로운 입력 아이템을 만든다거나 입력 값을 삭제한다거나 비교한다던가 하는 것을 "확인" 이라고 표현 할 수 있겠다. 

하나의 간단한 코드를 보면서 빅 오 분석법을 이해해보고자 한다.

위의 코드는 주어진 배열에서 최대값을 찾는 코드이다. 여러 방법이 있겠지만 그 중에 위의 코드는

최대값을 찾는 변수를 할당해 놓고 모든 수와 한 번씩만 비교해서 가장 큰 값을 반환하는 코드이다.

자, 입력된 항목의 자료들이 한 번 씩만 비교하면 되므로 O(n)의 시간복잡도가 계산된다. 

명확히 말하면 맨 처음에 자료가 0개인지 아닌지를 판별하는데 1이 소모 되었고,

maxvalue를 첫번째 원소로 초기화하는데 1이 소모 되었으므로 

O(n + 2)라고 할 수 있다. 하지만 2라는 상수는 충분히 커진 수에서는 별로 의미가 없다.

우리는 위의 코드처럼 고작 6개의 수가 얼마나 시간이 걸리는지를 계산할려고 시간복잡도를 구하는 것이 아니기

때문이다. 우리는 수백, 수억개의 숫자들 중에서 최대값을 찾는데 걸리는 시간에 대한 복잡도를 구하는 것이다. 

예를 들어 O(10000000000000 + 2)에서 2는 의미가 있나? 없다고 판단해도 된다.

그래서 시간 복잡도는 O(n)으로 계산되는 것이다. 

이중 for문에서도 비슷하게 계산 가능하다. 

상수 시간이 걸리는 부분은 과감히 생략되고 실질적으로 n개의 자료들이 이중 for문의 연산이 수행되면

O(n^2)이 된다. (블로그에 제곱 표기가 좋지 않아 이렇게 표현한다)

* 시간 복잡도를 구하는 방법 정리

1. 빅-오(Big-Oh)표기법

최악의 경우를 복잡도를 구하는 경우를 말한다. "최악의 경우 시간 복잡도는 O(n)이다" 이런식

2. 빅-오메가(Big-Omega) 표기법

빅 오와 반대되는 개념. 최선의 경우의 복잡도를 구하는 것을 말한다. "최선의 경우 Ω(n)이다."이런식

3. 세타(Theta) 표기법

빅오와 빅오메가의 중간인 평균적인 복잡도를 구하는 경우를 말한다.

조합알고리즘

nCr 을 구현해야 됐던 적이 있었나?

경험적으로 재귀적으로 수행했을 때도 충분히 답이 나오는 문제만 풀어서 그런지 없었다. 

1010 다리 놓기 라는 문제를 통해 

그냥 재귀탐색과 DP를 통한 메모이제이션 탐색의 엄청난 시간 차이를 경험했다. 

조합알고리즘에 대해서 간단히 설명하자면

n개 중에서 r개를 뽑는 경우의 수를 nCr 이라고 표현하고 

수학에서는 (n - r)! / r!     또는      n! / r! * (n-r)!으로 계산 해주지 않았나?

=> 6C3 => 6 * 5 * 4 / 3 * 2 * 1 이었다.

하지만 수학이 아닌 컴퓨터에서는 

이렇게 팩토리얼 개념을 적용시켜주면 자칫 메모리를 엄청나게 

쓰다가 스택 오버플로우가 날 수 있다.

n이 충분히 커지게 되면 n!은 기하급수적으로 증가하게 된다. 

그래서 식을 다음과 같이 바꾸어주게 된다. 

nCr = (n - r + 1) / r * nCr-1

nC0 = 1(r ==0일때, basecase)

그렇다면 이 것을 cache를 써서 다음과 같이 표현해주면 완벽하다.

2 * 2 배열에 1,2를 채우는 경우의 수하기.

2 * 2 * 2 * 2 => 16가지의 경우의 수가 나와야 한다.

그런데 내가 코딩한 거에는 96가지가 나왔다. 무엇인가 잘 못 코딩해준것이었다. 

항상 2차원 배열에 대한 경우의 수 구하는 문제를 만나면 어디선가 루프를 잘 못 돌고 

그랬었는데, 확실히 내가 잘 못된 코드를 통해 풀고 있었다는 것을 깨달았다. 

2차원 루프에서 만약에 조건을 만나면 재귀 탐색 시작하고 무조건 빠져나와야 한다는 것이 중요했다.

반복하는데 귀신인 컴퓨터에 적당한 방법이다. 가능한 경우를 모두 검사(exhaustive search)하는 무식한(?)방법이다.

답 내는 것이 문제가 아니라 얼마 만큼의 빠른 시간에 작업을 끝낼수 있는 가를 고민해야 되는 파트.

가능성이 없는 것은 미리 잘라버리는 것이 관건이다. 예를 들어, 3 번의 시합에서 2 번 우승하면 이기는 게임에서 미리 2 번 이기면 나머지 한 번은 할 필요가 없다. 이런 가능성을 생각해서 미리 많이 잘라버리면 그 만 큼의 실행시간이 빨라진다.

가능한 경우를 모두 검사하는 방법에는 보통 두 가지 유형의 문제로 나뉠수가 있다.

• 부분집합형 백트래킹
• 팩토리얼형 백트래킹

예를 들어 , 주머니 속에 7 개의 공이 있고 , 각 공에는 번호가 부여되어 있다.

부분집합형

주머니에서 몇 개의 공을 꺼내어 합이 13 이 공들을 찾는 경우에는 2^7 가지의 부분집합을 모두 검사해야 한다.

한 개 뽑는 경우

• 6
• 2
• 9
• ..

두 개 뽑는 경우

• 6 , 2
• 6 , 9
• 6 , 8
• ...

세 개 뽑는 경우

• 6 , 2 , 9
• 6 , 2 , 8
• ...

...

7 개 모두 뽑는 경우

• 6, 2, 9 , 8 , 3 , 4 , 7

팩토리얼 형

7 개의 공을 임의로 나열했을 때 인접한 수의 곱이 최대 인 경우는 어떤 경우인가를 알고자 할 때 7! 가지의 모든 경우를 생각해야 하므로 이는 팩토리얼 형 문제라고 생각할 수 있다.

• 6 2 9 8 3 4 7
• 6 2 9 8 3 7 4
• ...

(문제) sum of subset 

6 , 1 , 9 , 8 , 3 , 4 , 7

총 합은 38 , 합은 반은 19 이다.

이 수들을 적절히 뽑아 19 를 만들 수 있는 방법의 수를 구하는 문제.

부분 집합형 문제의 기본 틀

첫째 원소, 둘째 원소 2 개 있을 때 부분집합의 수는 4 개이다.

• 2 가지 모두 포함하는 경우 (o o)
• 첫 원소 포함 , 둘째 원소 포함하지 않는 경우 (o x)
• 첫 원소 포함하지 않고 , 둘째 원소 포함하는 경우(x o)
• 2 가지 모두 포함하지 않는 경우 (x x)

o 를 1 로 x 를 0 으로 놓으면 ,

• 1 , 1
• 1 , 0
• 0 , 1
• 0 , 0

원소의 수가 2 개 일 때

이를 구현하기 위해 배열(배열명을 include[] 라 하자)을 사용하여

원소의 수가 3 개일 때

(샘플 문제)수의 부분합 문제로 조금씩 실행 속도를 높여 보기로 하자. 문제는 전제 합의 반 50 이되는 원소를 골라내는 문제이다. 
주어지는 데이터는 40 20 30 10 (수의 부분합 풀이)

그 동안 난해했던 이러한 류의 코딩하는 방법을 조금은 터득한 것 같아 정리해둘려고 한다. 

1) 항상 몇 가지 나열된 원소(숫자)를 중복을 허락하지 않고 모든 경우의 수를 구해야 할 때, 

=> n!

2) 몇 가지 나열된 원소(숫자)로 만들 수 있는 모든 경우의 수 구하기

=> n * n * n * n * ......

위와 같은 수행과정이 필요할 때 재귀적으로 코딩하는 것이 만만치 않았다. 

단지 for문을 돌면서 수행 할 수도 있다.(완전 탐색의 원소의 개수를 완벽히 알 수 있을 때 말이다.)

하지만 그렇지 않을 때에는 난 감했던 적이 많았는데 다음과 같이 코딩해주면 된다. 

이 것은 지속적으로 반복기억해주어야 겠다.

3) m가지의 수들로 n자리 수를 중복을 허락하여 만드는 경우

m * m * m( ... n번)

동적 계획법(dp)는 가장 흔한 문제 유형 중 하나이고 메모이제이션은 굉장히 자주 구현하게 된다. 

따라서 한 가지 패턴을 정해두고 풀게 되면 확실한 풀이 방법을 알 수 있을 것 같다. 

1. 가장 먼저 basecase 처리

2. cache[]를 모두 -1로 초기화하고, -1이 아니면 cache[]의 값이 없는 것으로 간주.

3. ret(리턴 값)을 참조형(reference)으로 관리하여 실수를 줄임

4. memset을 이용한 초기화

- 우선 2를 제외한 모든 짝수들은 소수가 아니다라는 점

- 만약 N이 합성수라면 N = a * b형태이므로(a > 1 && b > 1), a와 b 둘 중 하나는 sqrt(N)보다 작거나 같음을 알 수 있다.

그러므로 N을 2부터 sqrt(N)까지 나눠보아 나누어지지 않으면 N은 소수가 된다. 

다음은 2부터 N까지 소수를 구하여 prime이라는 배열에 반영하는 코드의 핵심 함수이다.

gcd는 

예를 들어 

8, 28의 최대 공약수를 구해보면

3 = 28 / 8 ...4

2 = 8 / 4 ...0

AB/GCD = GCD*a*b;

결국 AB/GCD는 최소공배수가 된다

한 붓 그리기에 대한 공식을 명확히 알 필요가 있을 것 같아 정리해둘려고 한다. 

한 붓 그리기란 그래프의 어느 한 점에서 시작하여 모든 간선들을 한 번씩만 지나가는 

경우를 말한다. 

이 것에 대한 조건은 일단 두 가지로 나뉜다. 

1) 모든 정점이 가지는 간선이 다 짝수 개 일 때

2) 두 정점만 간선이 홀 수개를 가질 때 

이렇게 가능하다고 한다. 

한붓그리기의 경로를 뽑아내기 위해서는 dfs의 마지막 부분에 출력을 넣어주면 된다. 

뒤에서부터 출력하면 가능하다. 이 부분은 제대로 이해를 못 해서 직접 손으로 그려봐야겠다

특징

- 오일러 서킷

1) 모든 정점의 간선의 개수는 짝수여야 함(무향)

2) 들어오고 나가는 것이 있어야 됨(유향)

- 오일러 트레일

시작점과 끝점의 간선이 홀수개여야 함(무향)

(방향)

시작점 : 들어오는 간선이 나가는 것보다 하나 더 적어야 함

끝 점 : 들어오는 간선이 나가는 것보다 하나 많아야 한다.