[내일배움캠프_spring] 2-1주차_알고리즘(3-9강)

하루치 넘게 밀려서 걱정했는데 오늘 많이 들을 수 있었다. 오늘은 원격 강의가 11시, 2시에 있었어서 강의만 듣는 것보다 시간이 더 빨리가는 날이었다. 그래도 원격강의가 더 재밌다. 금요일이라 나머지 밀린 강의는 주말에 들을 수 있어서 다행이다. 주말코딩은 필수!!

---

 

**3-3.정렬(2)
선택정렬 : 선택해서 정렬한다!
input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)

    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i + j] < array[min_index]:
             min_index = i + j
        array[i], array[min_index] = array[min_index],array[i]
    # 이 부분을 채워보세요!
    return


selection_sort(input)
print(input)


삽입정렬 : 선택정렬이 최솟값을 '선택'하는 것이었다면, 삽입정렬은 전체에서 하나씩 올바른 위치에 '삽입'하는 방식
--->선택정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입정렬은 필요할 땨만 위치ㅡㄹㄹ 변경하므로 더 효율적인 방식

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    # 이 부분을 채워보세요!
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            print(i-j)
    return


insertion_sort(input)
print(input)


**3-4.정렬(3)
병합정렬 : 정렬 된 두개 이상의 배열들을 합칠 때 함친 배열이 정렬 되어 있어야 함
array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    array_c = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index +=1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1
    if array1_index == len(array1):
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1
    if array2_index == len(array2):
        while array1_index < len(array1):
            array_c.append(array2[array1_index])
            array1_index += 1

    # 이 부분을 채워보세요!
    return array_c


print(merge(array_a, array_b)

3-5.스택
last in- first out (ex. 되돌리기 기능(ctrl z))
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head
        # 어떻게 하면 될까요?


    # pop 기능 구현
    def pop(self):   #head값 없애기
        if self.is_empty():
            return  "Stack is Empty"
        delete_head =self.head
        self.head = self.head.next
        # 어떻게 하면 될까요?
        return delete_head

    def peek(self):# 가장 꼭대기를 반환
        # 어떻게 하면 될까요?
        if self.is_empty():
            return "Stack is Empty"
        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        # 어떻게 하면 될까요?
        return self.head is None

stack = Stack()
stack.push(3)
print(stack.peek())
stack.push(4)
print(stack.peek())
print(stack.pop().data)
print(stack.peek())
print(stack.is_empty())
print(stack.pop().data)
print(stack.is_empty())

스택을 사용해 보기 위해 탑 풀기

*****원격 강의 CPU
컴퓨터의 특성을 이해하자!
싱글코어 ->멀티코어
 bcs)싱글코어로는 발열 때문에 한계가 있음(코어의 성능 향상에 본질적인 문제)
     -> multiple하게 해결하자!
멀티코어 :멀티하게 state(register)를 가짐

register-업무별로 general purpose(범용)/special purpose(특수용)
 
2)cpu생김새 3)cpu 프로그램 통신방법 4)명령어 수행 방법


3-6.큐
:한쪽 끝으로 자료를 넣고 반대쪽에서는 자료를 뺄 수 있는 선형구조