코딜리티 pdf 번역 리뷰

나의 무궁무진한 슈퍼 블로거꿈을 위해, 코딜리티pdf를 한국어로 번역해보자. 떡상할수 있어

---

3.TimeComplexity

3.1. Comparison of different time complexities

3.2. Time limit

온라인 시험의 시간 제한은 보통 1초에서 10초까지입니다. 그러므로 우리는 시간 복잡성을 추측할 수 있습니다.(슈퍼 갓뎀 중요)

• n <= 1 000 000에서  예상 시간복잡도는  O(n) or O(n log n),

• n <= 10 000에서  예상 시간복잡도는 O(n2),

• n <= 500에서  예상 시간복잡도는 O(n3)

 

3.3. Space complexity

time limit 가 좀더 strict 하게 적용 되고 공간 복잡도는 유연하게 제공됨.

---

4.Counting elements

연속적인 수 a0, a1, a2.... an-1 은 다양한 방식으로 저장할 수 있다.

가장 전통적인 방법은  배열 A 에 고대로  박는 것이다.

A[0] = a0, A[1] = a1, A[2] = a2, .. A[n-1] = n-1

 

다른 방식으로는 우리는 counter 배열을 만들수도 있다.

각각의 수는 배열 A 에  각각의 인덱싱 값에 해당하는 값으로 카운팅 된다.( 그림을 집중하면 이해간다.))

 

우리는 요소를 바로 셀에 넣는 것이아니라, 우리는 단순히  발생을 카운트 했다. 

모든 요소가 {0, 1, . . . . m} 집합에 있다는 것을 알게 되면, 카운트에 사용되는 배열은 m + 1 사이즈여야 한다.

# 4.1 Counting Elements - O(n+m)
def counting(A, m):
	n  = len(A)
    count = [0] * (m+1)
    for k in range(n):
		count[A[k]]+=1
    return count

생각해야할 점은, 값 메모리가 한정되어있다는 점을 생각해야한다.(우리는 10^9 이상의 정수를 쓰면 안된다.)

 

음수를 세는 것도 두 가지 방법으로 가능하다. 

1. 음수 없애는 큰수를  배열에 더하던가

2. 음수를 위한 배열을 따로 생성한다.

 

4.1. Exercise

def slow_solution(A, B, m):
    n = len(A)
    sum_a = sum(A)
    sum_b = sum(B)
    for i in range(n):
        for j in range(n):
            change = B[j] - A[i]
            sum_a += change
            sum_b -= change
            if sum_a == sum_b:
                print(sum_a)
                return True
            sum_a -= change
            sum_b += change
    return False

# 내 깨달음. 쓸데 없으면 리스트 말고 딕셔너리 이득

내 풀이 -  코딜리티가 collections 를 허용하는지 아직 모르겠음.

import collections
def solution(A, B, m): # m 은 max 수
    a = collections.Counter(A)
    b = collections.Counter(B)
    sum_a = sum(A)
    sum_b = sum(B)
    if sum_a == sum_b:
        return True
    
    else:
        diff = sum_a-sum_b
    for i in a:
        if i-diff in B:
            return True
        elif diff-i in B:
            return True
        
        
        
solution(A, B, 34)

 

def fast_solution(A,B,m):
	n = len(A)
    sum_a = sum(A)
    sum_b = sum(B)
    d = sum_b  - sum_a
    if d%2 ==1: # 빼면 더해줘야해서  무조건 차이가 짝수여야함
    	return False
    d //=2
    count = counting(A,m)
    for i in range(n):
    	if B[i] -d and B[i] -d <=m and count[B[i] -d] >0:
        	return True
    return False

5.Prefix sums

여기 간단하지만 미친 속도를 자랑하는 부분 배열의 연속 요소들의 합 계산 테크닉이있다.

There is a simple yet powerful technique that allows for the fast calculation of sums of
elements in given slice (contiguous segments of array). 

우리는 이게 O(n) 복잡도일 것이라고 계산할 수 있다.

def prefix_sums(A):
	
    n = len(A)
    P = [0] *(n+1)
    for k in range(1, n+1):
    	P[k] =P[k-1] + A[k-1]
    return P

마찬가지로 k 마지막 값의 합계인 접미사 합계를 계산할 수 있다. prefix (or suffix) sums 을 사용하는 것은 우리에게 배열의 부분합을 더 빨리 계산하게 돕는다. 예를 들어,  배열 A의 A[x:y+1]의 합을 구한다 생각하자.( ax + ax+1  + ax+2 + ax+3 + ax+4 +ax+5 + ax+6 + ... + ay-1 + ay

 

 

이게 진짜 심각하게 구하면 O(n*m) 으로 계산할 수 있는데 굳이 왜! 라는 것이지.

쌈빡한 방법으로는 O(1)  로 total 을 구할 수 있다.

이러한 방식으로, total 시간 복잡도는 O(n+m) 이다.

# 5.2 Total of One Slice  => O(1)
def count_total(P,x,y):
	return P[y+1] - P[x]

5.1. Exercise

def mushroom(A,k,m):
	n = len(A)
    result = 0
    pref = prefix_sums(A)
    for p in range(min(m,k) +1):
    	left_pos = k-p
        right_pos = min(n-1, max(k, k+m-2*p))
        result  = max(result, count_total(pref, left_pos, right_pos))
    for p in range(min(m+1, n-k)):
    	right_pos = k+p
        left_pos = max(0,min(k,k-(m-2*p)))
        result = max(result, count_total(pref, left_pos, right_pos))
   	return result

밑에 문제 아직 이해 안함.. 집 가고 싶다아아아