새싹프로그래머의 이야기

[문제 풀이]

• 배열의 좌표가 (i,j)일 때, 해당 배열의 요소 값은 좌표 중 큰 값 입니다.
• 따라서, left와 right가 포함되는 열만 배열로 만들어서 배열의 좌표중 큰 값을 배열의 요소로 만들었습니다.
• 하지만, 시간 복잡도 부분에서 성능이 떨어지는 코드입니다. 또한, left와 right가 포함되는 열만 만들어줘야 하므로 출력하고자 하는 범위를 다시 계산해야한다는 단점이 있습니다.

**하지만, 저 좋은 발상이 있었습니다. 배열의 크기는 3x3이고 5번째 좌표를 알고 싶을 때, 그 좌표는 (5//3+1,5%3+1)인 것입니다.

(+1을 하는 이유는, 좌표를 (0,0) 부터가 아닌 (1,1)부터 계산하기 때문입니다.)

두번째 코드가 위 발상에 해당되는 코드입니다.

[풀이 코드]

def solution(n, left, right):
    answer = [(i, j) for i in range(int(left // n) + 1, int(right // n) + 2) for j in range(1, n + 1)]
    l = left - (int(left // n) * n)
    r = l + (right - left)
    return list(map(max, answer[l:r + 1]))

def solution(n, left, right):
    return [max(i // n, i % n) + 1 for i in range(left, right + 1)]

운영체제의 핵심은 바로 Virtualization(가상화) 입니다.

그렇다면 가상화란 무엇일까요?

가상화란?

"물리적인 컴퓨터 리소스의 특징을 다른 시스템, 응용프로그램, 최종 사용자들이 리소스와 상호 작용하는 방식으로부터 감추는 기술" - 위키피디아

만약 가상화 되지 않는 컴퓨터를 사용한다면, 하나의 작업을 하기 위해서 한 대의 컴퓨터와 서버가 필요합니다. 실제로 컴퓨터 기능의 10% ~ 15% 정도 밖에 사용하지 못한다고 합니다. 보다 효율적으로 활용하기 위해 "가상화"란 기술이 나왔습니다.

가상화란, 컴퓨터 리소스를 물리적으로 활용하는 것이 아닌 논리적으로 활용하도록 하는 기술입니다.

물리적으로 활용한다면 하나의 리소스를  A라는 작업을 차지하는 반면 논리적으로 활용한다면 하나의 리소스에 A라는 작업이 차지 하지 않는 부분을 B라는 작업이 활용할 수 있게 하는 기술 입니다.

가상화의 장점은?

1. 비용 절감: 1개의 OS에서 1개의 TASK를 수행하기 위해서는 1개의 물리적 서버가 필요합니다. 하지만 가상화를 하게 되면, 1개의 서버로 여러 개의 TASK를 수행할 수 있으므로 비용을 감소 시키는 효과가 있습니다.
2. 효율성: Resource를 abstract하여 사용함으로써, resource 자체를 효율적으로 사용할 수 있습니다. 또한, 하나의 물리적 시스템을 논리적으로 분리하여 여러 OS를 사용할 수 있습니다.
3. 재해 복구 능력 향상 및 연속성 유지: 자연 재해, 사이버 공격 등으로 인해 물리적 시스템이 손상된다면 복구하는데 많은 자원과 시간이 필요합니다. 하지만 가상화된 횐경은 몇 분내로 복구가 가능합니다. 빠른 복구가 가능할 뿐더러 물리적 시스템으로부터 분리된 환경을 제공함으로써 물리적 시스템을 보호하는 효과도 있습니다.

가상화의 종류?

Host OS형

Host OS형 가상화는 VMware, VirtualBox등의 가상화 기술을 통해  Host OS 위에서 가상화 소프트웨어와 가상 머신을 동작시키는 방법입니다. 일반적으로 물리적 소프트웨어 위에 있는 OS를 Host OS 라고 부르며, 가상머신에 설치되어 동작하는 OS를 Guest OS라고 부릅니다.

Host OS 위에서 별도의 OS를 구동시키는 방법이라 Host OS에는 별 다른 제약이 없으나, 같은 이유로 오버헤드가 클 수 있습니다.

하이퍼바이저형

하이퍼바이저형은 크게 전가상화 방식(Full Virtualization)과 반가상화 방식(Para Virtualization)으로 나뉩니다.

[전가상화 방식]

전가상화 방식은 말 그대로 하드웨어 전체를 가상화하여 활용하는 방식입니다. 하드웨어를 완전히 가상화 한다는 것은 CPU가 가상화 지원이 가능해야합니다.  뿐만 아니라, Guest OS는 자신이 가상화된 OS인지 모릅니다.   여기서 두 가지 문제점이 발생합니다.

첫번째, Guest OS는 자신이 가상화 된 OS인지 모르므로, 자신의 OS에서 사용하는 하드웨어 동작 명령을 전달하려고 하는 문제.

두번째, 같은 이유로 특권 명령(previleged Instruction)과 같이 Root 모드에서만 가능한 동작을 실행하려 할 때 발생하는 문제.

위 두가지 문제는 모두 하이퍼바이저(HyperVisor)가 해결합니다.

첫번째 문제의 경우, HyperVisor가 각 Guest OS로부터 명령을 전달 받아 Host OS에 맞게 번역하여 전달합니다.

두번째 문제의 경우, HyperVisor가 Trap&Emulate 방식으로 문제점을 해결합니다.

Trap & Emulate 방식이란?

• Guest OS은 기본적으로 non-root 모드로 동작합니다. 따라서, 특권 명령 등이 발생하면 Guest OS의 Kernel은 Trap을 발생시켜 하이퍼바이저에게 제어권을 넘겨줍니다.
• 하이퍼바이저는 Root 모드 동작이 가능하므로, 해당 동작들을 모두 처리 합니다.
• 처리가 완료되면 다시 kernel로 제어권을 넘겨줍니다.

Guest OS에서 별다른 수정 없이 활용할 수 있는 방식이지만, 하이퍼바이저가 모든 것을 처리해야하고 특히나 Trap이 엄청난 오버헤드를 유발하기 때문에 단점이 큰 방식입니다.

Trap의 오버헤드를 줄이기 위해 Binary Translation이라는 방식이 등장하였습니다.

• Binary Translation이란, Guest OS에서 특권 명령을 실행할 때 이를 하이퍼바이저가 하드웨어가 인식할 수 있는 명령으로 변환해주는 방식입니다.
• CPU가 명령에 대한 동작을 실행하는 방식이지만, 중간에 하이퍼 바이저가 번역하는 과정이 있습니다.

하지만 여전히 하이퍼바이저 단에서 많은 처리를 해주어야 하는 단점이 존재합니다.

이러한 전가상화의 성능적인 문제를 해결하기 위해 반가상화 방식이 등장하였습니다.

[반가상화 방식]

반가상화 방식은 Guest OS가 스스로가 Guest 임을 인지하는 가상화방식으로 Hyper call이라는 인터페이스 기술을 활용합니다.

Hyper call이란?

• Hyper call이란, Guest OS가 하드웨어가 인식할 수 있는 명령을 직접 전송하는 방식입니다.
• 하드웨어로 직접 전송하는 것은 아니지만 하이퍼바이저는 해당 명령을 전달하는 역할만 수행하므로 처리과정에서 발생하는 오버헤드가 없습니다.

이러한 동작이 되기 위해서는 Guest OS 커널의 수정이 필요합니다. 하지만, 하이퍼바이저는 각 Guest들의 리소스만 관리해주면 되므로 전가상화 방식보다 빠른 처리가 가능합니다.

[컨테이너형]

컨테이너는 호스트 OS에 논리적인 파티션을 만들어 애플리케이션이 구동하는데 있어 필요한 라이브러리, 자원 등을 사용할 수 있게 하는 기술 입니다.

기존 가상화 방식은 가상머신 이미지마다 별도의 OS가 필요했습니다. 하지만, 컨테이너 가상화는 이러한 컨테이너를 이용하여 OS를 가상화하여 여러 개의 컨테이너를 Host OS 위에서 동작시킵니다. 

따라서, 기존 가상화 방식보다 빠르고, 메모리를 적게 차지하며, Host OS 커널을 공유하기 때문에 오버헤드가 확연히 적은 방식입니다.

Reference

https://mangkyu.tistory.com/87

https://velog.io/@jiti/%EC%A0%84%EA%B0%80%EC%83%81%ED%99%94-VS-%EB%B0%98%EA%B0%80%EC%83%81%ED%99%94

https://suyeon96.tistory.com/53#Para%--Virtualization%---%EB%B-%--%EA%B-%--%EC%--%--%ED%--%---

https://tech.ktcloud.com/77

http://wiki.hash.kr/index.php/%EC%84%9C%EB%B2%84_%EA%B0%80%EC%83%81%ED%99%94#.ED.95.98.EC.9D.B4.ED.8D.BC.EB.B0.94.EC.9D.B4.EC.A0.80

https://kr.linkedin.com/pulse/container%EC%99%80-kubernetes-%EA%B8%B0%EC%88%A0-%EC%86%8C%EA%B0%9C-jun-hee-shin

[풀이 방법]

• dfs를 활용하여 완전 탐색 진행하였습니다.
• isPrime 함수를 구현하여 소수 판별을 하였습니다.

[풀이 코드]

import math

def isPrime(k):
    if k in (2, 3):
        return True
    if k in (0, 1) or k % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(k)) + 1, 2):
        if k % i == 0:
            return False
    return True


def dfs(prev, num, numbers, visited):
    for i in range(len(numbers)):
        if visited[i]:
            continue
        visited[i] = True
        if prev + numbers[i] not in num and isPrime(int(prev + numbers[i])):
            num.append(prev + numbers[i])
        dfs(prev + numbers[i], num, numbers, visited)
        visited[i] = False


def solution(numbers):
    numbers = list(numbers)
    visited = [False] * len(numbers)
    prev = ''
    num = []

    dfs(prev, num, numbers, visited)

    return len(set(list(map(int, num))))

코딩 테스트 연습을 하던 중 다음과 같은 상황을 맞이하여 엄청 당황했었습니다.

s = [1,2,3]
for i in range(len(s)):
    a = s
    print(a,s)
    a.pop()

위 코드를 동작 시켰을 때, 제가 기대한 결과는 a라는 list에만 변화가 생기는 것이었습니다. 하지만 다음과 같은 결과가 나온 것입니다.

a: [1, 2, 3] s: [1, 2, 3]
a: [1, 2] s: [1, 2]
a: [1] s: [1]

파이썬의 copy 개념이 제대로 잡혀있지 않아 발생한 문제였습니다.

copy가 동작하는 방식은 데이터가 immutable / mutable 인지 그리고 shallow copy / deep copy인지에 따라 달라집니다.

• immutable한 자료형은 int형, str형 과 같은 자료형이며 mutable한 자료형은 list, set, dictionary와 같은 자료형입니다.
• shallow copy에는 '=', [:] , copy.copy(), 객체.copy() 연산이 있습니다.

shallow copy일 경우, 다음과 같이 동작합니다.

서로 다른 변수가 같은 객체를 참조하고 있는 형태 입니다. 바로 문제가 발생했던 상황이죠.

변수가 immutable할 경우 이 상황에서 문제가 발생하지 않습니다. immutable한 자료형은 바뀌지 않기 때문에 데이터에 변화가 생길 경우 새로운 객체가 생성됩니다.

하지만 문제는 mutable한 자료형에서 발생합니다. mutable한 자료형은 말 그대로 바뀔 수 있기 때문에 객체 자체가 바뀌게 됩니다.

코드로 살펴보겠습니다.

<immutable한 자료형에서의 shallow copy>

a = 3
b = a

print('a,b:',a,b)
print('ID of a and b:',id(a),id(b))

# a,b: 3 3
# ID of a and b: 140423687498096 140423687498096

b = 5
print('a,b:',a,b)
print('ID of a and b:',id(a),id(b))

# a,b: 3 5
# ID of a and b: 140654810294640 140654810294704

처음에는 동일한 객체를 참조하고 있지만, 값이 변하게 되면서 b가 새로운 객체를 참조하고 있음을 알 수 있습니다.

<mutable한 자료형에서의 shallow copy>

listA = [1,2,3]
listB = listA

print('listA,listB:',listA,listB)
print('ID of listA and listB:',id(listA),id(listB))

# listA,listB: [1, 2, 3] [1, 2, 3]
# ID of listA and listB: 140613739648320 140613739648320

listB.append([1,2,3])
print('listA,listB:',listA,listB)
print('ID of listA and listB:',id(listA),id(listB))

# listA,listB: [1, 2, 3, [1, 2, 3]] [1, 2, 3, [1, 2, 3]]
# ID of listA and listB: 140613739648320 140613739648320

mutable한 자료형의 경우, 객체가 새로 생성되는 것이 아니라 객체 자체에서 변화가 생깁니다. 

저는 이러한 것을 고려하지 않고 '=' 을 통해 shallow copy를 하였기 때문에 문제가 발생했던 것이었습니다.

이러한 문제를 [:]을 통해 간단히 해결할 수 있습니다.(완벽한 방식은 아닙니다.)

listA = [1,2,3]
listB = listA[:]

print('listA,listB:',listA,listB)
print('ID of listA and listB:',id(listA),id(listB))

# listA,listB: [1, 2, 3] [1, 2, 3]
# ID of listA and listB: 140613739648320 140613739648320

listB[0] = 99
print('listA,listB:',listA,listB)
print('ID of listA and listB:',id(listA),id(listB))

# listA,listB: [1, 2, 3] [99, 2, 3]
# ID of listA and listB: 140457913193792 140457913193600

listB.append([1,2,3])
print('listA,listB:',listA,listB)
print('ID of listA and listB:',id(listA),id(listB))

# listA,listB: [1, 2, 3] [99, 2, 3, [1, 2, 3]]
# ID of listA and listB: 140457913193792 140457913193600

listA = listB[:]

listB[3].append(999)

print('listA,listB:',listA,listB)
# ID of listA and listB: 140524217406784 140524217406592
# listA,listB: [99, 2, 3, [1, 2, 3, 999]] [99, 2, 3, [1, 2, 3, 999]]

보시면 [:]를 활용할 경우, listA와 listB의 주소가 다르기 때문에 Deep copy로 보이기도 합니다.

하지만 마지막을 보시면 [1,2,3] 객체에 999를 append하였을 때 두 리스트 모두 반영되는 것을 알 수 있습니다.

따라서, 완벽한 방식은 아니지요. 하지만 때에 따라 활용할 수는 있을 것 같습니다.

해결 방안

• 자료형을 고려하여 shallow copy와 deep copy를 적절히 사용하는 것이 가장 좋은 방법이라고 생각합니다.

Reference

https://blockdmask.tistory.com/576

[문제 풀이]

-DFS를 활용하여 완전탐색을 진행하였습니다. 코드의 dfs 함수와 같이 방문했다가 나올 경우, (visited = false)를 통해 방문하지 않은 걸로 처리해주어 완전 탐색이 가능하도록 하였습니다.

-완전 탐색 시 가장 깊게 들어간 경우를 측정해야하므로, depth 설정을 통해 모든 경우에서 가장 깊게 들어간 경우를 측정해주었습니다.

[풀이 코드]

def dfs(k, answer, depth, dungeons, visited):
    answer = max(answer, depth)
    for i in range(len(dungeons)):
        if visited[i] or k < dungeons[i][0]: continue

        visited[i] = True
        answer = dfs(k - dungeons[i][1], answer, depth + 1, dungeons, visited)
        visited[i] = False
    return answer


def solution(k, dungeons):
    visited = [False] * len(dungeons)
    depth = 0
    answer = -1
    answer = dfs(k, answer, depth, dungeons, visited)

    return answer

[문제 풀이]

• 두 큐의 합이 같게 되려면 모든 원소의 평균이 정수여야 하며, 각 큐의 합이 평균과 동일하게 만들어주면 됩니다.
• 문제에 대한 설명과 같이, 시간복잡도을 낮추고 큐의 특성을 활용하기 위해 deque()를 사용했으며, 원소의 합이 큰 쪽에서 작은 쪽으로 원소를 보내주도록 구현하였습니다.
• 이때 매번 큐의 합을 구해주는 것이 아닌 구해놓은 합에 대하여 +- 연산을 통해 시간 복잡도를 낮췄습니다.
• 마지막으로 두 개의 큐가 비지 않고 큐의 길이 * 2번 만큼 이동하게 된다면 원 상태가 되므로 해당 조건을 추가하였습니다.

[풀이 코드]

from collections import deque


def solution(queue1, queue2):
    answer = 0
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    s = (sum1 + sum2) / 2

    if s - int(s) > 0 or max(queue1) > int(s) or max(queue2) > int(s):
        return -1

    dq1 = deque(queue1)
    dq2 = deque(queue2)

    while dq1 and dq2 and sum1 != sum2 and answer <= 600000:
        if sum1 < sum2:
            v = dq2.popleft()
            dq1.append(v)

            sum1 += v
            sum2 -= v
        else:
            v = dq1.popleft()
            dq2.append(v)

            sum1 -= v
            sum2 += v
        answer += 1

    return answer if sum1 == sum2 else -1

Interrupt란?

CPU가 동작하고 있을 때, 입출력 연산과 같이 CPU가 대기해야하는 작업이 끝났을 때 또는 소프트웨어적 예외 상황이 발생하여 처리가 필요할 때 보내는 신호 입니다.

Interrupt를 사용하는 이유?

• I/O 이벤트 상황의 처리 : 입출력 연산이 CPU의 연산 속도 보다 현저히 느릴 뿐만 아니라 모종의 이유로 CPU가 대기해야하는 상황에서 CPU가 아무 일도 하지 않고 있을 수 없기 때문입니다. 예를 들어, 사람의 입력이 필요한 상황이 발생하면 running 중이던 process를 wait/ready 상태로 바꾸고 다른 작업을 수행하며 다시 running 시킬 때 interrupt를 통해 상황이 완료되었음을 CPU에게 알려주는 역할을 수행합니다.                                                                             

• 예외상황의 처리: 우선순위가 앞서는 예외상황이 발생하였을 때 현재 작업을 멈추고 예외상황을 처리하게 하기 위함도 있습니다.

• 선점형 스케쥴링 구현: 선점형 스케쥴링이란, 우선 순위가 높은 process를 먼저 동작 시키는 것입니다. 즉, 기존에 CPU가 하던 작업이 있다면 이를 중단시킨 후 우선 순위가 높은 process를 동작 시키기 위함입니다.

Interrupt 동작과정

• CPU가 어떠한 작업 중에 system call을 통해 인터럽트가 발생합니다.
• CPU는 현재 진행 중인 기계어 코드를 완료하고, 현재 수행 중이던 process의 상태를 PCB(Process Control Block)에 저장합니다. (수행 중이던 Memory 주소, 레지스터 값 등등)
• PC에 다음에 실행할 명령어 주소를 저장합니다.
• 인터럽트 벡터를 읽고 ISR 주소를 얻어 ISR(Interrupt Service Routine)으로 점프하여 작업을 수행합니다.
• 이때 발생한 인터럽트 번호를 토대로 IDT(Interrupt Descriptor Table)에서 인터럽트 번호에 해당하는 함수를 호출하여 작업을 처리합니다.
• 작업이 완료되면 PCB에서 수행중이던 process 상태를 복원하고, 인터럽트가 해제되면 PC에 저장된 주소로 다시 점프해 하던 작업을 수행합니다.

Reference

https://velog.io/@tnddls2ek/OS-%EC%9D%B8%ED%84%B0%EB%9F%BD%ED%8A%B8-Interrupt

[풀이 방법]

• 해당 문제는 주어진 cards라는 리스트에서 Circular한 그룹이 몇개가 있는지, 각 길이가 어떠한지 알아야 하는 문제입니다.
• 배열 요소를 따라가는 것은 Circular한 성질을 가지고 있으므로, 1개 이상의 그룹이 만들어집니다. 
• 또한 cards에는 중복된 요소가 들어가 있지 않으므로, 모든 요소를 탐색(즉, 모든 그룹을 탐색)하게 되면 배열의 모든 index를 탐색하게 됩니다.
• 따라서, 배열의 모든 요소가 탐색될 때까지 문제 조건에 맞춰 그룹화를 해주었습니다.

[풀이 코드]

# 두 개의 그룹의 곱이 최대가 되는 값을 찾아야한다.
# 그룹은 어떤 수로 시작해도 같은 그룹이 만들어진다.
def solution(cards):
    answer = 0
    group = []
    isopen = [-1] * len(cards)
    rnd = 1
    while isopen.count(-1) != 0:
        idx = isopen.index(-1)
        isopen[idx] = rnd
        while True:
            idx = cards[idx] - 1
            isopen[idx] = rnd
            if isopen[cards[idx] - 1] == rnd:
                break
        group.append(isopen.count(rnd))
        rnd += 1

    group.sort()
    return 0 if len(group) <= 1 else group[-1] * group[-2]

[풀이 방법]

• order에는 택배가 실려야할 순서가 있습니다. order = [4,3,1,2,5] 라면 4번째 상자, 3번째 상자, 1번째 상자 순으로 order에 맞춰 실어야 합니다.
• 이때, 순서에 맞지 않는 택배가 왔을 경우를 위한 보조 컨테이너가 있습니다. 보조 컨테이너는 stack 구조 입니다.
• 택배는 무조건 첫번째부터 순서대로 나오므로, for문을 통해 탐색을 해주었습니다. 문제 조건에 맞춰 나오는 상자의 순서와 order가 맞지 않을 경우 stack에 넣었습니다.

*이때 핵심이 되는 경우는 for문 안에 while문 입니다. 보조컨테이너 역할을 하는 q가 비어있지 않을 경우, 매 상황에 처리될 수 있는지 확인하는 코드입니다.

[풀이 코드]

from collections import deque


def solution(order):
    answer = 0
    q = deque()
    now = 0

    for i in range(len(order)):
        if i + 1 != order[now]:
            q.append(i + 1)

        if i + 1 == order[now]:
            answer += 1
            now += 1

        while q and q[-1] == order[now]:
            q.pop()
            answer += 1
            now += 1

    return answer

[문제 풀이]

• enemy 배열을 앞에서 탐색하며 무적권을 먼저 사용하는 방법을 활용했습니다.
• 하지만 사용했다해서 끝이 아니라 값을 비교하면서 무적권 안에 현재 마주한 적 수보다 작은 라운드에 무적권이 사용되었다면 현재 라운드에 무적권을 사용한 것으로 갱신해주었습니다.

[풀이 코드]

import heapq


def solution(n, k, enemy):
    answer = 0
    invinc = [0] * k  # 무적권

    for i in range(len(enemy)):
        # invinc[0] 랑 비교하면서 invinc 대체
        if enemy[i] > invinc[0]:
            n -= heapq.heapreplace(invinc, enemy[i])
        else:
            n -= enemy[i]
        if n < 0:
            return i
    return len(enemy)  # 만약 배열이 다 돌고 나서도 여기로 나온다면 n > 0 이라는 뜻으로 무조건 clear