[TIL][Krafton Jungle] 3주차 - (3) : 그리디 + DP / 컴퓨터 시스템

오늘은 어제 하던 Greedy를 문제에 적용하면서 경험한 서사와 컴퓨터 시스템 약간을 추가해서 작성해 보겠다.

 

 

 

---

BaekJun - # 11047 : 동전 0 (그리디 탐색법)

출처 : https://www.acmicpc.net/problem/11047

11047번: 동전 0

동전 0의 문제를 처음 풀려고 생각했을 때는, 굉장히 쉽다고 생각했다.

거스름돈을 계산할 줄 아는 사람이라면 코드를 짜는 건 어렵지 않다.

 

하지만 문제는 시간 초과에서 발생했다.

 

왜 이 문제가 전형적인 그리디 탐색법을 시작할 때 맛봐야 하는지,

그리디 알고리즘이 무엇인지 조금은 더 와닿게 해줬다.

 

많은 사람들은 문제에서 거스름돈을 걸러주는 생각을 하며

초기에 받은 돈의 가치보다는 낮은 단위의 동전단위들만 모아

큰 순으로 리스트에서 빼어 목표 금액에다 계속 마이너스 하면서

1개씩 동전을 셀 것이라 생각한다.

(아니면 걍 내가 멍청한 걸지도)

 

하지만 100000만원을 목표로 하는 금액에서 100원짜리로 센다면?

극단적인 상황을 생각해보니

이건 목표금액에서 빼는 문제가 아니라 단위금액을 목표금액에다 나누는 문제였다.

 

from collections import deque
import heapq
import re
import sys

n, cost = map(int,sys.stdin.readline().strip().split())
coinList = []

for i in range(n):
    coin = int(sys.stdin.readline())
    if coin <= cost:
        coinList.append(coin)


coinList.sort()
count = 0

def sol(cost):
    global count
    while coinList:
        thisCoin = coinList.pop()
        if cost % thisCoin == 0:
            return count+(cost//thisCoin)
        else:
            count += cost // thisCoin
            cost = cost % thisCoin
                


print(sol(cost))

 

이문제는 실제로 풀어보면 굉장히 쉽고, 내가 무엇을 더 개선할 수 있는지 파악하기 쉽다.

 

이 문제를 통해 다른 더 어려운 Greedy의 문제에서는

특정 Edge case(사람들이 잘 생각하지 못하는 예외의 상황이나 극단적인 상황)에 주의하여

풀어내야 한다고 생각이 들었다.

 

---

 

BaekJun - #1931 : 회의실 배정(Greedy)

문제 출처 : https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

문제의 내용을 요약하면,

여러 시간대의 회의가 있는데 이 회의중에 곂치는 시간 없이 회의실을 최대한 여러개의 회의를 진행하는 방법을 찾고 그 회의의 갯수를 출력하는 문제이다.

 

회의를 진행하는 팀의 회의가 끝나는 일정이 제일 늦는 팀은 최대 2^31승의 시간대까지 있으므로 모든 시간을 배열로 나타내서 True False로 체크하는 방법은 불가능하다.

 

따라서 나는 저번주에 공부한 스위핑과 비슷한 개념을 이 문제에 적용해보았다.

 

가장 먼저 Greedy 문제니까 문제 파악을 하는 것이 중요했다.

회의를 가장 많이 시간 내에 진행시키려면 가장 회의시간이 덜 걸리는 회의를 먼저 배정해줘야 되지 않을까?

 

그래서 시작 시간과 끝시간의 차가 적은 순으로 배정을 해보았다.

근데 듬성듬성 회의시간이 짧은 순으로 배정을 하고 나니까 더 회의시간이 길어지면 그 사이에 끼어넣을 수 있는지에 대한 여부를 판단하기가 힘들었다.

 

그래서 시작시간으로 오름차순을 한 뒤, 2순위 정렬로 끝마치는 시간을 오름차순 정렬한다.

그리고 (시작시간,끝시간) 의 회의내용을 리스트에 넣다가,

만약 다음 회의가 이전 회의보다 일찍 끝난다면

가장 최근에 들어간 리스트를 pop으로 빼내고 지금 회의를 리스트에 넣는 식으로 문제를 풀었다.

 

이게 정확하게 스위핑인지는 모르겠지만, 왼쪽에서 오른쪽으로 한번만 스캔한다고 생각하면 스위핑 문제랑 조금 비슷하다고 생각했다.

 

from collections import deque
import sys
import heapq

n = int(sys.stdin.readline())
heap = []
heapq.heapify(heap)
endTime = 0
for i in range(n):
    start , end = map(int,sys.stdin.readline().split())
    heapq.heappush(heap,(start,end))
bookingLog = []
while heap:
    start, end = heapq.heappop(heap)
    if not bookingLog:
        bookingLog.append([start,end])
    else:
        if bookingLog[-1][1] > end:
            bookingLog.pop()
            bookingLog.append([start,end])
        elif bookingLog[-1][1] <= start:
            bookingLog.append([start,end])

# print(bookingLog)
print(len(bookingLog))

 

힙을 굳이 사용할 필요가 없이, 리스트로 받아 정렬한 뒤 pop을 하는 형식으로 코드를 짜도 되지만,

그냥 내부 정렬 기능이 있는 heap으로 코드를 간결하게 해보고 싶어서 이렇게 코드를 짰다.

 

---

 

BaekJun - #1904 : 01타일 (동적 계획법 : DP)

문제 출처: https://www.acmicpc.net/problem/1904

1904번: 01타일

 

문제를 파악하는게 여전히 어렵다.

DP는 초기 베이스 케이스를 기록해보고 어떤 규칙이 있는지 생각해 내는 것이 중요하다.

 

N = 1일 때, 나올 수 있는 경우는

1

한개

 

N = 2일 때, 나올 수 있는 경우는

11 , 00

두개

 

N = 3이상 부터는 1과 2의 조합으로 수열을 만들 수 있다는 걸 알 수 있다.

 

그 규칙을 잘 생각해보면

'1'은 크기 1개를 차지하므로 N-1의 규칙에 붙일 수 있고,

'00'은 크기 2개를 차지하므로 N-2 규칙에 붙일 수 있다.

 

근데 n=2일때 수열인 '00'에는 1을 양쪽에 붙여야 하지만 , '11'에 1을 양쪽에 붙이면 중복되는 경우가 발생한다.

1'11' 과 '11'1 은 같은 수열이기 때문이다.

 

그런데 잘 생각해보면

n-2의 오른쪽에 00을 붙인 수열이 양쪽에 붙이는 경우 중 하나를 커버해준다.

 

예를 들어 '00' 에 1'00' 과 '00'1 을 위해 n-1 수열의 경우에다가 2배 해줘야 할 것 같지만,

n-2 수열에서 1'00'이 포함되기 때문에 왼쪽에 1을 붙이는 케이스를 고려할 필요가 없다.

 

즉 따라서

n = 3인 경우는

n-2 = 1 인 수열 오른쪽에 '00'을 붙인 케이스 + n-1 = 2인 수열 오른쪽에 '1'을 붙인 케이스를 더하면

n = 3일때의 수열은 모두 찾을 수 있다.

 

이 규칙을 연산으로 생각해보면

f(1) = 1

f(2) = 2

f(3) = f(1) + f(2) = 3

-> f(n) = f(n-1) + f(n-2) 의 규칙을 만들어 낼 수 있다.

 

코드는 다음과 같다.

import sys

n = int(sys.stdin.readline())
result = [1,2]

for i in range(2,n):
    result.append((result[i-1]+result[i-2])%15746)

print(result[n-1]%15746)

 

해당 규칙을 생각해 내는데 중복때문에 너무 어려웠다.

DP는 푸는 방법이 Greedy보다는 정형화 되어있어서 많이 풀어봐야 될 것 같다.

 

---

컴퓨터 시스템 정리

 

부호 확장(Sign-extension) vs Zero-extension

책을 읽다보니 데이터를 메모리와 레지스터에 저장하거나 옮기면서 부호 확장과 0으로 확장하는 것에 대해 이해가 잘 안되어서 정리하겠다.

 

부호 확장은 MOV 명령어로 값을 레지스터로 복사할 때,

부호 있는 정수는 데이터의 마지막 최상위 비트가 부호를 나타내는데,

이 부호를 유지하기 위해 더 확장된 비트에 채워준다.

 

부호가 있는지의 여부는 가장 높은 비트(최상위 비트)를 사용해서 나타내는데, 

예를 들면 8비트의 정수 -1은 이진수로 '11111111'이다.

 

이때 16비트 레지스터에 복사할 때, 부호확장을 수행하면 '11111111 11111111'로 확장된다. 

 

 

0으로 채우기(Zero Extension)은 부호 없는 정수 데이터(Unsigned int) 혹은 논리 값을 다룰 때, 사용할 수 있다.

예를 들면, 8비트의 부호없는 정수 255는 '11111111'인데,

이 값을 16비트 레지스터로 확장할 때, 부호가 없다는 것을 표현하기 위해

'00000000 11111111'로 확장한다.

 

이렇게 하면 데이터의 크기를 유지하면서 16비트로 확장된다.

 

정리하면, 부호확장과 zero extension은 레지스터처럼 용량이 큰 저장소로 옮겨지면서 남는 비트 자리에 

데이터의 의미의 보존과 크기 확장을 동시에 해결하기 위해 사용한다.

 

---

인스트럭션 명령어 MOV의 접미사는 무엇을 가리키는가 ?

 

인스트럭션 mov 뒤에 붙는 (b , w , l , q) 는 도대체 누구에 맞춘 기준인가? 에 대해서 의문점을 가지게 되었다.

 

인스트럭션 명령어 MOV 시 첫번째 인자가 소스 오퍼랜드, 두번째 인자가 목적어 오퍼랜드인데

 

MOVb 일 경우 소스 오퍼랜드가 byte 단위라는 건지,

목적어 오퍼랜드가 byte 단위라는 건지 사람 개 헤깔리게 한다. (책 = 속터짐)

 

그래서 연습문제를 비롯해서 예제까지 분석해 본 결과(+ 책의 개소리를 분석해본 결과)

'왼쪽 데이터를 오른쪽 참조로 이동한다' 의 의미인 MOV 인스트럭션의 접미사는 오른쪽이나 왼쪽 오퍼랜드에 맞춰져있는게 아니고, 둘 중 하나가 레지스터이기 때문에 레지스터에 맞춰진다.

 

한글 번역 책 177페이지 하단을 보면 "메모리의 데이터를 바로 메모리로 참조하지 못하고, 레지스터를 거치는 방식으로 2단계의 인스트럭션을 사용해야 한다." 고 되어있다.

 

따라서 한 인스트럭션엔 무조건 레지스터(혹은 $ 표기가 된 Immediate 상수)를 거친다는 말이다.

그래서 mov의 바이트 단위를 나타내는 접미사는 레지스터 저장소 크기에 맞춰진다.

 

그러면 의문점이 든다.

 

레지스터에서 레지스터로 mov가 발생하면 어디를 기준으로 해야 하는가?

 

소스 오퍼랜드의 레지스터 속 값이 목적 오퍼랜드의 레지스터로 이동되는데,

그런 상황에서는 목적 오퍼랜드의 크기에 맞춘다.

(이는 위에 설명한 부호확장과 zero-extension을 위해서 이기도 함.)

 

하지만 데이터 손실을 방지하기 위해서는 레지스터 to 레지스터 mov 시 둘다 바이트 크기가 같은 레지스터를 사용하는 것이 올바르다고 한다.

 

 

또다른 의문점은 상수 to 메모리이다.

 

예를들어 mov $0x08 , (%rsp) 라면

immediate 상수를 , rsp 레지스터 안에 들어있는 메모리 주소를 참조하여

메모리로 저장시키라는 인스트럭션이다.

 

여기선 레지스터가 없다.

이럴 때는 간단하게 immediate 상수값에 맞춰주면 되는데,

0x표기는 오른쪽 수가 16진수 숫자로 표기되었다는 뜻이기 때문에

0x08은 0000 1000 을 뜻한다. 이는 8bits. 즉, 1byte이다.

 

따라서 movb $0x08 , (%rsp) 라고 표기해주면 된다.

 

---