컴사파 - 5주차

5.1 정수형 난수 리스트의 정렬 및 경과시간 측정

(1) 중복되지 않는 정수형 (int) 난수를 지정된 개수 (예: 10,000 ~ 1,000,000) 만큼 생성하는 함수 genBigRandList(n)을 구현하라. 이 함수는 정수 n을 인수로 전달 받고, 리스트 L을 생성한 후, n개의 중복되지 않는 정수형 난수를 생성하여 리스트 L에 포함한 후, 이 를 반환한다.

(2) 주어진 리스트의 첫 부분 2줄 (한 줄에 10개씩)과 마지막 2줄을 출력하는 함수 printListSample(L, per_line, sample_lines)를 구현 하라.

(3) 주어진 리스트의 원소들을 오름차순으로 병합정렬 구조로 정렬하는 함수 mergeSort(L) 함수를 구현하라.

(4) 표준입력장치로 부터 100,000 이상 크기의 정수형 난수 개수를 입력 받은 후, genBigRandList() 함수를 사용하여 중복되지 않는 정 수형 난수 리스트를 생성하고, 이를 printListSample() 함수를 사용하여 출력하라. 이 정수형 난수 리스트를 mergeSort() 함수를 사 용하여 정렬하고, 정렬된 상태를 printListSample() 함수를 사용하여 출력하라.

(5) 정렬에서 걸린 시간을 time 모듈의 time() 메소드를 사용하여 측정하고, 출력하라.

## 22211975_homework5
"""
 Project: 22211975_homework5.1
 Author:
 Date of last update: 22.09.29
 Update list:
    -v1.0: 22.09.27
        - added genBigRandList, printListSample function
    -v1.1: 22.09.29
        - added merge, mergeSort function
    -v1.2: 22.10.04
        - printSampleList가 입력된 per_line, sample_lines 에 맞게 출력하는 기능을 추가함.
"""
import random, time

def genBigRandList(n):
    for i in range(size+1):
        BigRand = random.randint(0, size)
        while BigRand in list: 
            BigRand = random.randint(0, size)
        else: 
            list.append(BigRand)
    return list

def printListSample(L, per_line = 10, sample_lines = 2):
    last_list = size % 20 
    cnt = 0
    for i in range(per_line * sample_lines):
        if cnt == per_line * sample_lines:
            break
        else:
            cnt += 1
            print("{:7}".format(L[i]), end = ' ')
            if cnt % per_line == 0:
                print('')
    print('\n ---------------------------------------------------------------------------------- ')
    cnt = 0
    if size % 20 == 0:
        for i in range(size-(per_line * sample_lines), size):
            if cnt == per_line * sample_lines:
                break
            else:
                cnt += 1
                print("{:7}".format(L[i]), end = ' ')
                if cnt % per_line == 0:
                    print('')
    else:
        for i in range(size-last_list, size):
            if cnt == per_line * sample_lines:
                break
            else:
                cnt += 1
                print("{:7}".format(L[i]), end = ' ')
                if cnt % per_line == 0:
                    print('')

def mergeSort(merge_list):
    if len(merge_list) > 1:
        middle = len(merge_list) // 2
        L_left = merge_list[:middle]
        L_right = merge_list[middle:]

        mergeSort(L_left)
        mergeSort(L_right)

        i = 0
        j = 0
        k = 0

        while i < len(L_left) and j < len(L_right):
            if L_left[i] <= L_right[j]:
              merge_list[k] = L_left[i]
              i += 1 
            else:
                merge_list[k] = L_right[j]
                j += 1
            k += 1
        while i < len(L_left):
            merge_list[k] = L_left[i]
            i += 1
            k += 1
        while j < len(L_right):
            merge_list[k] = L_right[j]
            j += 1
            k += 1
    return merge_list
    
while True:
    list = []
    print("\nPerformance test of merge sorting algorithm")
    size = int(input("Input size of random list L (0 to quit) = "))
    if size == 0:
        break
    L = genBigRandList(size)

# testing MergeSorting
    print("\nBefore mergeSort of L :")
    printListSample(L, 10, 3)
    print('\n')
    t1 = time.time()
    sorted_L = mergeSort(L)
    t2 = time.time()
    print("After mergeSort of L :")
    printListSample(sorted_L, 10, 3)
    print('\n')
    time_elapsed = t2 - t1
    print("Merge sorting took {} seconds".format(time_elapsed))

---

5.2 터틀 그래픽 - drawPolygon()

 파이썬 터틀 그래픽 기능을 사용하여 지정된 위치에 지정된 크기 (한 변의 길이)의 다각형을 그리는 drawPolygon() 함수를 구현하 라. 이 함수에 전달되는 인수로는 터틀 객체, 다각형의 중심 위치 (x좌표, y좌표), 다각형의 꼭지점 수, 다각형 한 변의 길이가 주어 지도록 하라.

 응용 프로그램 부분에서는 다각형의 중심 좌표 (x, y), 꼭지점 수, 한 변의 길이를 입력 받고, 입력된 중심 위치에 붉은색 점 (dot)을 표시하고 좌표값을 출력하라.

 다각형의 각 꼭지점에 붉은색 점 (dot)을 표시하고, 각 꼭지점의 좌표값을 출력하라.

# 22211975_homework5
"""
 Project: 22211975_homework5.2
 Author:
 Date of last update: 22.09.26
 Update list:
     -v1.0: 22.09.26
         - added source code
""" 
import turtle, math
from math import pi
from turtle import *

def drawPolygon(t, center_x, center_y, line_length, num_vertices):
    vertices_angle = (360 / num_vertices)
    startPosX = center_x - line_length / 2
    startPosY = center_y + line_length * num_vertices / (2 * pi)
    line_width = 3
    turtle.color('blue')
    turtle.width(line_width)
    turtle.up()
    turtle.setpos(startPosX, startPosY)
    turtle.down()
    for n in range(num_vertices):
        turtle.forward(line_length)
        turtle.right(vertices_angle)
        write(pos()) # showing each position
        dot(10, 'red') # showing dot
    turtle.exitonclick()
t = turtle.Turtle()
turtle.ht()

center_x, center_y, num_vertices, line_length =\
map(int, input("input center_x, center_y, num_vertices, and line_length : ").split(' '))
center_pos = (center_x, center_y)
line_width = 3
t.up(); t.goto(center_pos); t.down()
t.dot(10, "red"); t.write(center_pos)

drawPolygon(t, center_x, center_y, line_length, num_vertices)

---

5.3 재귀함수, 동적 프로그래밍

 Fibonacci 수열을 신속하게 계산할 수 있도록 memo 기능을 포함하는 재귀함수 dynFibo(n)를 구성하고, 시작 (start), 끝 (end), 간격 (stride)의 정수를 입력 받은 후 해당 순서의 피보나치 수열을 출력하는 프로그램을 작성하라. 각 단계별 피보나치 수열 계산에서 이 미 메모에 포함된 피보나치 수열 값은 별도로 계산하지 않고 메모의 내용을 사용하며, 이전에 계산된 적이 없은 피보나치 수열 값은 재귀함수를 사용하여 계산한 후, 이를 메모에 기록하여 두고, 계산된 결과값을 반환하도록 하라. 이 프로그램에서는 dynFibo(n)에서 걸린 경과 시간을 time() 함수를 사용하여 측정한 후, 계산된 피보나치 수열과 함께 출력하도록 하라. start = 50, end = 100, stride = 5로 설정하여 실행 결과를 출력하라.

# 22211975_homework5
"""
 Project: 22211975_homework5.3
 Author:
 Date of last update: 22.09.28
 Update list:
     -v1.0: 22.09.28
         - added source code
""" 
import time

memories = [0, 1]

def dynFibo(n):
    if n >= len(memories):
        memories.append(dynFibo(n-1) + dynFibo(n-2))
    return memories[n]

start, stop, step = tuple(map(int, input("input start, stop, step of Fibo: ").split()))
for i in range(start, stop+1, step):
    t1 = time.time()
    fibo_n = dynFibo(i)
    t2 = time.time()
    total_time = t2 - t1
    print("dynFibo({:3d}) = {:25d}, took {:10.2f}[micro_sec]".format(i, fibo_n, total_time))

 

---

5.4 행렬의 출력, 연산 프로그램

(1) 행렬을 표현하는 2차원 리스트 1개를 행렬의 이름 (문자열)과 함께 전달받아 출력하는 함수 printMtrx(name, M)을 작성하라.

(2) 2차원 리스트 2개를 전달받아 행렬의 덧셈을 계산하여 결과를 반환하는 함수 addMtrx(A, B), 뺄셈을 계산하여 결과를 반환하는 함 수 subMtrx(A, B), 그리고 곱셈을 계산하여 결과를 반환하는 함수 mulMtrx(A, B)를 작성하라.

(3) 다음 기능 시험 프로그램을 사용하여 결과를 출력하라.

# 22211975_homework5
"""
 Project: 22211975_homework5.4
 Author:
 Date of last update: 22.09.28
 Update list:
    -v1.0: 22.09.28
        - added source code, added printMtrx function
    -v1.1: 22.09.30
        - added sumMtrx function, subMtrx function
""" 
def printMtrx(name, M):
    print(f"{name} = ")
    for y in range(len(M)):
        print("{}".format(M[y]))
        
def sumMtrx(M1, M2):
    sum_Mtrx = []
    for i in range(len(M1)):
        temp=[]
        for j in range(len(M1[i])):
            temp.append(M1[i][j]+M2[i][j])
        sum_Mtrx.append(temp)
    return sum_Mtrx

def subMtrx(M1, M2):
    sub_Mtrx = []
    for i in range(len(M1)):
        temp=[]
        for j in range(len(M1[i])):
        sub_Mtrx.append(temp) 
    return sub_Mtrx

def mulMtrx(M1, M2):
    mul_Mtrx = [[] for i in range(len(M1))]
    for i in range(len(M1)):
        temp = [0] * len(M2[0])
        for j in range(len(M1[0])):
            for k in range(len(M2[0])):
                temp[k] += M1[i][j] * M2[j][k] 
        mul_Mtrx[i] = temp
    return mul_Mtrx
# ----------------------------------------------------------------
def main():
    A = [[1,2,3,4], [5,6,7,8], [9,10,0,1]]
    B = [[1,0,0,0], [0,1,0,0], [0,0,1,1]]
    C = [[1,0,0], [0,1,0], [0,0,1], [0,0,0]]

    printMtrx("A", A)
    printMtrx("B", B)
    printMtrx("C", C)

    D = sumMtrx(A, B)
    printMtrx("A + B", D)
    E = subMtrx(A, B)
    printMtrx("A - B", E)
    F = mulMtrx(A, C)
    printMtrx("A * C", F)

if __name__ == "__main__":
    main()

작성중 22.9.28 ~

22.9.30 작성완