TIL - 2024/04/09

박상우·2024년 4월 9일

TIL

📝 TIL

목록 보기

16/21

CSAPP

레지스터

프로세스 레지스터(processor register) 또는 레지스터는 컴퓨터의 프로세서 내에서 자료를 보관하는 아주 빠른 기억 저장소이다. 일반적으로 현재 연산에 사용되는 값을 저장하는데 사용된다.

레지스터의 종류

데이터 레지스터 : 정수 값을 저장할 수 있는 레지스터
주소 레지스터 : 메모리 주소를 저장해서 메모리 접근에 사용되는 레지스터. 주소를 사용하는 것이 아닌 조작을 위해서 색인레지스터를 사용하기도 한다.
범용 레지스터 : 데이터와 주소를 모두 저장할 수 있는 레지스터
부동소수점 레지스터 : 부동소수점 값을 사용하기 위해 저장
상수 레지스터 : 0 or 1등 고정된 값을 저장하는 레지스터
특수 레지스터: 프로그램의 상태를 저장한다.
- 명령 레지스터: 현재 실행중인 명령어를 저장한다.
- 색인 레지스터: 피연산자의 주소를 계산하는데 사용된다.

프로세서 내부 레지스터 구성

PC(프로그램 카운터) : 다음 실행할 명령어의 주소를 가지고 있다.
IR (명령어 레지스터) : 현재 수행중인 명령어를 가지고 있다.
MAR (메모리 주소 레지스터) : 메모리를 읽어오거나 메모리에 쓰기 위한 주소를 가지고 있다.
MBR (메모리 버퍼 레지스터) : 메모리로 부터 읽어온 데이터 또는 메모리에 써야하는 데이터를 가지고 있다.
I/O AR (입출력 주소 레지스터) : 입출력 장치에 따른 입출력 모듈의 주소를 가지고 있다.
I/O BR (입출력 버퍼 레지스터) : 입출력 모듈과 프로세서 간의 데이터 교환을 위해 사용된다.

3.7 프로시저

3.7.4 스택에서의 지역저장공간

지역 데이터가 메모리에 저장되어야하는 경우

레지스터 수가 부족한 경우
지역 변수 연산자에 ‘&’가 사용되었고, 이 변수의 주소를 만들어야하는 경우
일부 지역 변수들이 배열 혹은 구조체 여서 배열이나 구조체 참조로 접근되어야하는 경우

프로시저는 스택 포인터를 감소시켜 스택 프레임에 공간을 할당한다.

3.8 배열의 할당과 접근

C에서 배열은 스칼라 데이터를 큰 자료형으로 연계시키는 수단이 된다.

💡 **스칼라 데이터 (Skalar Data)** : 단 하나의 데이터만 저장할 수 있는 데이터 타입. 상반되는 의미로 컴포지트 타입(Composite Type)이 있다.

C에서 배열 원소들에 대한 포인터를 만들고 포인터를 간 연산이 가능하다는 점이 특이하다. 이 부분은 나중에 기계어로 번역될 때 주소 계산으로 사용된다. 최적화된 컴파일러는 배열의 인덱스를 사용할 때 필요한 주소 계산을 단순화 할 때 특히 우수한 성능을 보인다.

3.8.1 원리

자료형 T와 정수형 상수 N에 대해서 다음 과 같이 선언할 수 있다.

T \;\; A[N]

x_A \; : 시작하는 위치 (포인터 \; 값) \\ L : 자료형 \; T의 크기 \\ L * N : 배열의 메모리 \\ x_A + L * i : 배열의 원소 i의 주소

3.8.2 포인터 연산

\text{\&Expr} : 객체의 주소를 주는 포인터 \\ \text{*AExpr} : 주소에 위치한 값

3.8.3 다중 배열

int A[5][3]
// 다음과 같다.
typedef int row3_t[3];
row3_t A[5];

T \;\; D[R][C]; \\ \\ \text{\&D[i][j]} = x_p + L(C * i + j) : 배열 원소 \; D[i][j]는\; 메모리 \; 주소

알고리즘 풀이

1946번 - 신입사원

Link : https://www.acmicpc.net/problem/1946

신입사원 문제의 풀이 방식은 위 그림과 같다.

2가지 과목에 대해서 어떤 한 명에게도 뒤떨어지면 떨어지는 조건에서 한쪽을 정렬해주어 그 과목에 대해서는 미리 크기 비교를 마친 상태에서 시작한다. 이때 기준은 어느 쪽이 되어도 상관 없다. 여러 조건을 비교해야하는 상황에서 정렬을 통해 비교 조건을 없애주는 방식이다.
그림에서는 x과목을 기준으로 정렬해주었다.
이제 y과목에 대해서만 차례대로 앞사람과 비교해주면 된다. 이때 앞사람의 성적보다 낮은 성적이 나오는 경우 탈락이 확정된다. x 과목에 대해서는 이미 오름차순으로 정렬되어있는 상태에서 나보다 x성적 순위가 높은 상대와 y 과목을 비교했는데 그 성적이 낮다면 그건 x, y 과목 양쪽 모두 특정 한사람에게 졌다는 뜻이 된다.

C와 E를 비교해보면, C와 E는 이미 x 과목 정렬로 인해서 C가 더 앞쪽에 있는 상황이다. 그 상태에서 y과목을 비교했을 때 E가 더 낮은 성적을 보이고 있기 때문에 E는 떨어지게된다.
정렬하지 않은 과목에 대해서 비교를 하는 과정에서 만약 가장 높은 성적을 만나게 되면 비교를 더이상 하지 않아도 된다. 동일 성적이 없다는 조건이기 때문에 이 성적을 이길 수 있는 사원은 뒤에 존재하지 않기 때문이다.

Code

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
  N = int(input())

  employees = []

  for i in range(N):
    employees.append(list(map(int, input().split())))

  employees = sorted(employees)
  
  total = 0
  min_value = N + 1
  for e in employees:
    _, val = e

    if min_value > val:
      total += 1
      min_value = val

    if min_value == 1:
      break

  print(total)

왜 그리디문제일까?

접근방식이 정답인지는 모르겠지만 정렬한 후 남은 과목의 성적을 비교하는 과정에서 그 한 번의 비교를 통해 결정한 합/불합 결과가 더 이상의 비교 없이 바로 결정되고, 이 후 전체적인 결과(total)로 봤을 때 최적의 값이 되었기때문이 아닐까 한다.

9084번 - 동전

Link: https://www.acmicpc.net/problem/9084

동적 프로그래밍의 대표적인 예시인 배낭 문제와 비슷한 느낌의 문제였다. (근데 못 품..)

전체적인 느낌은 현재 추가한 동전에 대해서 동전 보다 작은 값인 경우, 동전을 사용하는 경우, 동전을 사용하지 않는 경우로 나누어 고려하고, 이전 값을 활용하여 빠르게 계산이 가능하다.

우선 표를 만들어 행이 하나씩 추가될 때 마다 그 다음 동전을 추가하여 가능한 조합의 횟수를 누산하면 된다.

먼저 2원의 경우 2원으로 계산할 수 있는 금액에 1로 표기해준다. 이때 0원인 경우에도 1을 넣어주는데, 동전을 0개 조합하면 0원을 만들 수 있다는 개념으로 1을 추가해준다.

2, 3원을 사용하는 경우, 0, 1, 2원의 경우 3원의 동전을 사용할 수 없는 케이스기 때문에 2원만 사용하는 경우와 동일하다. 3 ~ 12원인 경우 두가지 값을 고려해서 더해주어야한다.

2,3 동전 [ n원 ] = 2 동전 [ n원 ] + 2, 3 동전 [ n - 3원 ]

이때 모든 횟수를 고려하는 문제이기 때문에 두 값을 더해주는 것이다.

이런 과정을 반복해서 테이블을 완성하면 5(가지)라는 답을 구할 수 있다.

Code

import sys

input = sys.stdin.readline

T = int(input())

test_case = []

for _ in range(T):
  N = int(input())
  coins = list(map(int, input().split()))
  price = int(input())

  test_case.append([
    N,
    coins,
    price,
  ])

total = 0

for c in test_case:
  N, coins, price = c

  dp = [ [ 1 ] + [ 0 ] * price for _ in range(len(coins)) ]

  dp = [ 1 ] + [ 0 ] * price

  for i in range(len(coins)):
    for j in range(1, price + 1):
      if j - coins[i] >= 0:
        dp[j] += dp[j - coins[i]]

  print(dp[-1])

박상우

나도 잘하고 싶다..!

이전 포스트

TIL - 2024/04/08

다음 포스트