뭐든지 다 알아보자

외부정렬

1> 외부 정렬은 데이터의 크기가 주기억장치의 용량보다 클 경우에 디스크 등의 외부 보조기억장치에 데이터의 대부분을 저장

==> 병합 정렬이 대표적

2> 보조기억장치에 입력을 저장 상태에서 수행되는 외부 정렬 ==> 입력을 분할해 주기억장치에서 수용할 수 있는 만큼의 데이터에 대해서만 내부 정렬 수행

EX) [31 , 20 ,22 ,30 ,35 ,23 ,25 ,32]

1> 분할: [31 ,20 ,22 ,30] // [35 , 23 ,25 ,32]

2>분할: [31,20] [22,30] ,[35,23] ,[25,32]

3> 분할:[31] , [20] , [22] , [30] , [35], [23] , [25] , [32]

4> 정복,결합(재귀호출) : [20 , 31] , [22, 30] , [23,35] , [25,32]

5> 정복,결합(재귀호출) : [20,22,30,31] , [23,25,32,35]

6> 정복,결합(재귀호출) : [20,22,23,25,30,31,32,35]

5. 퀵정렬

==> 데이터의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬

==> 1번째 데이터를 중심으로 중간값 설정 , 중간값을 적당한 곳에 위치시켜서 대상 자료를

부분적으로 나누어가는 방식

EX) [5 ,3 ,8 ,4 ,9 ,1 ,6 ,2 ,7]

㉠ 1회전

1. 5[pivot] 3 8 4 9 1 6 2 7[end]

2.start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 8 4 9 1 6 2 7[end]

3. 교환 ==> 5[start, pivot] 3 2 4 9 1 6 8 7[end]

4. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 2 4 9 1 6 8 7[end]

5. 교환 ==> 5[start, pivot] 3 2 4 6 1 9 8 7[end]

6. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 2 4 6 1 9 8 7[end]

7. 교환 ==> 5[start, pivot] 3 2 4 1 6 9 8 7[end]

8. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 2 4 1 6 9 8 7[end]

9. 큰값과 , 작은 값이 엇갈린다! ==> 작은값과 pivot 값 교환 ==> 1[start, pivot] 3 2 4 5 6 9 8 7[end]

==> 1 3 2 4 5 6 9 8 7

㉡ 2회전

1. 1[start, pivot] 3 2 4[end]  // 6[start, pivot] 9 8 7[end]

2. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기

==> 1 3[start, pivot] 2 4[end] ==> end부터 pivot 보다 작은 값 없다. pivot값 3으로 변경

==> 6[start, pivot] 9 8 7[end] ==> end부터 pivot 보다 작은 값 없다. pivot값 9로 변경

3. 교환

==>1 3[start, pivot] 2 4[end] ==> 큰값과 , 작은 값이 엇갈린다! ==> 작은값과 pivot 값 교환 ==> 1 2 3 4

==> 6 7[start, pivot] 8 9[end] ==> 큰값과 , 작은 값이 엇갈린다! ==> 작은값과 pivot 값 교환 ==>6 7 8 9

6. 힙정렬

1. 전이진 트리를 이용한 정렬 방식 ==> 이진 트리를 힙 정렬로 변환하는 방법

2. 전이진 트리형태로 노드의 배치가 상위에서 하위로 내려가면서 좌측에서 우측으로 순서적으로 배치하여 트리를 구성

3. 부모 노드가 자식 노드보다 큰 값(최대 힙) 이거나 작은 값(최소 힙) 이 되도록 구성

==> 최대힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 힙 ==> 루트 노드에 가장 큰 원소가 위치

==> 최소힙:  부모 노드의 키 값이 자식 노드의 키 값 보다 작은 힙 ==> 루트 노드에 가장 작은 원소가 위치

EX) [10 , 9 , 5 , 8 , 3 , 2 , 4 , 6 , 7 , 1]

1> 최대힙의 루트 노드를 배열의 마지막 값과 교환 , 가장 큰 값은 배열의 마지막에 저장

==>[1, 9 , 5 , 8 , 3 , 2 , 4 , 6 , 7 ,10]

2> 마지막 요소를 제외한 크기가 9인 힙을 다시 재구조화

==> [9 , 8 , 5 , 7 , 3 , 2 , 4 , 6 , 1 , 10]

3> 다시 최대힙의 루트 노드를 배열의 마지막 값과 교환

==> [1, 8 , 5 , 7 , 3, 2, 4 , 6 , 9 ,10]

4> 마지막 요소를 제외한 크기가 8인 힙을 다시 재구조화

==>[8, 7 , 5 , 6 , 3, 2, 4 ,1 , 9 ,10] 

5> 다시 최대힙의 루트 노드를 배열의 마지막 값과 교환

==>[1, 7 , 5 , 6 , 3, 2, 4 , 8  , 9 ,10] 

반복········> [ 1, 2, 3, 4, 5 , 6 , 7 , 8 , 9 , 10]

7. 2진 병합 정렬

==> 주어진 입력 파일을 크기가 2인 서브파일로 모두 나누어서 각 서브 파일들을 정렬

==> 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다.

EX) [7 , 3 , 6 , 4 , 1 , 8 , 9 , 2]

{7,3} {6,4} {1,8} {9,2}

==> {3,7} , {4,6} , {1,8} , {2,9}

==>{3,4,6,7} , {1,2,8,9}

==> {1,2,3,4,6,7,8,9} 

내부 정렬 기법

㉠ 삽입법 : 삽입 정렬 , 셀 정렬

㉡ 교환법 : 선택 정렬 , 버블 정렬 , 퀵 정렬

㉢ 선택법 : 힙 정렬

㉣ 분배법 : 기수 정렬

㉤ 병합법 : 2진 병합 정렬

외부 정렬 기법

==> 대용량의 데이터를 보조기억장치에서 몇 개의 서브 파일로 나누어 내부 정렬이후 주기억장치에서 각 서브 파일 병합

==> 속도는 느리지만 , 정렬하고자 하는 양이 많을 경우 효과적

㉠ 균등 병합 정렬

㉡ 다단계 병합 정렬

㉢ 계단식 병합 정렬

㉣ 교대식 병합 정렬

1) 내부정렬

1. 삽입정렬

==> 기준이 되는 키 값의 앞쪽 자료들의 값과 비교하여 자신의 위치를 찾아 삽입하여 정렬

==> 자료 일부가 정렬 되어있을 때 유리

==> 총 비교 횟수(N은 노드 수) : N*(N-1) / 4

EX) 15 , 11, 1 , 3, 8 삽입 정렬

1. 11 15 1 3 8

2. 1 11 15 3 8

3. 1 3 11 15 8 

4. 1 3 8 11 15

2. 셸 정렬

==> 매개변수 설정--> 데이터를 모아서 매개변수 간격만큼 파일 생성 --> 매개변수의 간격을 감소하면서 정렬

==> 주어진 데이터를 매객변수의 값으로 적절한 것으로 선택 --> 이를 점차 감소시키면서 셸 정렬 --> 매개변수가 1이 될때 종료

1> 나누는 간격 k

2> 간격 k의 초깃값 : (데이터 개수) / 2

3> 매 회전마다 k는 절반으로 나눈다. 항상 홀수가 되도록 값을 수정한다. (짝수인 경우 +1)

EX) 10 2 5 4 1 6 9 8 7 3 ==> 셸 정렬 이용

N = 10

K = N/2 = 5

1. [10 , 2 , 5 , 4 ,1] [6 ,9 ,8 ,7 ,3]

2. 1회전

[6 , 2 , 5 , 4 , 1 , 10 , 9 , 8 ,7 ,3]

3. K = 5/2 +1 = 3 , 2회전

[6 ,2 ,5] [4 ,1 ,10] [9 , 8, 7] [3]

==> [3 , 1 , 5 , 4 , 2 , 7 , 6 , 8 , 10 , 9]

4. K = 3/2 + 1 = 2 , 3회전

[3,1]

[5,4]

[2,7]

[6,8]

[10,9]

==>[2, 1 , 3 , 4 , 5 , 7 , 6,8 , 10, 9]

5. K = 2/2 = 1 , 4회전

[2, 1 , 3 , 4 , 5 , 7 , 6,8 , 10, 9]

==> 삽입정렬로 정렬

1)  1 ,2  , 3 , 4 , 5 , 7 , 6,8 , 10, 9

2)  1 ,2  , 3 , 4 , 5 , 6 , 7 ,8 , 10, 9

3)  1 ,2  , 3 , 4 , 5 , 7 , 6, 8 , 9, 10

셸 정렬에서 간격(K) 1일 때 삽입 정렬 ==> 배열의 처음 상태보다 어느 정도 정렬이 되어있으므로, 처음부터 삽입 정렬을 하는 것보다 속도가 빠르다.

3. 선택정렬

==> 정렬되지 않은 DATA들에 대해 가장 작은 DATA를 찾아 가장 앞의 DATA와 교환

==> 총 비교횟수 : N*(N-1) /2 

EX) 8 3 4 9 7

1. 3 8 4 9 7

2. 3 4 8 9 7

3. 3 4 7 8 9

4. 버블정렬

==> 인접한 데이터와 비교하여 위치가 맞지 않을 경우 서로 자리를 교환

==> 최대 수행 단계는 데이터 개수보다 1개 적은 횟수만큼 단계 수행

EX) 5 8 4 2 6 9 3

1. 5 4 8 2 6 9 3 ==> 2번째 요소부터 바로 뒤에꺼랑 2개씩 비교

2. 5 4 2 8 6 9 3

3. 5 4 2 6 8 9 3

4. 5 4 2 6 8 3 9

5. 4 5 2 6 8 3 9

6. 4 2 5 6 8 3 9

7. 4 2 5 6 3 8 9

8 . 2 4 5 6 3 8 9

9. 2 4 5 3 6 8 9

10. 2 4 3 5 6 8 9

11. 2 3 4 5 6 8 9

1. 트리(Tree)

Degree(차수) : 루트 노드로부터 퍼저나간 간선안의 노드수

Leaf : Node의 차수가 0인 Node or 자식 없는 Node

Root Node : 제일 최상위 노드

2.전위순회(Pre-order Traversal)

==> ROOT-좌측 - 우측

3. 중위순회(IN-order Traversal)

==>좌측 - Root - 우측

4.  후위순회(Post-order Traversal)

==> 좌측 - 우측 - ROOT

5. 중위식(Infix) ==> 후위식(Postfix)

EX-01)  A / B * (C + D) + E

==> (AB /) * ( CD +) + E

==> (AB /)(CD+*) + E

==> (AB /)(CD+*)(E+)

==> 곱셈, 나눗셈 먼저 뒤로 옮긴다.

EX-02) A = (B-C) * D +E

 ==> A = {(BC-)*D} + E

==> A= {(BC-D*) + E}

==> A = (BC-D*E+)

==> BC-D*E+A=

5. 후위식(Postfix) ==> 중위식(Infix)

ABC- /DEF+ * +

==> (ABC-/)(DEF+*+)

==>{A/ (BC-)}+(DEF+*)

==> {A/(B-C)} + {D* (EF+) }

==> A/(B-C)+D*(E+F)

https://www.acmicpc.net/problem/11660

VERSION 2.0

import sys

M = list(map(int , sys.stdin.readline().split(' ')))

A = [[0] * (M[0]+1)]
D = [[0] * (M[0]+1) for _ in range(M[0]+1)]

for i in range(M[0]):
    A_row = [0] + [int(x) for x in sys.stdin.readline().split()]
    A.append(A_row)

for i in range(1,M[0]+1):
    for j in range(1 , M[0]+1):

        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
print(D)
for _ in range(M[1]):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())

    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

    print(result)
#%%

※ 시간복잡도 오류

VERSION 1.0

import sys

M = list(map(int , sys.stdin.readline().split(' ')))

N = M[1]







prefix_2 = [ [0 for i in range(5)]]
for k in range(M[0]):
    a = 0
    prefix = [0]
    Nums = list(map(int , sys.stdin.readline().split(' ')))
    for i in range(M[0]):
        a += Nums[i]
        prefix.append(a)
    prefix_2.append(prefix)
# print(prefix_2)
# print(prefix_2[1][-1])
res = []
for i in range(N): #결과값 횟수
    RES = list(map(int , sys.stdin.readline().split(' ')))
    x_1 = RES[0]
    y_1 = RES[1]
    x_2 = RES[2]
    y_2 = RES[3]
    b = 0
    for k in range(x_1 , x_2+1):
        # print("prefix_2[{}][y_1] :{}".format(k, prefix_2[k][y_1]))
        # print("prefix_2[{}][y_2 - y_1] :{}".format(k , prefix_2[k][y_2 - y_1]))
        b += prefix_2[k][y_2] - prefix_2[k][y_1 - 1]

    print(b)


#%%

VER 2.0

import sys

T = list(map(int , sys.stdin.readline().rstrip().split(' ')))

M = T[0]

n = T[1]

N = list(map(int , sys.stdin.readline().rstrip().split(' ')))
res , res2 = [0] , []
prefix_sum = 0
for i in range(M):
    prefix_sum += N[i]
    res.append(prefix_sum)
for i in range(n):
    T  = list(map(int , sys.stdin.readline().rstrip().split(' ')))
    res2.append(res[T[1]] - res[T[0] -1])
for i in res2:
    print(i)

==> prefix 할 때 앞에 값 0으로 초기화해주어야 한다!

==> 2부터 4까지의 합 ==> 14 - 5 = 9

==> 1부터 4까지의 합 ==> 14 - 0  = 14 

VER 1.0

import sys

A = list(map(int , sys.stdin.readline().split(' '))) #N = 개수 , M= 합을 구해야 하는 횟수
B = list(map(int , sys.stdin.readline().split(' '))) #N개의 개수
res= []
for i in range(A[0]-1):
    #B= [5,4,3,2,1]
    B[i+1] += B[i] #B[1] += B[0] = [5,9,3,2,1]
    #B[2] += B[1] = [5,9,12,2,1]
    #B[3] += B[2] = [5,9,12,14,1]
    #B[4] += B[3] = [5,9,12,14,15]
B = [0] + B
#B = [0,5,9,12,14,15]
for i in range(A[1]):
    C = list(map(int, sys.stdin.readline().split(' ')))
    res.append(B[(C[1])] - B[(C[0]-1)])
for j in res:
    print(j)

누적 합(prefix sum) 알고리즘

구하려 하는 구간 i, j에 해당하는 두 원소의 차를 구해 그 구간의 합을 구하는 방식을 사용한다.

VERSION 3.0

import sys

n = int(sys.stdin.readline())
N = list(map( int , sys.stdin.readline().rstrip()))

print(sum(N))
#%%

VERSION 2.0

import sys

A = int(sys.stdin.readline())

while True:
    N = list(map(int, sys.stdin.readline().rstrip()))
    if len(N) == A:
        break
sum = 0
for i in N:
    sum+=i

print(sum)

VERSION 1.0

10번째 줄 Num = list(map(str,sys.stdin.readline().rstrip())) 

==> Num 객체에 List형태로 각각의 입력값 각자리수들을 분리하여 string형태로 저장한다. 단 rstrip()함수 때문에 제일 마지막 리스트의 요소값은 삭제시킨다.

즉 70을 입력시 ==> Num => ['7','0'] 형태로 저장되어진다.

by. rstrip() ==> 동기님의 도움

24. 실업률 9.5% , 청년 무작위 100명 선정

X ~ B(100 , 0.095)

X ~ N(100*0.095 , 100*0.095*(1-0.095))

1> 표본 선정된 청년들 중에서 평균 미취업자 수

9.5명

2> 미취업자 수의 분산과 표준편차

V(X) = 8.5975

s(x) = 2.93214

3> 미취업자가 정확히 8명일 근사확률

P(7.5<=X<=8.5) = P(X<=8.5) - P(X<=7.5) = P(Z<= (8.5-9.5)/  2.932) ) -  P(Z<= (7.5-9.5)/  2.932) ) = 0.1189

b = scipy.stats.norm.cdf( (8.5-9.5)/  2.932) -  scipy.stats.norm.cdf( (7.5-9.5)/  2.932)
b

3> 미취업자가 많아야 12명일 근사확률

P(X<=12) = P(X<=12.5) = P(Z<= (12.5-9.5)/  2.932) ) = 0.8468

b = scipy.stats.norm.cdf( (12.5-9.5)/  2.932)
b

25.근로자 2000명의 사망률 0.001, 적어도 4건에 대해 보상할 근사확률

==> X ~ B(2000 , 0.001)

E(X) = 2

1> 푸아송 근사(이산확률분포)

https://knowallworld.tistory.com/242

X ~ P(2) 

f_x = 0
m = 2
def fact(n):
    if n==0 or n==1:
        return 1
    else:
        return fact(n-1) * n

for x in range(0,4):
    f_x += (m ** x) * math.exp(-m) / fact(x)
print(1- f_x)

P(X>=4) = 1 - P(X<=3) = 0.1428

2> 정규 근사(연속확률분포)

b = 1- scipy.stats.norm.cdf( (3.5-2)/ math.sqrt(2*0.999))
b

P(X>=4) = P(X>=3.5) = 1- P(X<=3.5) = 1- P(Z<= (3.5-2)/ 루트(2*0.999) ) = 0.1443

26. T ~ t(n)에 대하여 분산= 1.25 , 자유도 n과 P(|T| <= 2.228) ==> T-분포

https://knowallworld.tistory.com/259

자유도(n) = 1.25*  (n-2) - n = 0

x = sympy.Symbol('x')

b = 1.25 * (x-2) - x

c = sympy.solve(b)
print(c)

자유도 n = 10

P(T<=2.228)*2 - 1 = 0.9499

#Z값 알고 있는건 cdf처리
dof = 10
b = scipy.stats.t(dof).cdf(2.228) *2 - 1
b

출처 :  [쉽게 배우는 생활속의 통계학]  [북스힐 , 이재원] 

※혼자 공부 정리용