새싹프로그래머의 이야기

문제: cache 사이즈와 문자열 리스트가 주어졌을 때, 캐시 교체에 드는 총 실행시간을 구하는 문제입니다.

풀이 코드:

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

문제 풀이:

문제 풀이의 핵심은 maxlen 옵션을 활용한 deque 사용입니다.

문제에서 캐시 교체 알고리즘은 LRU 알고리즘을 활용한다고 명시해주었습니다.

예를 들면, 길이가 3인 ['a', 'b', 'c'] 라는 리스트에 'd' 라는 원소가 추가된다면 'a'라는 원소가 없어지고 'd'가 추가되는 것입니다.

deque의 maxlen 옵션을 활용한다면 위와 같이 동일하게 동작하는 deque를 구현할 수 있습니다.

from collections import deque

q = deque(maxlen=3)

for i in range(6):
    q.append(i)
    print(q)

위와 같은 코드가 있을 때, 데크에 담기는 원소를 확인해보면 다음과 같습니다.

따라서, 문제 풀이는 maxlen이 정의된 deque를 통해 풀어주었습니다. 

def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

maxlen이 설정된 deque에 append 할 경우, LRU 알고리즘과 맞게 동작하므로 원소가 있는지 여부만 판단하여 실행시간을 구해주었습니다.(원소가 있을 경우, 'cache hit'. 없을 경우, 'cache miss'.)

* 해당 문제는 https://www.youtube.com/watch?v=orf9ailzXvI 을 듣고 작성하였습니다.

문제: 문자열이 주어졌을 때, 문제에서 주어진 방식으로 압축 시킬 수 있는 모든 방법중에서 가장 짧은 문자열의 길이를 구하는 문제입니다.

풀이 코드:

def solution(s):
    answer = 0
    length = len(s)
    lst = [[] for _ in range((length - 1) // 2 + 2)]
    string = ''
    l = 1

    while l <= (length - 1) // 2 + 1:
        strlst = [s[i:i + l] for i in range(0, len(s), l)]  # 1부터 (length - 1) // 2 + 1까지 길이에 맞춰 문자열 쪼개기
        pos = strlst[0]
        cnt = 0
        for i in range(len(strlst)):
            if strlst[i] == pos:    # 앞선 문자열과 동일한 문자열이 들어온다면 갯수를 count하며 추가
                cnt += 1
                string += strlst[i]
            else:
                if cnt > 1:     # 앞선 문자열과 다른 문자열이 들어온다면 문자열 압축 및 새로운 문자열 추가
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))
                cnt = 1
                string += strlst[i]
                pos = strlst[i]

            if i == len(strlst) - 1:    # 동일한 문자가 반복되며 종료될 경우에 대한 처리 진행
                if cnt > 1:
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))

        lst[l] = list(string)
        string = ''
        cnt = 1
        l += 1
    answer = 1001

    for i in lst[1:]:
        if len(i) < answer:
            answer = len(i)

    return answer

풀이 방법:

• 첫번째는 문자열이 있을 때, 앞에서 부터 문자열 길이의 반 이상으로 쪼갠다면 중복되는 것이 생길 수 없으므로 범위를 (문자열 길이 -1)//2 +1 로 정의했습니다.

-> 'abcdefg' 를 'abcde' 'fg'로 쪼갠다면 앞의 문자열에 중복되는 문자열이 뒤에 나올 수 없습니다.

• 두번째로는, 쪼개진 문자열을 앞에서 부터 탐색하면서 다른 문자열이 나올 경우 앞선 문자열에 대한 압축과 동시에 새로 들어온 문자열을 추가해주었습니다.
• 마지막으로,동일한 문자('ababccc'에서 'c') 가 반복되며 종료될 경우를 위해 마지막 index에 대하여 처리하는 코드를 추가해주었습니다.

문제: 주어진 점수를 계산하여 성격유형 검사 결과 출력하기.

풀이 코드:

def solution(survey, choices):
    answer = ''
    dic1 = {'R': 0, 'T': 0, 'C': 0, 'F': 0, 'J': 0, 'M': 0, 'A': 0, 'N': 0}
    lst = 'RTCFJMAN'

    for string, score in list(zip(survey, choices)):
        if score == 4:
            continue
        elif score > 4:
            dic1[string[1]] += abs(score - 4)
        else:
            dic1[string[0]] += abs(score - 4)
    for i in range(0, len(lst), 2):
        if dic1[lst[i]] >= dic1[lst[i + 1]]:
            answer += lst[i]
        else:
            answer += lst[i + 1]

    return answer

풀이 설명:

성격 유형에 대한 점수를 확인하기 위해 다음과 같이 탐색을 해주었습니다.

또한, 탐색 결과를 바탕으로 문제 조건에 맞게 점수를 배분하였습니다.

• 4점 이상일 경우, 'RT'(예시)에서 T에 점수를 배정
• 4점 이하일 경우, 'RT'에서 R에 점수를 배정

for string, score in list(zip(survey, choices)):
    if score == 4:
        continue
    elif score > 4:
        dic1[string[1]] += abs(score - 4)
    else:
        dic1[string[0]] += abs(score - 4)

이후, 각 성격 유형에 대해 점수가 다 반영되면 각 카테고리 별로 강한 성향을 보이는 성격 유형을 answer에 담아주었습니다.

for i in range(0, len(lst), 2):
    if dic1[lst[i]] >= dic1[lst[i + 1]]:
        answer += lst[i]
    else:
        answer += lst[i + 1]

문제: LZW 압축

풀이 코드:

import string


def solution(msg):
    answer = []
    alphabet = list(string.ascii_uppercase)
    dic = {c: i + 1 for i, c in enumerate(alphabet)}
    pos = 27

    while msg:
        length = 1

        while msg[:length] in dic.keys() and length <= len(msg):
            length += 1
        if msg[:length] not in dic.keys():
            dic[msg[:length]] = pos
            pos += 1

        answer.append(dic[msg[:length - 1]])
        msg = msg[length - 1:]

    return answer

문제풀이:

alphabet = list(string.ascii_uppercase)
dic = {c: i + 1 for i, c in enumerate(alphabet)}

먼저, 알파벳에 대한 index가 필요하기 때문에 다음과 같이 enumerate 함수를 통해 딕셔너리 형태로 알파벳:index 형태로 저장해주었습니다.

while msg:
    length = 1

    while msg[:length] in dic.keys() and length <= len(msg):
        length += 1
    if msg[:length] not in dic.keys():
        dic[msg[:length]] = pos
        pos += 1

    answer.append(dic[msg[:length - 1]])
    msg = msg[length - 1:]

가장 핵심이 되는 코드는 문제 조건에 따라 다음과 같이 구현하였습니다.

• 문자열의 시작점으로부터 문자를 탐색하여 딕셔너리에 담긴 최대 길이의 문자열을 구합니다. 즉, 해당 문자열에 한 글자가 추가된다면 해당 문자열은 딕셔너리에 담기지 않은 문자열이 됩니다.
• 딕셔너리에 담기지 않는 문자열에 대해서는 새로운 index와 함께 딕셔너리에 추가해줍니다.
• 딕셔너리에 담긴 최대 길이 문자열에 대한 index를 answer 배열에 담습니다.

위 과정을 반복하여, 문자열을 압축합니다.

문제: 두 개의 문자열이 있을 때, 자카드 유사도를 구하는 문제입니다.

조건:

• 입력된 문자열을 두 글자씩 끊어서 다중집합의 원소로 만듭니다.
• 이때, 토큰화 된 문자열에 특수문자가 들어갈 경우 제외합니다.
• 대문자와 소문자의 차이는 무시합니다.

풀이 코드:

num = 65536


def solution(str1, str2):
    answer = 0

    dic1 = dict()
    dic2 = dict()

    ls1 = len(str1)
    ls2 = len(str2)
    
    for i in range(ls1 - 1):
        key = str1.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic1.get(key):
                dic1[key] += 1
            else:
                dic1[key] = 1

    for i in range(ls2 - 1):
        key = str2.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic2.get(key):
                dic2[key] += 1
            else:
                dic2[key] = 1

    # intersection
    int_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            int_val += min(dic1[i], dic2[i])
    # Union 구하기
    uni_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            uni_val += max(dic1[i], dic2[i])
            dic2.pop(i)
        else:
            uni_val += dic1[i]

    for i in dic2.keys():
        uni_val += dic2[i]

    if uni_val == 0:
        answer = num
    else:
        answer = int(int_val / uni_val * num)

    return answer

풀이 설명:

for i in range(ls1 - 1):
    key = str1.lower()[i:i + 2]
    if key.isalpha():  # 특수문자 있을 경우 제외.
        if dic1.get(key):
            dic1[key] += 1
        else:
            dic1[key] = 1

자카드 유사도의 경우, 다중집합의 경우 같은 문자열도 다른 원소로 취급하므로 개 수를 세기 위해 딕셔너리를 활용하였습니다.

또한, 특수문자가 포함된 문자열을 제거하기 위해 .isalpha() 함수를 활용하였습니다.

str1 = '112' str2 = '1212' 일 경우,

dic1 = { '11' : 1 , '12': 1}

dic2 = {'12': 2 , '21:': 1} 가 됩니다.

# intersection
int_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        int_val += min(dic1[i], dic2[i])

교집합을 구하는 부분은 다음과 같습니다. 토큰화된 문자열에 대한 개 수를 담은 딕셔너리의 key 값을 통해 같은 key가 존재할 경우, 

교집합이기 때문에 최소값을 더해주었습니다.

위의 예시에서 str1에는 '12'가 1개 , str2에는 '12'가 2개 있을 때 교집합은 1개 인 것을 보면 이해에 도움이 되실 것 입니다.

# Union 구하기
uni_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        uni_val += max(dic1[i], dic2[i])
        dic2.pop(i)
    else:
        uni_val += dic1[i]

for i in dic2.keys():
    uni_val += dic2[i]

합집합의 경우, 두 문자열에 모두 존재하는 원소일 경우 개 수의 최대 값을, dic1에만 존재할 경우 그 원소의 개 수를 더하도록 하였으며, 

교집합에 해당되는 원소에 대한 값을 반영하였을 경우, pop() 함수를 통해 dic2에서 제거를 해주었습니다.

그리고 아직 dic2에만 있는 원소에 대한 값을 반영하지 않았으므로, 반복문을 별도로 구성해 값을 반영하여 주었습니다.

문제를 풀고 나서 다른 코드들을 보니 엄청 깔끔하고 파이써닉하게 풀어낸 코드가 있어서 소개드리고 마무리 하도록 하겠습니다.

num = 65536

def solution(str1, str2):
    answer = 0

    token1 = [str1[i:i + 2].lower() for i in range(len(str1) - 1) if str1[i:i + 2].isalpha()]
    token2 = [str2[i:i + 2].lower() for i in range(len(str2) - 1) if str2[i:i + 2].isalpha()]

    intersect = set(token1) & set(token2)
    uni = set(token1) | set(token2)


    uni_val = sum(max(token1.count(i), token2.count(i)) for i in uni)
    intersect_val = sum(min(token1.count(i), token2.count(i)) for i in intersect)


    if uni_val == 0:
        answer = num
    else:
        answer = int(intersect_val/uni_val*num)
    return answer

다중집합의 원소의 개 수로 답을 구하는 문제이므로, set()과 count() 함수를 통해 깔끔하게 풀어낸 풀이가 있더라구요. 보면서 감탄만 나왔던 코드였습니다. 제가 앞으로 파이썬으로 알고리즘을 공부해가면서 나아가야할 방향을 보여주는 듯 했습니다.

머신러닝이란?

머신러닝은 인공지능(AI)의 하위 집합으로, 경험을 통해 자동으로 개선하는 컴퓨터 알고리즘에 대한 연구 입니다. 즉, 컴퓨터가 학습할 수 있도록 알고리즘과 기술을 개발하는 분야입니다. 머신러닝의 알고리즘은 대규모 데이터 셋에서 패턴과 상관관계를 찾고, 이에 대한 분석을 기반으로 최적의 의사결정과 예측을 수행하도록 훈련됩니다.

*머신러닝과 그 구성요소인 딥러닝, 신경망은 모두 AI의 하위집합입니다.

신경망이란?

신경망은 인공 신경망(ANN, Artificial Neural Network)라고도 불리며, 인간의 두뇌로 부터 영감을 받아 생물학적 뉴런이 신호를 주고받는 방식을 모방했습니다. 하나의 입력 계층, 하나 이상의 은닉 계층 및 하나의 출력 계층을 포함하는 노드 계층들로 구성되어 있습니다. 각 노드 또는 인공 뉴런은 숫자로 된 신호를 수신하여 이를 처리하고 연결된 다른 뉴런으로 신호를 전송합니다. 사람의 뇌와 마찬가지로 패턴 인식, 지식, 전반적인 학습을 개선합니다.

딥러닝이란?

딥러닝(Deep Learning)은 신경망과 혼동되어 사용되어진다고 합니다. '딥(Deep)'이 의미하는 바는 신경망에서 계층의 깊이를 의미합니다. 입력과 출력을 포함할 수 있는 세 개이상의 계층으로 구성된 신경망은 딥러닝 알고리즘으로 분류 될 수 있으며, 2개 또는 3개의 계층을 갖는 신경망은 기본 신경망에 불과합니다.

세개 이상의 계층으로 구성된 인공신경망을 기반으로 스스로 학습을 수행하고 예측하는 모델입니다.

머신러닝과 딥러닝의 차이점

머신러닝은 컴퓨터가 학습할 수 있도록 알고리즘과 기술을 개발하는 분야라고 하였고, 딥러닝은 인공신경망을 기반으로 스스로 학습하는 모델이라고 하였습니다. 세분화 하여 분류하면 다음과 같습니다.

머신러닝: 인간이 데이터를 제공하고, 그 데이터를 기반으로 학습 및 예측을 수행하는 것. 즉, 데이터가 인간에 의해 제공이 되어야합니다.

딥러닝: 데이터를 스스로 학습할 수 있는 모델. 즉, 데이터가 제공되지 않습니다.

빅데이터, 데이터 마이닝과 머신러닝의 차이점

빅데이터: 대규모 데이터를 처리하는 기술

데이터 마이닝: 가지고 있는 데이터에서 현상 및 특성을 발견하는 것을 목적으로함.

머신러닝은 기존 데이터를 학습하여 새로운 데이터에 대하여 예측하는 것을 목적으로함.

머신러닝의 알고리즘 - 지도학습, 비지도학습, 강화학습

머신러닝 알고리즘은 크게 지도 학습(Supervised-Learning), 비지도 학습(Unsupervised-Learning), 강화 학습(Reinforcement-Learning)으로 나눌 수 있습니다.

1. 지도 학습

지도 학습(Supervised-Learning)은 데이터에 대한 레이블(Label, 정답)을 제공하여 학습시키는 방법입니다.

이를 바탕으로, 새로운 입력 값을 토대로 예측하는 것을 목표로 하는 학습 방법입니다.

지도학습의 종류에는 대표적으로 Classification(분류) 문제와 Regression(회귀) 문제가 있습니다.

Classification(분류): 분류는 주어진 데이터를 기반으로 정해진 카테고리(라벨)에 따라 분류하는 문제를 말합니다. 

예를 들면, 동물의 사진과 그 종에 대한 정보가 주어지면 이를 바탕으로 학습을 진행한 후, 새로운 동물의 사진이 입력 값으로 들어왔을 때 어떤 동물인지 분류하는 것입니다.

Regression(회귀): 회귀는 데이터들의 Feature을 기준으로, 연속된 값(Graph)를 예측하는 문제로 주로 경향 등을 예측하는데 활용됩니다. 

예를 들어, 집 값 예측을 위하여, 지역과 평 수에 대한 아파트 가격 데이터를 기반으로 학습하여, 특정 지역의 특정 평수에 대한 집 값을 예측하는 것이 있습니다.

2. 비지도 학습

비지도 학습(Unsupervised-Learning)이란, 지도 학습과 달리 정답 라벨(Label)이 없는 데이터를 학습 시키는 방법입니다. 라벨링 되어있지 않은 데이터를 기반으로 학습을 진행하며, 스스로 데이터의 패턴(Pattern) 또는 유사성(Similiarity)등을 학습합니다. 데이터 간의 숨어 있는 특징(Feature) 또는 구조(Structure)을 찾아내어 비슷한 구조끼리 묶는 것(clustering)을 목표로 합니다.

3. 강화 학습

강화 학습(Reinforcement Learning)은 지금까지 봐왔던 지도 학습 또는 비지도 학습과는 약간 다른 종류의 학습이라고 할 수 있습니다. 앞의 두 학습은 데이터가 주어진 상황에서의 학습, 즉 정적인(Static) 상태에서의 학습입니다. 반면, 강화 학습은 주어진 상황(State)에 대하여 행동(Action)을 취하고, 이에 대하여 보상(Reward)을 받으면서 학습을 진행하게 됩니다. 즉, 역동적인(Dynamic) 상태에서의 학습입니다. 행동에 대한 보상이 최대가 되도록 하는 것을 목표로 합니다.

추가적으로, 준지도 학습(Semi-Supervised Learning)이라는 것이 있습니다. 준지도 학습은 정답(Label)이 있는 데이터와 정답이 없는 데이터를 모두 사용하여 학습을 시키는 방법입니다. 지도 학습의 분류 분야에서는 레이블링 되지 않은 데이터를 통해 성능을 향상시키는데 활용될 수 있고, 반대로 비지도 학습의 클러스터링 분야에서는 새로운 데이터를 어느 클러스터에 넣을지 결정함에 있어 활용될 수 있습니다.

레이블링된 데이터를 구성하는 cost를 줄일 수 있다는 장점이 있습니다만, 몇가지의 전제 조건이 필요하며 무조건적인 성능 향상을 보장하지 않습니다.

reference

https://www.ubuntupit.com/frequently-asked-machine-learning-interview-questions-and-answers/

*컴퓨터 구조 및 설계 5th Edition (저자 David A. Patterson 과 John L. Hennessy)를 기반으로 작성되었습니다.

*MIPS 어셈블리언어 기반으로 작성되었습니다.

프로시저(procedure)와 함수(Function)는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나입니다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중하여 처리할 수 있게 도와줍니다. 그리고 프로시저는 소프트웨어에서 추상화를 하는 구현 방법입니다.

프로그램이 프로시저를 실행하는 방법은 다음과 같습니다.

1. 프로시저가 접근할 수 있는 곳에 인수를 넣습니다.
2. 프로시저로 제어를 넘깁니다.
3. 프로시저가 필요로 하는 메모리 자원을 획득합니다.
4. 필요한 작업을 수행합니다
5. 호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣습니다.
6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 자리로 되돌려줍니다.

*프로시저(procedure): 제공되는 인수에 따라서 특정 작업을 수행하는 서브루틴.

*인수(parameter)는 프로시저에 값을 보내고 결과를 받아오는 일을 처리하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스(interface)역할을 수행합니다. 

레지스터는 데이터를 저장하는 가장 빠른 장소이므로 많이 사용하는 것이 바람직합니다. 따라서, MIPS 소프트웨어는 다음의 프로시저 호출 관례에 따라 레지스터 32개를 할당합니다.

MIPS 어셈블리 언어는 레지스터를 할당할 뿐만 아니라 프로시저를 위한 명령어도 제공합니다. 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하는 명령으로 jal 명령어(jump-and-link instruction)이라 부른다.

link란, 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻입니다. 동작 과정을 보면, 먼저 호출 프로그램(caller)은 $a0 - $a3에 전달할 인수 값을 넣은 후 jal X 명령을 이용해서 프로시저 X[피호출 프로그램(callee)라고 부릅니다.] 로 점프 합니다. 그렇게 되면, 피호출 프로그램은 계산을 끝낸 후, 계산 결과를 $v0 - $v1에 넣은 후 jr $ra 명령을 실행하여 복귀합니다.

* 현재 수행 중인 명령어의 주소를 기억하는 레지스터를 프로그램 카운터(program counter)라고 부릅니다. jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC+4를 레지스터 $ra에 저장합니다.

컴파일러가 프로시저를 번역하는거에 있어서 인수 레지스터 4개, 결과 값 레지스터 2개만으로는 부족한 경우가 있을 수 있습니다. 프로시저 호출이 다른 부분에 영향을 미쳐서는 안되므로 호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야합니다. 데이터 복원을 위해 메모리에 데이터(기존 레지스터 값)를 저장한 후 사용합니다. 즉, '레지스터 스필링'이 필요한 경우입니다. 이를 위해서 자료구조로는 스택(stack)을 사용합니다. 또한 스택을 사용하려면 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가르키는 포인터가 필요합니다. 이를 스택 포인터(stack pointer)라고 하며, 레지스터 29번을 할당해놓고 있습니다. 스택에 데이터를 넣는 작업을 푸시(push), 꺼내는 작업을(pop)이라고 합니다. 그리고 역사적 선례에 따라서 스택은 높은 주소에서 낮은 주소쪽으로 공간을 할당합니다.

int leaf_example(int g, int h, int i, int j)
{
    int f;

    f = (g + h) - (i + j);
    return f;
}

예를 들어 위와 같은 코드가 있을 때, 임시 레지스터를 통하여 레지스터 스필링을 줄일 수 있습니다. 

첫번째로 t0, t1 레지스터를 원상복구해야한다고 가정했을 때 MIPS 어셈블리 코드는 다음과 같습니다.

leaf_example:

$\qquad addi \quad \$sp\,,\$sp\,,-12$     # 향후 사용할 $t0, $t1, $s0가 사용할 스택 공간 할당

$\qquad sw \quad \$t1\,,8(\$sp)$    # 원상 복구 하기 위해 스택에 레지스터 저장

$\qquad sw \quad \$t0\,,4(\$sp)$   # 원상 복구 하기 위해 스택에 레지스터 저장

$\qquad sw \quad \$s0\,,0(\$sp)$   # 원상 복구 하기 위해 스택에 레지스터 저장

$\qquad add \quad \$t0\,,\$a0\,,\$a1 $     # t0 = g + h

$\qquad add \quad \$t1\,,\$a2\,,\$a3 $     # t1 = i + j

$\qquad sub \quad \$s0\,,\$t0\,,\$t1 $     # f = $t0 - $t1  => (g + h) - (i  + j)

결과 f를 보내주기 위해 결과 값 레지스터에 f를 복사합니다.

$\qquad add \quad \$v0\,,\$s0\,,\$zero$     # return f

호출 프로그램으로 되돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구 합니다.

$\qquad lw \quad \$s0\,,0(\$sp) $     # 레지스터 복구

$\qquad lw \quad \$t0\,,4(\$sp) $     # 레지스터 복구 

$\qquad lw \quad \$t1\,,8(\$sp) $     # 레지스터 복구

$\qquad addi \quad \$sp\,,\$sp\,,12$     # stack에 할당한 공간 삭제

프로시저는 복귀 주소를 사용하는 jr 명령으로 끝납니다.

$\qquad jr \quad \$ra$   #복귀 주소를 기반으로 복귀합니다.

하지만 임시 레지스터와 같이 간단한 관례를 정함으로써 레지스터 스필링을 많이 줄일 수 있습니다. 실제로 t0, t1 값은 호출 전후로 같은 값을 유지할 필요가 없기 때문에 저장 명령 두 개와 적재 명령 두 개를 없앨 수 있습니다.

새 데이터를 위한 스택 공간의 할당

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데에도 스택이 사용되기 때문에 보다 복잡해집니다. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame) 또는 액티베이션 레코드(activation record)라고 부릅니다.

MIPS 소프트웨어 중에는 프레임 포인터(frame pointer, $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있습니다.  즉, 스택을 사용하는데 있어서 베이스 레지스터 역할을 수행하여 지역 변수를 간단하게 참조할 수 있도록 하는 역할을 합니다. (그림 1 참조)

*별도의 프레임 포인터 사용 여부와 상관 없이 액티베이션 레코드는 항상 스택에 존재합니다.

새 데이터를 위한 힙 공간의 할당

C 프로그래머는 프로시저에만 국한되는 자동 변수 외에도 정적 변수와 동적 자료구조를 위한 메모리 공간이 필요합니다. 정적 데이터 세그먼트(static data segment)라는 부분이 있는데, 상수와 기타 정적 변수들이 저장됩니다(그림 1 참조). 배열은 그 크기가 고정되어 있어 정적 세크 먼트에 잘 맞습니다. 다만 링크드 리스트(linked list)와 같은 자료 구조는 늘어났다 줄어들었다 합니다. 이러한 자료구조를 위한 세그먼트를 전통적으로 힙(heap)이라고 합니다. 

*스택과 힙이 서로 마주보면서 자라도록 할당하기 때문에 공간을 효율적으로 사용합니다.

*C언어의 경우, 함수를 통해 힙 공간을 할당받고 반환하는데 사용이 끝난 공간을 반납하는 것을 잊어버리면 '메모리 누출(memory leak)'이 발생하여 메모리 부족으로 운영체제가 붕괴될 수 있습니다.

*반대로 공간을 너무 일찍 반납하면 프로그램의 의도와 상관없이 엉뚱한 것을 가리키는 '매달린 포인터(dangling pointer)'가 발생합니다.

*Java에서는 이러한 버그를 피하기 위해 자동 메모리 할당과 가비지 컬렉션(garbage collection)을 사용합니다.

*컴퓨터 구조 및 설계 5th Edition (저자 David A. Patterson 과 John L. Hennessy)를 기반으로 작성되었습니다.

*MIPS 어셈블리언어 기반으로 작성되었습니다.

논리연산 명령어

초기의 컴퓨터는 워드 전체에 대한 처리에만 관심을 가졌습니다. 하지만 곧 워드 내 일부 비트에 대한 연산 , 심지어는 개개 비트에 대한 연산도 필요하다는 것이 명백해졌습니다. 이를 위해 만들어진 명령어들을 논리연산 명령어 라고 부릅니다.

• 자리이동(shift)

$$0000\,0000\,0000\,0000\,0000\,0000\,0000\,1001_{two} = 9_{ten}$$

위와 같은 값이 있을 때 왼쪽으로 4번 shift 시키는 명령어를 실행하면 다음과 같이 됩니다.

$$0000\,0000\,0000\,0000\,0000\,0000\,1001\,0000_{two} = 14_{ten}$$

이렇게 왼쪽으로 자리이동을 하는 명령어를 sll(shift left logical)이라고 하며, 반대로 오른쪽으로 자리이동하는 명령어를 srl(shift right logical) 이라고 부릅니다. R 형식의 명령어와 기계어 형식으로 표현하면 다음과 같습니다.

$$ sll \quad \$t2,\$s0,4$$

*shamt필드는 shift amount를 나타내는 것으로 자리이동 명령어에서 사용됩니다. 

sll 명령은 또 다른 용도로 사용될 수 있는데 왼쪽으로 $i$비트 자리이동을 하면 $2^i$을 곱한 것과 같은 결과가 됩니다.

• AND

AND 연산은 비트대 비트 연산자로서 두 비트 값이 모두 1일 경우에만 결과가 1이 되는 연산입니다.

$$0000\,0000\,0000\,0000\,0000\,1101\,1100\,0000_{two} $$

$$0000\,0000\,0000\,0000\,0011\,1100\,0000\,0000_{two} $$

위와 같은 t1, t2 값이 있을 때, 다음과 같은 MIPS 명령어를 실행하고 나면

$$and \quad \$t0,\$t1,\$t2$$

t0 레지스터의 값은 다음과 같이 됩니다.

$$0000\,0000\,0000\,0000\,0000\,1100\,0000\,0000_{two}$$

• OR

OR 연산은 AND와 대칭되는 연산으로 두 비트 중 하나만 1이면 결과가 1이 되는 연산자입니다. 

$$or \quad \$t0,\$t1,\$t2$$

위와 같은 명령어를 수행하면 t0 레지스터 값은 다음과 같이 됩니다.

$$0000\,0000\,0000\,0000\,0011\,1101\,1100\,0000_{two}$$

• NOT

NOT연산은 0을 1로, 1을 0으로 바꾸는 연산입니다.

판단을 위한 명령어

컴퓨터가 단순한 계산기와 다른 점은 판단 기능이 있다는 점입니다. 프로그래밍 언어에서는 보통 if 문으로 판단 기능을 표현하는데, MIPS의 경우 beq, bne 명령어를 통해 표현합니다.

• beq: branch if equal

$$beq\quad\,register1\,,register2\,,L1$$

예를 들면 위와 같은 명령어는 'register1과 register2가 같다면 L1에 해당하는 문장으로 이동.' 이라는 뜻입니다.

• bne: branch if not equal

$$bne\quad\,register1\,,register2\,,L1$$

register1과 register2가 다르다면 L1으로 이동하라는 뜻입니다.

*beq, bne 두 명령어를 조건부 분기(conditional branch) 라고 부릅니다.

*어셈블러가 컴파일러나 어셈블리 언어 프로그래머가 지겨운 분기 주소 계산을 하지 않도록 해줍니다.

*컴파일러가 소스 프로그램에는 없는 분기 명령이나 레이블을 만들어 내는 경우가 많이 있습니다. 이를 통해, 필요한 레이블과 분기 명령을 일일이 표시하지 않아도 되는 것이 상위 수준 프로그래밍 언어의 장점 중 하나이며, 코딩이 더 빨라지는 이유이기도 합니다.

• Loop

판단 기능은 둘 중 하나를 선택(if 문장 사용)하는 것도 중요하지만, 계산의 반복(순환문 사용)에도 중요합니다.

• slt, slti: set on less than

비교 명령은 부호 있는 수와 부호 없는 수 사이의 이분법도 다루어야 한다. 어떤 때는 MSB가 1인 수가 음수를 나타내며, 이때는 MSB가 0인 어떤 양수보다도 작으며, 부호가 없는 정수의 경우에는 MSB가 1인 수가 MSB가 0인 어떤 양수보다도 더 큽니다. MIPS는 이 두가지 경우를 처리할 수 있도록 set on less than의 두가지 유형의 명령어를 제공합니다. 

*slt, slti는 부호 있는 수에, sltu, sltiu는 부호없는 정수에 사용합니다.

*blt(branch on less than) 명령어는 제외되었습니다. 이 명령어는 구현하게되면 클럭 속도가 느려지거나 이 명령 실행에 별도의 클럭 사이클이 더 필요하게 되므로 하드웨어는 간단해야 좋다는 von Neumann의 경고를 준수하여 MIPS 구조에서는 제외되었습니다.

MIPS에서는 부호 있는 수와 부호 없는 수에 대하여 MSB의 이중적 의미를 이용하여 배열 경계 검사 비용을 줄이는 방법이 있습니다. 부호 있는 정수를 부호없는 정수처럼 다루면 $0 <= x < y$ 검사비용을 낮출 수 있는데, 이 검사는 인덱스가 배열의 한계를 벗어났는지 확인하는 검사에 딱 맞습니다. 핵심은 2의 보수로 표현된 음수가 부호없는 정수에서의 큰 수 처럼 보인다는 것입니다. 

* 여기서 말하는 배열의 한계란 다음과 같습니다. 배열의 index는 배열의 length를 벗어날 수 없다. 즉, length보다 큰 index를 갖거나 음수인 index를 가질 수 없다는 것입니다.

$$ sltu \quad \, $t0\,,$s1\,,$t2$$

$$beq \, $t0\,,$zero\,,IndexOutOfBounds$$

위 명령어는 경계를 검사하는 명령어로 부호없는 정수 연산을 이용하여 한번에 두 가지 모두 검사하는 명령어입니다.

s1은 index를 t2는 배열 사이즈를 의미합니다. 

$sltu\quad \, \$t0\,,\$s1\,,\$t2$ 를 보면 s1(index) >= length or s1(index) < 0이라면 t0 = 0 가 되는 명령어 입니다.

$beq\quad \, \$t0\,,\$zero\,,IndexOutOfBounds$를 보면 t0 == 0 일 경우, Error를 발생시키도록 되어 있죠.

이렇게 MSB의 이중적 의미를 통해 한 명령어로 경계 검사를 한번에 수행할 수 있습니다.

• case/switch 문장

대부분의 프로그래밍 언어는 특정 변수의 값에 따라 여러가지 중 하나를 선택하는 case나 switch 문장을 갖고 있습니다. 가장 간단한 방법은 계속적인 조건 검사를 통해 switch를 if-then-else의 연속으로 변환하는 것입니다.

다만, 여러 코드의 시작주소를 표로 만들면 더 효율적으로 구현할 수 있기 때문에, 프로그램은 점프 주소 테이블(jump address table) 또는 점프 테이블(jump table)의 인덱스만 계산해서 해당 루틴으로 점프할 수 있습니다.

*컴퓨터 구조 및 설계 5th Edition (저자 David A. Patterson 과 John L. Hennessy)를 기반으로 작성되었습니다.

*MIPS 어셈블리언어 기반으로 작성되었습니다.

명령어는 컴퓨터 내부에서 높고 낮은 전기 신호의 연속으로 저장되므로 숫자로 표현할 수 있습니다. 실제로 명령어의 각 부분을 숫자로 볼 수 있으며, 이 숫자들을 나란히 늘어놓으면 명령어가 됩니다.

예를 들어, 다음 어셈블리 명령어의 실제 MIPS의 언어 버전을 십진수와 이진수의 형태로 표현하면 다음과 같습니다.

$$add \, \$t0,\$s1,\$s2$$

<십진수 표현법>

<이진수 표현법>

*세부 설명은 MIPS 명령어 필드 설명 부분에서 진행하겠습니다.

위 예제에서 보인 레이아웃을 명령어 형식(instruction format)이라고 합니다. MIPS 명령어 길이는 데이터 워드와 마찬가지로 32비트이며, "간단하게 하기 위해서는 규칙적인 것이 좋다" 라는 설계 원칙에 따라 모든 MIPS 명령어는 32비트 입니다.

어셈블리 언어와 구별하기 위하여 명령어를 숫자로 표현한 것을 기계어(machine language)라고 하고, 이런 명령어들의 시퀀스를 기계 코드(machine code)라 합니다.

모든 컴퓨터의 데이터 길이는 4의 배수이므로 16진수(hexadecimal)가 많이 사용됩니다. 기수 16은 2의 멱승이므로 이진수 4비트를 16진수 숫자 하나로 쉽게 바꿀 수 있으며, 그 반대도 마찬가지 입니다. 

MIPS 명령어 필드

• op: 명령어가 실행할 연산의 종류로서, 연산자(opcode)라고 부릅니다.
• rs: 첫 번째 근원지(source) 피연산자 레지스터를 의미합니다.
• rt: 두 번째 근원지 피연산자 레지스터를 의미합니다.
• td: 목적지(destination) 레지스터를 의미합니다. 연산 결과가 기억됩니다.
• shamt: 자리이동(shift)량을 의미합니다.
• funct: 기능(function)을 의미합니다. op 필드에서 연산의 종류를 표시하고 funct 필드에서 연산을 구체적으로 지정합니다.

5비트 필드로는 부족한 경우가 있을 수 있습니다. 설계원칙 4번 "좋은 설계에는 적당한 철충이 필요하다." 라는 원칙에 의거하여 MIPS 설계자들이 택한 절충안은 모든 명령어의 길이를 같게 하되, 명령어 종류에 따라 형식은 다르게 하는 것이었습니다. 위와 같은 명령어 형식을 R타입 또는 R 형식(R은 Register를 의미합니다.)이라 하며, 이것만으로는 불충분하기 때문에 I 타입 또는 I 형식(I는 immediate)라는 명령어 형식을 만들었습니다. I 타입은 수치 연산과 데이터 전송 명령어에서 사용되며 그 모양은 다음과 같습니다.

각 필드는 6bits, 5bits, 5bits, 16bits입니다. I - 형식의 명령어에서는 rt필드의 의미가 바뀌어 적재 결과가 들어갈 목적지 레지스터 번호를 표시하는 것으로 바뀌었습니다.

명령어 형식이 여러가지가 되면서 하드웨어는 복잡해지지만 모든 형식을 유사하게 함으로써 복잡도를 낮출 수 있었습니다.

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 플로이드 워셜 알고리즘이란?

최단 경로 알고리즘 중 하나로, 모든 노드에서 모든 노드까지의 최단 경로를 모두 구하는 알고리즘 입니다.

플로이드 워셜 알고리즘은 거리 정보를 계산할 때, 점화식을 활용한다는 점에서 다이나믹 프로그래밍이 적용되어 있다고 할 수 있습니다.

점화식은 다음과 같습니다.

$$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$

동작과정은 다음과 같습니다.

1. 초기 값 입력. 

각 간선(edge)에 대한 cost가 주어진다고 가정하였을 때, 이차원 배열에 해당 cost를 갱신 시킵니다.

자기 자신에 대한 cost는 0이며, 갈 수 없는 노드는 INF로 초기화 합니다.

2. 각 노드를 순회하며, 해당 노드를 거쳐갈 수 있는 경로 확인 및 갱신

예를 들어, 모든 1번 노드에 대해서 거쳐갈 수 있는 경로는 다음과 같습니다.

$$D_{23} = min(D_{23}, \, D_{21}+D_{13}) \qquad =>min(2,7+4) == 2$$

$$D_{24} = min(D_{24}, \, D_{21}+D_{14}) \qquad =>min(2,7+INF) == 2$$

$$D_{32} = min(D_{32}, \, D_{31}+D_{12}) \qquad =>min(INF,5+1) == 6$$

↑update

$$D_{34} = min(D_{34}, \, D_{31}+D_{14}) \qquad =>min(3,5+INF) ==3$$

$$D_{42} = min(D_{42}, \, D_{41}+D_{12}) \qquad =>min(INF,1+1) == 2$$

↑update

$$D_{43} = min(D_{43}, \, D_{41}+D_{13}) \qquad =>min(INF,1+4)==5$$

↑update

이와 같이 거쳐가는 경로를 계산하여, 기존 담겨있는 cost보다 더 낮은 cost가 든다면 table을 갱신하여 줍니다.

이 과정을 모든 노드에 대하여 반복하여 줍니다.

2. 코드구현

코드는 백준 알고리즘 11404번을 기반으로 작성되었습니다.

• 이차원 배열(= 거리 테이블)에 대하여, 자신한테로의 경로를 0으로 초기화 해줍니다.
• 간선와 cost에 대한 정보를 입력받아 거리 테이블에 갱신하여 줍니다.
• 3중 for문을 통해, 각 노드별로 거쳐가는 경로(점화식 기반)를 모두 탐색하고 거리 테이블을 갱신합니다. 

import sys

INF = sys.maxsize

n = int(input())    # number of city
m = int(input())    # number of bus

graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0  # path to self = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = min(graph[a][b],c)    # update array about initial path

# D_ab = D_ak + D_kb
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for i in range(1,n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            graph[i][j] = 0
for i in range(1, n+1):
    print(*graph[i][1:])
    # print(' '.join(map(str,graph[i][1:])))

• Reference

https://freedeveloper.tistory.com/385