22.11.11)알고리즘과 CS를배운 10일차

#오늘배운 것

CS(cpu)

1. cpu를 싱글>멀티로 변경한 점
2. CPU생김새
3. CPU < > 프로그래머 통신방법
4. 명령어 수행방법

cpu/memory/disk

cpu는 모든 장치를 관리한다. n개의 register로 이루어져있다.

코어 하나에 n개의 register가 있다. state도 n개를 가질 수 있게 됐다.

싱글 코어 > 멀티코어로 발전한 이유는 '무어의 법칙' : 1년마다 프로세스 성능이 2배씩 증가한다. 발열이 심하니까...

결론 : 코어의 성능 향상엔 본질적인 한계가 있으므로 멀티코어로 보완한 것이다.

그러므로 멀티한 state를 가진다 (state는 resiter들)

CPU구성 :

• ALU(산술/논리연산)
• CU(controlunit.뇌라고 생각하면 된다. os나 프로그램을 행동하면 그것을 cu가 받아 연산해 fatch한다.그리고 명령어를 해석하고 산술논리에 전달하면 프로그램에 메모리가 변경된다.)
• regeister :업무 별로 나뉜다( general - purpose (범용) /  special - purpose (특용) /pc레지스터 : 프로그램 카운터)명령어에는 한라인으로 들어간다.그 것을 관리하는것이 pc다.
• cache :캐시 코이런스(cache cogerence)

cpu와 프로그래머가 소통하는 방법 : 기계어 (binary 원툴) 어렵다 ! > 이것을 어셈블리어(cpu arch)코딩으로 했다가 또 어려워서 컴파일러를를 통해 통역하여 프로그래밍한다(C,C++,JAVA)

010101010 못쓰니까 어샘블리어 만들데 이것도 힘들어서 C언어같은 HIGH LEVEL 언어를 만들었다

ISA : 명령어 인스트럭션 셋 아티텍쳐 -명령어 집합

• CISC : Complex instruction set computer
• RICS : Reduced Instruction Set Computer

명령어 수행 : 코드의 하나하나(line)가 실행될 때 메모리,레지스터들이 변한다.그래서 원하는 결과를 출력한다.

수행절차디테일 : 모니터와 디스크에 영향을 끼친다. 명령어(fetch)를 cu가 실행.후에 opcode로 디코딩을 한다.

(RICS를 1사이클에 명령어를 수행할 수 있게 해준다.) 오퍼랜드(operand)는 즉시값(imm,register,memory) 

>execute 실행 >alu(산술논리) Write back

prefech를 하면 최적화(처리속도)가 좋아진다.컴퓨터 구조 : OS,DB,네트워크 - 에센셜컴파일러 : 프로그래밍 언어 - 어드벤스

[컴퓨터 구조]에 대해 더 자세히 알아보기..

 

알고리즘

이진탐색 : 반을 쪼개어 탐색한다.up&down게임을 생각하면 편하다. 이 게임에서 범위의 절반인 50을 시도하는 것.

0과1로 이뤄짐.

 

※숫자 내림 하는 방법

// 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있다.

이진탐색같이 중간을 기준으로 탐색할 때 정수로 나타낸다면 더 유리하다.

>>> print((4 + 5) / 2)
4.5
>>> print((4 + 5) // 2)
4

숫자찾기 예시 1차시도

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

#찾으면 되는 범위의 최소값 + 최대값 = 반의 값을 구한다.
def is_existing_target_number_binary(target, array):
    cur_min = 0
    cur_max = len(array) - 1
    cur_guess = (cur_min + cur_max) // 2
    
    while cur_min <= cur_max:
        if array[cur_guess] == target:
            return True
        #target이 더 크다는 뜻이면 위에있는 범위를 찾아야한다.
        #업이면 최소값을 현재시도값+1,다운이면 최대값을 현재시도값-1해야한다.
        elif array[cur_guess] < target:
            cur_min = cur_guess + 1
        else:
            cur_max = cur_guess - 1
        #while문을 다시 돌면 cur_guess를 다시 업데이트 해야한다.
        cur_guess(cur_max + cur_min) // 2
            
    return False

처음 변수명을 조금 변경하여 출력했을 때 

"TypeError: 'int' object is not callable"라는 에러가 출력되었다.
=알고보니 cur_guess에 =을 빼먹은 것이다..코드를 잘 보자..

최종

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

#찾으면 되는 범위의 최소값 + 최대값 = 반의 값을 구한다.
def is_existing_target_number_binary(target, array):
    cur_min = 0
    cur_max = len(array) - 1
    current_guess = (cur_min + cur_max) // 2
    
    while cur_min <= cur_max:
        if array[current_guess] == target:
            return True
        #target이 더 크다는 뜻이면 위에있는 범위를 찾아야한다.
        #업이면 최소값을 현재시도값+1,다운이면 최대값을 현재시도값-1해야한다.
        elif array[current_guess] < target:
            cur_min = current_guess + 1
        else:
            cur_max = current_guess - 1
        #while문을 다시 돌면 current_guess를 다시 업데이트 해야한다.
        current_guess = (cur_max + cur_min) // 2
            
    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

이진탐색했을경우

find_count = 0
    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)  # 3!
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2
 #3

총 숫자가 1~N 까지라고 한다면, 1번 탐색하면 반절이 줄어드니 N/2 개가 남습니다.
2번 탐색하면 반절이 줄어드니 N/4 = N/2^2 개가 남습니다.
3번 탐색하면 반절이 줄어드니 N/8 = N/2^3 개가 남습니다.
... k번 탐색하면 반절이 줄어드니 N/2^k 개가 남습니다. 이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다.
이걸 수식으로 표현하면, N/2^k = 1 입니다. 즉, k = \log_2{N} 횟수를 시도하면 정답을 찾을 수 있다.
결론적으로 이분탐색을 위해서는 시간 복잡도가 $(logN) 만큼 걸린다. 라고 말할 수 있습니다.

참고로 K는 미지수라고 한다.
분모와 분자를 바꾸고,지수를 밑의 수로 변경하면 된다.
log_2N이 아니라logN인 이유는 상수는 무시해도 되기 때문에 표기하기 쉽도록 logN 으로 부르기로 되있기때문이다.

 

순차탐색 : 하나하나씩 탐색하는 방법

def is_existing_target_number_sequential(target, array):
    find_count = 0
    for number in array:
        find_count += 1
        if target == number:
            print(find_count) # 14!
            return True
            
 #14
 #for문을 이용해 넘버를 하나씩 탐색하다보니 14번이 걸렸다.
 #O(N)만큼 걸릴수도있따.

 

재귀함수

자기 자신을 호출하는 함수.재귀 함수를 이용해서 간결하고 효율성 있는 코드를 작성할 수 있다.

밑의 함수의 경우 재귀함수를 사용해 해결한다.

finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]
#이진탐색으로 찾을시 원하지않는 답이 나온다.
#최소값과 최대값을 찾아야하는데 최소값 범위에 6이 들어가기 때문에 맞지 않는 결과가 나온것이다.
#리스트에서 타겟을 찾으려면 숫자를 정렬 후 찾아야한다.

재귀함수를 이용해 카운트다운

def count_down(number):
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)
#이경우 에러가 난다. 끝도 없이 반복해서
#그렇기 때문에 재귀함수는 반드시 빠져나가는 지점을 명확하게 알려줘야한다.

if문을 사용해서 수정한 버전

def count_down(number):
    if number < 0:         # 만약 숫자가 0보다 작다면, 빠져나가자!
        return
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)

팩토리얼

팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것

!는 팩토리얼의 표기 방법이다.

예시
3! 은 3 * 2 * 1 = 6,
4! 는 4 * 3 * 2 * 1 = 4 * 3! = 24
즉, Factorial(n) = n * Factorial(n - 1)
Factorial(n - 1) = (n - 1) * Factorial(n - 2) .... Factorial(1) = 1 의 구조다.

def factorial(n):
    return n * factorial(n - 1)

print(factorial(5))
#오류가 뜬다.범위를 지정 안해줬기 때문이다.

#최종수정
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

회문

회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장

# palindrome 은 회문을 의미합니다!
is_palindrome("토마토")   # True
is_palindrome("tomato") # False
is_palindrome("abcba")  # True

#맨앞글자와 맨뒤글자 > 두번째 뒤두번쨰 > 세번째 뒤세번째로 반복문을 이용해서 구현한다.

input = "abcba"
#is_palindrome(문자열) → is_palindrome(문자열[1, -1]) 로 문제가 축소
def is_palindrome(string):
    #만약 가운데 글자만 남는다면 true를 반환하도록 한다.이 조건문은 무조건 앞에 있어야한다
    #string -1인덱스를 길이가 1이하인 문장에서 찾으면 에러가 난다. 
    if len(string) <=1:
        return True
    #string의 맨앞과 맨뒤가 다르다면 false를 반환하라.
    if string[0] != string[-1]:
        return False
    return is_palindrome(string[1:-1])

print(is_palindrome(input))

# 1.is_palindrome에 input이 들어가게 된다.
# 2.그 주소를 string에 박혀있는데 길이를 확인해 1이상일 경우 넘긴다.
# 3. 0번째와 1번째 인덱스가 같냐는 조건을 확인하고 넘긴다.
# 4. is_palindrome 1번째~-1번째인텍스까지 문자열을 잘라 다시 한번 호출하고 반복
# 5. 이제 문자열 길이가 1이하면 true를 반환하면 값을 출력한다.

 

문자열 슬라이싱

파이참에서 문자열을 자를 수 있다. 문자열[시작인덱스:끝인덱스] 로 표기

뒤에서 자르고 싶다면 음수 인덱싱을 사용하면 됩니다. ex) "가나다라마바사"[1: -3] 

"가나다라마바사"[0:5] # 가나다라마  Q. 여기서 5번째 인덱스는 "바" 아닌가요?
                             #A. 5번째 인덱스 "전"에서 잘라줍니다.
"가나다라마바사"[1:-3] # 나다라

파이썬 정렬 방법

배열뒤 .sort()함수 호출하기

 

집합(자료형)

중복을 허용하지 않는 자료형. set라는 함수를 사용한다.

ex) a = set([1,2,3,1,2])   결과 = 1,2,3

Q.menus_set을 set함수를 통해 집합화를 하는 것인데 집합화를 안해도 코드는 작동을 합니다. 굳이 필요한 작업인건지

A.  in 연산자는 어떤 자료형을 탐색하느냐에 따라 시간복잡도의 차이가 발생합니다

1)list인 menus를 in 연산으로 순회하고 있습니다.

내부적으로 파이썬은 list에 대해서 in연산을 O(N)의 시간복잡도로 처리합니다

2)menus를 set으로 바꿔서 in 연산을 진행합니다.

내부적으로 파이썬은 set에 대해서 in 연산은 O(1)의 시간복잡도로 처리합니다