[TIL] 그리디 문제 풀이 + 기계 수준 표현1

1. 그리디 문제 풀이

1. 1931번 - 회의실 배정

import sys

N = int(sys.stdin.readline())
# meeting[0] : 시작 시간 / meeting[1] : 끝나는 시간
meeting = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

meeting.sort(key= lambda x : (x[1], x[0]))

count = 1
prev = meeting[0][1] # 앞 회의 끝나는 시간
for i in range(1, N) :
    # 만약 현재 회의 시작 시간이 앞 회의 시간보다 크거나 같으면
    if prev <= meeting[i][0] :
        count += 1
        prev = meeting[i][1]

print(count)

회의실을 최대한 많이 사용하기 위해 회의를 선택해야한다.
이때 먼저 해야할 것은 끝나는 시간이 빠른 순으로 선택해야 다음 회의를 선택할 수 있기 때문에
각 회의의 시작 시간과 끝나는 시간이 존재하므로 끝나는 시간을 기준으로 먼저 정렬한다.

앞선 회의 끝나는 시간보다 다음 회의 시작 시간이 이후일 때 새로운 회의를 시작한다.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
위의 문제 조건에 의해 앞선 회의의 끝나는 시간과 다음 회의의 시작 시간이 같을 수 있다.

---

2. 1946번 - 신입사원

import sys

T = int(sys.stdin.readline())

for _ in range(T) :
    N = int(sys.stdin.readline())
    people = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    # 서류 심사 성적을 기준으로 정렬
    people.sort()
    
    count = 1 # 서류 1등은 우선 무조건 선발 가능
    interview = people[0][1] # 비교할 면접 성적
    for i in range(1, N) :
        # for문의 지원자들은 서류가 1등의 성적보다 무조건 낮기 때문에
        # 적어도 면접 성적이 더 높아야한다.
        if  interview > people[i][1] :
            count += 1
            interview = people[i][1]
    print(count)

서류와 면접 성적 중 적어도 하나는 다른 사람보다 떨어지면 안된다.
우선 서류 성적을 기준으로 정렬했다.
그럼 서류 1등은 일단 무조건 다른 사람보다 서류는 제일 높아 무조건 선발된다.
이 다음 사람부터는 서류 성적은 무조건 1등보다 낮으므로 면접 성적이 높아야한다.

반복문을 반복하다보면 늘 전 사람보다 다음 사람의 서류성적은 낮기 때문에
면접 성적을 비교해가면서 선발 여부를 판단한다.

---

3. 1700번 - 멀티탭 스케줄링

import sys

N, K = map(int, sys.stdin.readline().split())
elec = list(map(int, sys.stdin.readline().split()))

plug = []
count = 0

for i in range(K) :
    if elec[i] in plug : # 이미 꽂여있을 경우
        continue
    elif len(plug) < N : # 꽂여있지 않고 멀티탭 사용 가능할 때
        plug.append(elec[i])
    else : # 꽂여있지 않고 멀티탭도 다 사용중일 때
        flag = True # 현재 플러그에 꽂여있는 모든 것들이 다음에 사용된다 = True
        for p in plug :
            # 현재 플러그에 꽂여있는 것이 다음에 사용될 일이 없으면 뽑는다.
            if p not in elec[i:] :
                plug.remove(p)
                count += 1
                plug.append(elec[i])
                flag = False
                break
        # 만약 플러그에 꽂인 모든 번호가 나중에 다 사용하는 것이라면
        if flag :
            last = 0 # 플러그에 있는 것 중 가장 나중에 사용될 번호의 인덱스
            for p in plug :
                tmp = elec[i:].index(p)
                if tmp > last :
                    last = tmp
            # elec[i:]를 기준으로 인덱스를 찾았기에 elec에 접근할 때 last+i 로 접근한다.
            plug.remove(elec[i+last])
            count += 1
            plug.append(elec[i])
                 
print(count)

코드 동작
1. 이미 멀티탭에 존재할 경우 pass
2. 멀티탭에 존재하지 않는데 멀티탭에 자리가 남아있으면
    → 멀티탭에 꽂는다.
3. 멀티탭에 존재하지 않는데 멀티탭마저 다 찼을 경우 → 하나를 빼야한다.
    → 멀티탭에 존재하는 것 중 앞으로 사용할 일이 없는 것이 존재하면 제거
    → 멀티탭에 존재하는 것들 모두 나중에 사용하면 그 중 가장 나중에 사용하는 것 제거

주의할 점은 나는 반복문을 돌면서 elec에 있는 것을 제거하면서 하지 않아서
elec[i:] 를 기준으로 안에서 반복문을 돈다. 그래서 3번의 2번 경우에서 elec[i+last] 로 접근해야한다.

---

2. 프로그램의 기계수준 표현

1. 어셈블리어

 기계어와 일대일 대응이되는 컴퓨터 프로그래밍 저급언어
이는 바이너리 기계어 코드 형식과 유사하지만 좀 더 읽기 쉬운 텍스트 형식의 코드이다.

<출처> https://ko.wikipedia.org/wiki/어셈블리어

• 기계 수준 프로그래밍 특징
  • Instruction Set Architecture (ISA)
    • 프로세서의 상태, 인스트럭션의 형식에 대한 각 인스트럭션들의 영향들 정의
    • 하나의 인스트럭션이 다음 인스트럭션의 실행 전에 완료되는 순차적인 실행을 하는 것처럼 동작을 설명
    • 하드웨어는 훨씬 더 정교해서 여러 인스트럭션을 동시에 실행하지만, ISA에 의한 순차적 동작과 일치하는 전체 동작을 보이도록 해주는 안전장치를 사용한다.
    • PC(Program Counter) : 실행할 다음 인스트럭션의 메모리 주소를 가리킨다.
  • 가상주소 : 메모리가 매우 큰 바이트 배열인 것처럼 보이게 하는 메모리 모델 제공
    • 운영체제가 이 가상 주소 공간을 관리해서 가상 주소를 실제 프로세서 메모리 상의 물리적 주소 값으로 번역
  • 기계어 코드는 메모리를 단순히 바이트 주소지정이 가능한 큰 배열로 본다.
    • 배열과 구조체 같은 연결된 데이터 타입들은 기계어 코드에서는 연속적인 바이트들로 표현
  • 하나의 기계어 Instruction은 매우 기초적인 동작만 수행

2. 정보 접근하기

• 범용 레지스터
  • 정수 데이터와 포인터를 저장하는데 사용
  • 일반적인 프로그램에서 서로 다른 레지스터들은 서로 다른 목적으로 이용된다.
  • 일련의 표준 프로그래밍 관습에 의해 스택을 관리하고 함수의 인자를 넘겨주고, 함수에서 값을 리턴하고, 로컬데이터와 임시 데이터를 저장하기 위해 어떤게 레지스터가 사용되는지가 정해진다.
• operand specifier (오퍼랜드 식별자)
  • operand = 피연산자 = 연산자의 연산 대상(https://ko.wikipedia.org/wiki/피연산자)
  • 대부분의 인스트럭션은 하나 이상의 오퍼랜드를 가진다.
  • 연산을 수행할 소스 값과 그 결과를 저장할 목적지 위치를 명시
    • source :  상수, 레지스터나 메모리에서 읽을 수 있다.
    • destination : 레지스터나 메모리에 저장할 위치
  • type
    • immediate : 상수 (표현 : $Imm)
    • register : 레지스터의 내용 (표현 : Ra)
    • 메모리 참조 : 유효 주소라고 부르는 계산된 주소에 의해 메모리 위치에 접근