[Algorithm] 코딩테스트 Cheat Sheet

1. 무한루프를 통해 테스트 케이스를 실행하는 경우

특정 조건이 일치하는 것을 찾는 문제에서, 테스트 케이스의 수가 정해지는 것이 아니라 무한루프를 통해서 확인한다면 Boolean 배열에 저장해 활용함으로써 시간 단축이 가능하다.

 

2.  소수 빠르게 구하기

소수인지 확인은 2 ~ (i ** 0.5) + 1 의 범위만 확인해도 된다.

 

3. 파이썬에서의 전역변수 처리

함수 외부에 있는 전역변수(입력 값)을 함수에서 사용하려면 global 키워드를 사용하면 된다.

 

4. 빠른 입출력함수

input(), print() 대신 sys.stdin.readline(), sys.stdout.write() 함수를 사용하는 것이 빠르다.

 

5. 다양한 기본 라이브러리 사용

collections(deque, Counter, ...), math, itertools, heapq, bisect 와 같은 라이브러리를 사용하면 코딩시간을 많이 단축할 수 있다. 심지어는 시간복잡도도 이게 더 빠름ㅎ;

 

6. 딕셔너리의 정렬

딕셔너리를 정렬하는 방법은 sorted() 내장함수를 사용하는 것이 편하다. 두 번째 인자인 key 값을 사용해 key를 사용해 정렬할지 value를 사용해 정렬할지 명시할 수 있다. 

 

7. 최소공배수/ 최소공약수

유클리드 호제법을 기억하는것이 베스트. 하지만 기억하기 귀찮다면 math 라이브러리의 gcd() 함수를 사용하자. 그리고 최소공약수는 (a * b) // math.gcd(a, b) 식을 통해 구할 수 있다. (유클리드 호제법)

 

8. Greedy 알고리즘 한줄요약

현재 상황에서 최적의 해를 찾아가는 방법. 즉, 현재 상황만 정확하게 고려하면 된다. 하지만 이를 위해서 사전에 정렬과 같은 전처리가 필요할 수 있다. (정렬해도 되는 경우엔!)

 

9. 동일한 나머지

하나의 수로 나눈 나머지가 같은 수는 등차수열을 이룬다. 어찌보면 당연한 것!

따라서 임의의 숫자 A, B, C 가 주어지고 동일한 나머지를 만들어내는 숫자 k를 찾아야 한다면 (B - A)와 (C - B)의 최대공약수를 찾고 그 수의 약수를 나열하면 된다.

 

10. 팩토리얼의 소인수

10! 의 소인수중에 2가 몇 개 있는지 알고싶다면 기본적으로 생각나는 방법은 10, 9, 8, ..., 2, 1 을 소인수분해 한 후 2의 개수를 세는 것이다. 하지만, 10 // 2 = 5, 5 // 2 = 2, 2 // 2 = 1, 1 // 2 = 0 의 값을 모두 더하면 간단하게 구할 수 있다. 원리는 모르겠네...

def div_number(k, n):
    count = 0
    while k != 0:
        k = k // n
        count += k
    return count

 

11. 특정 연산 후 뒤에나오는 0의 개수

뒤에 0이 나오기 위해서는 2 * 5의 연산이 필요하다. 따라서 연산에 들어가는 수들의 소인수들을 구하고 2와 5의 개수중에서 작은 값을 구하면 된다.

 

12. 경우의 수

A가 3개, B가 1개, C가 2개(각각 다르다) 일때 이를 선택하는 경우의 수는 기본적으로 3*1*2이다. 하지만, 안꺼내는 수까지 고려해야한다면 (3 + 1)(1 + 1)(2 + 1) 이된다. 마지막으로 모두 뽑지 않는 경우를 제외해야한다면 1을 빼주면 된다.

www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

13. Reverse의 시간복잡도 최소화

deque를 사용해 Reverse의 시간복잡도를 O(1)로 최소화할 수 있다. 실제로 뒤집는 것이 아니라 뒤집힌 것처럼 시작위치가 왼쪽인지 오른쪽인지 판단하면 된다.

left = True
for op in ops:
	if op == 'R':
		left = not left
	elif op == 'D':
		if not lst:
			isError = True
			break
		if left:
			lst.popleft()
		else:
			lst.pop()

 

14. 배열에서 앞의 값 제거하기

del lst[0] 은 배열의 값들을 앞으로 당겨야하기 때문에 시간이 오래걸린다. collections 라이브러리의 deque에서 popleft() 함수를 사용하면 빠르게 앞의 값을 제거할 수 있다.

 

15. 나머지 연산의 분배법칙

문제에서 결과 값이 너무 커질 것을 대비해 나머지 연산을 수행하는 경우가 종종 있다. 이 경우 나머지 연산의 분배법칙을 사용하면 연산과정의 속도와 메모리를 최소화할 수 있다.

(A + B) % M = ((A % M) + (B % M)) % M
(A * B) % M = ((A % M) * (B % M)) % M
(A - B) % M = ((A % M) - (B % M) + M) % M

위 연산에 대해서만 알고있고 다른 형태에서 함부로 하면 안된다. (예를 들어 분수형태)

 

16. 빠른 거듭제곱

우선 내장함수로 제공되는 pow를 사용하는 방법이 가장 편한 방법이다. 기본적으로 내장함수는 최적화가 잘되어있기 때문에 어지간하면 내장함수를 사용하는것이 좋다. 

pow(5, 2)  # 5의 2승
pow(5, 2, 1000000007)  # 5의 2승을 1000000007 로 나눈 나머지

직접 함수를 구현할 땐 분할정복 알고리즘을 사용하면된다.

def power(N, K):
	if K == 1:
    	return N
    
    half_power = power(N, K // 2)
    if K % 2 == 0:
    	return half_power * half_power
    else:
    	return half_power * half_power * N


m = 1000000007
def power2(N, K):
	if K == 1:
    	return N
    
    half_power = power2(N, K // 2)
    if K % 2 == 0:
    	return half_power * half_power % m
    else:
    	return half_power * half_pwoer * N % m

 

여기서 참고할만한 내용으로는 half_power를 미리 구해서 재귀를 2번이 아니라 한번만 호출한다는 것이다. power(N, K // 2) * power(N, K // 2 + 1) 와 같이 할 수 있지만 이렇게하면 시간적인 부분에서 2배이상의 손해를 보게 된다.

 

그리고 곱셈의 분배법칙이 있기 때문에 각각의 나머지를 미리 계산해 메모리를 최소화할 수 있다.

 

17. 페르마의 소정리

페르마의 소정리는 자세히 설명하기 보다 문제를 풀며 필요했던 케이스에 대해서만 설명해본다. 우선 위에 15번에서 나머지를 분배하는 방법에 대해서 말했는데, (A * B * C) % m 이 아니라 (A / (B * C)) % m 의 경우에는 위 분배식이 성립하지 않는다.

 

이를 해결하기 위해 페르마의 소정리를 사용해 B와 C의 역원을 구하게 된다. 예를 들면 조합문제가 있는데 nCk의 경우에는 (n!) / (n - k)! * k! 이고 이 결과를 m으로 나누는 식은 ((n!) / (n - k)! * k!) % m 즉, ((n!) * ((n - k)!)^-1 * (K!)^-1) % m이 된다. 그러면 (K!)^-1 와 같은 역원을 페르마의 소정리를 통해 어떻게 구하는지 살펴보자.

 

위는 기본적인 페르마의 소정리의 정의이다. 즉 p가 1000000007 이라고 했을 때 다음 식이 성립한다.

 

양 변을 a^-1으로 나누면 다음 식이 성립하는데, (K!)^-1 이 (K!)^1000000005 와 같다는 것을 알 수 있다. 물론 소수인 1000000007 로 나눴을때 나머지가!!

따라서 ((n!) * ((n - k)!)^-1 * (K!)^-1) % m 을 ((n! % m) * (((n - k)!)^-1 % m) * ((K!)^-1 % m)) % m 으로 고칠 수 있고 페르마의 소정리를 통해 최종적으로 ((n! % m) * (((n - k)!)^(m - 2) % m) * ((K!)^(m - 2) % m)) % m 로 고칠 수 있다.

 

18. 행렬곱셈

3중 포문을 통해 구할 수 있는데 코드를 기억하는게 효율적인듯..? 당연히 스스로 만들 수 있어야 한다. 단지 시간 단축의 목표를 위해서 기억하는 것 뿐!

def mul_matrix(matrixA, matrixB):
    global A_row, A_col, B_row, B_col

    result = [[0 for _ in range(B_col)] for _ in range(A_row)]
    for i in range(A_row):
        for j in range(B_col):
            for k in range(A_col):
                result[i][j] += matrixA[i][k] * matrixB[k][j]
    return result