Published 2022. 11. 5. 18:48

크래프톤 정글 1주차 TWIL..

dev-log/크래프톤 정글

this week i learned..

1주차 학습 내용

컴퓨터 시스템 책(Compouter Systems - A Programmer's Perspective / CSAPP) 1.1 - 1.4
- 5주차 이후에 본격적으로 학습하기 전에, 용어들을 미리 익혀두는 것을 목표로..
백준 문제 풀이 + 관련 이론 학습
- 기초
- 수학
- 재귀함수
- 정렬
- 완전탐색

CSAPP 1.1 - 1.4

1.1 정보는 비트와 컨텍스트로 이루어진다.

소스파일은 0, 1로 표시되는 비트들의 연속이다.
8비트는 1바이트를 구성하며, 각 바이트는 프로그램의 텍스트를 나타낸다.

1.2 프로그램은 다른 프로그램에 의해 다른 형태로 번역된다.

컴파일 시스템과 컴파일 단계

전처리 단계
- 프로그램: 전처리기(cpp)
- 결과 파일 확장자: .i
- 무엇을 하는 단계인가?: .c 파일을 #로 시작하는 디렉티브(예: #include)에 따라 수정
컴파일 단계
- 프로그램: 컴파일러(cc1)
- 결과 파일 확장자: .s (어셈블리어 프로그램)
- 무엇을 하는 단계인가?: .i 파일을 .s 파일로 번역하는데, 이 파일은 저수준 기계어 명령어를 나타낸다.
어셈블리 단계
- 프로그램: 어셈블러(as)
- 결과 파일 확장자: .o (바이너리 파일)
- 무엇을 하는 단계인가?: .s 파일을 기계어 인스트럭션으로 번역하여 .o라는 목적파일에 저장한다.
링크 단계
- 프로그램: 링커 프로그램(ld)
- 결과 파일: 실행파일 (=실행가능 목적 파일, 실행가능 목적 프로그램)
- 무엇을 하는 단계인가?: 관련 있는 .o 파일들을 결합한다.

👉 이 과정을 거쳐 컴파일된 실행파일은 메모리에 적재되어 실행된다.

1.3 컴파일 시스템이 어떻게 동작하는지 이해하는 것은 중요하다.

프로그래머가 컴파일 시스템의 동작에 대해 이해해야 하는 이유 몇 가지 :
- 프로그램 성능을 최적화할 수 있다.
- 링크 에러에 대해 이해할 수 있다.
- 보안 약점을 피할 수 있다.

1.4 프로세서는 메모리에 저장된 인스트럭션을 읽고 해석한다.

명령어 인터프리터(command line interpreter)
- 명령어 인터프리터는 줄 단위의 명령어를 읽어 들여 실행하는 프로그램이다.
- 명령어 인터프리터 종류 (예: zsh, pwsh)
프롬프트(prompt)
- 사전적 의미는 [컴퓨터] 프롬프트, 입력 촉진 (기호[문]) (지시 대기 상태임을 나타내는 기호 (출처: 네이버 사전)
- 명령어 인터프리터는 프롬프트를 출력하고, 명령어 라인을 입력 받아 명령을 실행한다.
- macOS 쉘 프롬프트 커스텀하는 것에 관심이 있으시다면..
- macOS의 기본 쉘인 zsh의 프롬프트는 아래 그림과 같다.

하드웨어 구성: 전형적인 시스템에서의 하드웨어 구성을 이해해야, 프로그램을 실행할 때 무슨 일이 일어나는지 설명할 수 있다.
- 버스(Buses)
  - 버스(bus)는 시스템 내를 관통하는 전기적 배선 군으로, 컴포넌트들 간에 바이트 정보를 전송한다. 즉 부품들 간 데이터가 오고 갈 수 있는 통로 역할을 한다.
- 입출력 장치
  - 입력용: 키보드, 마우스
  - 출력용: 디스플레이
  - 데이터/프로그램 장기 저장: 디스크 드라이브
- 메인 메모리
  - 프로세서가 프로그램을 실행하는 동안, 데이터와 프로그램을 모두 저장하는 임시 저장장치
  - 물리적으로는 DRAM 칩들로 구성되어 있으며, 논리적으로는 연속적인 바이트들의 배열이다.
    - 삼성전자 반도체 사이트의 DRAM 제품 소개 페이지에서 DRAM의 생김새와 기능을 자세히 확인해볼 수 있다.
- 프로세서(=CPU, 주처리장치, 중앙처리장치)
  - 메인 메모리에 저장된 인스트럭션(명령)들을 해독/실행하는 엔진
  - 프로세서의 중심에는 PC가 있음. PC는 그 personal computer할 때의 PC가 아니라 program counter라는 의미다. 구체적으로는:
    - PC는 CPU 레지스터로서, 메모리로부터 실행되어야 할 다음 인스트럭션의 주소를 가지고 있다.
      - 레지스터: "프로세서에 위치한 고속 메모리로, 극히 소량의 데이터나 프로세서가 바로 사용할 수 있는 데이터(처리 중인 중간 결과 등)를 담고 있는 영역을 레지스터라고 한다. 컴퓨터 구조에 따라 크기와 종류가 다양하다." (나무위키), "프로세서 레지스터 또는 단순히 레지스터는 컴퓨터의 프로세서 내에서 자료를 보관하는 아주 빠른 기억 장소이다. 일반적으로 현재 계산을 수행중인 값을 저장하는 데 사용된다." (위키백과)
    - PC는 디지털 계수기(digital counter)로서 작업들의 빠른 실행과 현재 실행 지점을 기록하기 위해 필요하다.
    - PC의 다른 이름들: instruction counter, instruction pointer, instruction address register, sequence control register
  - CPU가 실행하는 작업 목록
    - 적재(load)
      - 한 바이트 또는 워드를 메인 메모리에서 레지스터로 복사 (이전 값에 덮어쓰는 방식)
    - 저장(store)
      - 한 바이트 또는 워드를 레지스터에서 메인 메모리로 복사 (이전 값에 덮어쓰는 방식)
    - 작업(operate)
      - 두 레지스터의 값을 ALU로 복사
      - 두 개의 워드로 수식 연산 수행
      - 결과는 레지스터에 덮어쓰기 방식으로 저장
    - 점프(jump)
      - 인스트럭션 자신으로부터 한 개의 워드를 추출
      - 추출한 워드를 PC에 덮어쓰기 방식으로 복사
  - 워드(word)란? 고정 크기의 바이트 단위로, 데이터를 전송하도록 설계된다. 이 때 한 개의 워드를 구성하는 바이트 수는 시스템마다 다르다. (보통 4바이트 또는 8바이트라고 함.)

문제풀이 및 알고리즘

소수인지 여부를 효율적으로 판단하는 방법은 이곳저곳에서 유용하게 쓰인다.
에라토스테네스의 체: 범위 n이 주어졌을 때, 소수만 남기고 걸러야 하는 상황에서 사용
1. 말 그대로 체(sieve)를 만든다. 그리고 여기에 n까지의 모든 숫자를 담는다. 배열로 구현한다. sieve = list(range(0, 10001))
  - 0번, 1번 자리에는 0을 넣는다.
2. 주어진 범위를 순회하며 숫자를 걸러내는 작업을 할 건데, 이때 주어진 범위(n)의 제곱근까지만 순회를 해도 된다. (위 소수를 효율적으로 판별하는 방법 참고)
3. 해당 인덱스에 위치한 원소를 0으로 교체함으로써 "소수가 아니므로 걸렀음"을 표시하기로 한다.
4. 순회를 하면서, 현재 인덱스에 위치한 원소의 값이 0인지(=소수가 아니어서 걸러졌는지) 여부를 살핀다.
  1. 0이다 ? 👉 다음 자리로 넘어가기
  2. 0이 아니다 ? 👉 해당 인덱스에 위치한 원소의 값의 2의 배수를 시작으로, 3의 배수, 4의 배수, ... (범위 n을 넘지 않는 범위에서) 이런 식으로 해당 원소의 배수들을 걸러나간다. (=0으로 교체한다.)
5. 이렇게 순회를 마치고 나면 체에는 0과 소수만 남게 된다!

import math

# 에라토스테네스의 체로 소수 먼저 걸러두기
sieve = list(range(0, 10001))
print(sieve)
sieve[0] = 0
sieve[1] = 0

i = 2

while i <= math.sqrt(10000):
  if sieve[i] == 0:
    i += 1
    continue
  else:
    j = i * 2
    while j <= 10000:
      sieve[j] = 0
      j += i
    i += 1

백준 2869번. 달팽이는 올라가고 싶다 ~~(답을 정말 맞추고 싶다..ㅠ)~~ 접근 방식:
- 달팽이가 마지막 날 낮에 A미터 올라갔을 때 정상에 성공적으로 도달해서, 그 다음날 밤으로 넘어가지 않을 수 있다!고 믿자!! 🐌 💪
- 그렇게 믿고 우선 마지막 날에 남은 거리, 즉 달팽이가 밤을 넘기지 않고 잘 올라갈 수 있을 것이라는 믿음(전제) 하에 남는 거리 A미터는 제외하고, 일단 마지막 날(최소 하루, 최대 이틀)은 나중에(=달팽이하는 거 봐서) 카운트하겠다는 생각으로 (V - A) / (A - B)를 구한다. 만약 달팽이가 우리의 바람대로 정상에 성공적으로 도달한다면, 즉 (V - A) / (A - B)가 남는 거리(=나머지) 없이 딱 맞아 떨어지면 하루만 더해주면 되고, 그게 아니라면 이틀을 더해주면 된다.

import math

[A, B, V] = list(map(int, input().split()))

cnt = math.floor((V - A) / (A - B))

if (V - A) % (A - B):
  cnt += 2
else:
  cnt += 1

print(cnt)

백준 9020번. 골드바흐의 추측 문제는 배운 것 좀 써보려고 에라토스테네스의 체로 풀어봤다가 시간초과가 떠버려서, 그냥 단순하게 소수 판단 방식으로 소수 여부를 판단했다. (구글링 해보면 에라토스테네스의 체로 푸신 분들도 있는 것 같다. 파이썬으로!)

def isPrime(num):
  for i in range(2, math.floor(math.sqrt(num)) + 1):
    if num % i == 0:
      return False
  return True

백준 1914번. 하노이 탑 문제는 2년 전 처음 봤을 때나 이번에 다시 봤을 때나 정말 이해가 안 됐다. 그때처럼 또 포기하기는 싫어서 끙끙대면서 교육 자료랑 설명 영상 찾아보다가, 아래 영상 보고 마침내 좀 이해가 갔다. 재귀 함수의 동작 방식이 머리 속에 그려지지 않았는데 영상에서 마지막 부분 쯤에 그 내용도 친절하게 설명해줘서 도움이 좀 되었다.
https://youtu.be/FYCGV6F1NuY
- 원판 각각을 따로 옮겨야 한다는 조건에 매몰되어 생각하다보니 도무지 이해가 안 갔는데, 영상에서 처음에 설명하는 것처럼: 결국은 "메인 원판이 아닌 나머지 원판들을 보조 장대로 옮긴다"(즉, 내부에서 개별 원판을 옮기는 작업들을 할지라도 우선은 나머지 원판들을 하나의 그룹으로 묶어서 통째로 옮긴다고 치자!) 👉 "메인 원판을 목표 장대로 옮긴다"는 작업을 하는 것이다. 재귀 호출을 하는 이유는 내부 원판 옮기는 작업을 위해서 그런 것이고! 재귀적으로 호출된 함수에선 해당 그룹에서 가장 큰 원판이 메인 원판이 되고 나머지는 보조 원판 그룹이 된다.

N = int(input())

def solveHanoi(disks: int, fromBoard: int, toBoard: int, tempBoard: int):
    if disks == 1:
        print("%d %d" % (fromBoard, toBoard))
        return

    solveHanoi(disks - 1, fromBoard, tempBoard, toBoard)
    print("%d %d" % (fromBoard, toBoard))
    solveHanoi(disks - 1, tempBoard, toBoard, fromBoard)

print((2 ** N) - 1)
if N <= 20:
    solveHanoi(N, 1, 3, 2)

백준 9663번. N-Queen 문제도 10시간 정도 붙잡고 있었는데, 풀이를 봐도 이해가 안 갔다. 그러다가 백트래킹 개념을 활용해야 한다는 글을 보고 어??하고 백트래킹에 대한 설명을 찾아보니 납득이 갔다. DFS에 대한 내용을 아직 제대로 학습해본 적이 없어 정확한 설명은 할 수 없는 단계이지만 그래도 위에 포스팅 작성해주신 분들 덕에 감은 잡은 것 같다. DFS는 학습 스케줄에 맞춰서 빠르면 이번 주 늦으면 다음 주 중에 학습해야겠다.
- 감은 잡은 상태에서 파이썬으로 코드를 작성해보았는데 계속 시간 초과가 났다. 혹시 몰라 C로 어설프게 구현해봤는데 그건 통과됐다. 파이썬에서 시간 초과 나지 않고 통과할 수 있을텐데 어떻게 하면 더 개선할 수 있을지 동료분들 코드 좀 훔쳐봐야겠다.
- 배운 거 또 응용해보겠다고 백준 9095번. 1, 2, 3 더하기 문제를 그런 식으로 허겁지겁 풀어봤는데, 정답 인정은 되는데 코드도 더럽고 뭔가 찝찝했다. 다른 분들 푸신 것도 보고 코치님 말씀도 들어보니 이렇게 DFS 이용해서 풀어도 되긴 하지만 DP와 수열 개념을 이용해서 푸는 방식이 훠얼씬 심플하고 더 효율적으로 풀 수 있는 방식이라고 한다.
- DP로 풀 생각을 진작에 했더라면 시간 절약해서 마지막 문제까지 풀 수 있었을텐데.. 아직 문제를 풀어본 경험이 많지 않아서 어떻게 접근하는 게 좋은지 떠올리고 판단하는 게 부족한 것 같다.
백준 2751번. 수 정렬하기 2 문제는 파이썬 내장 정렬 함수를 사용해도 통과는 되지만 정렬 로직을 직접 구현해보는 게 의미가 있을 것 같아서 직접 구현을 해보았다. 우선 처음에는 퀵 소트로 구현을 했고 배열의 가운데에 위치하는 원소가 피봇이 되도록 했다. 그런데 시간 초과가 발생했다. 퀵 소트는 최악의 경우에 시간복잡도가 O(N^2)인데 이렇게 매번 정해진 자리에서 피벗을 구하는 방식으로 퀵 소트를 구현한 경우, 최악의 경우를 만들기 쉽다고 한다.

import sys

N = int(sys.stdin.readline())
nums = []

for _ in range(0, N):
    nums.append(int(sys.stdin.readline()))

# 그룹을 분할하고 정렬하는 프로시저
def partition(A: list, left: int, right: int):
    # 왼쪽부터 순회를 시작하는 포인터
    pl = left
    # 오른쪽부터 순회를 시작하는 포인터
    pr = right
    pivot = A[(left + right) // 2]

    # 두 포인터가 교차할 때까지 반복 작업
    while pl <= pr:
        while A[pl] < pivot:
            pl += 1
        while A[pr] > pivot:
            pr -= 1

        if pl <= pr:
            # swap
            A[pl], A[pr] = A[pr], A[pl]
            pl += 1
            pr -= 1

    if left < pr:
        partition(A, left, pr)
    if right > pl:
        partition(A, pl, right)

# quick sort
def quick_sort(A: list): # 인자로 원본 배열을 전달
    partition(A, 0, len(A) - 1)

quick_sort(nums)

for num in nums:
    print(num)

# ! 퀵소트는 최악의 경우 시간복잡도가 O(N^2)이다.

그러한 최악의 경우를 피하기 위한 방법 중 하나로 랜덤 피벗을 선택하는 방법이 있다고 하여 구현해보았다. 시간이 오래 걸리기는하나 시간 초과는 나지 않았고, 병합 정렬보다 살짝 더 빠르게 처리되는 걸로 보여진다.

import sys
import random

N = int(sys.stdin.readline())
nums = []

for _ in range(0, N):
    nums.append(int(sys.stdin.readline()))

# 최악의 경우를 피하기 위해, 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택한다.
def getPivot(A: list):
    [a, b, c] = random.sample(A, 3)

    if a > b:
        if b > c:
            return b
        if c > a:
            return a
        return c
    if a > c:
        if c > b:
            return c
        return b
    if b > c:
        return c
    return b

# 그룹을 분할하고 정렬하는 프로시저
def partition(A: list, left: int, right: int):
    # 왼쪽부터 순회를 시작하는 포인터
    pl = left
    # 오른쪽부터 순회를 시작하는 포인터
    pr = right
    pivot = getPivot(A[left:(right + 1)]) if len(A[left:(right + 1)]) >= 3 else A[(left + right) // 2]

    # 두 포인터가 교차할 때까지 반복 작업
    while pl <= pr:
        while A[pl] < pivot:
            pl += 1
        while A[pr] > pivot:
            pr -= 1

        if pl <= pr:
            # swap
            A[pl], A[pr] = A[pr], A[pl]
            pl += 1
            pr -= 1

    if left < pr:
        partition(A, left, pr)
    if right > pl:
        partition(A, pl, right)

# quick sort
def quick_sort(A: list): # 인자로 원본 배열을 전달
    partition(A, 0, len(A) - 1)

quick_sort(nums)

for num in nums:
    print(num)

# ! 퀵소트는 최악의 경우 시간복잡도가 O(N^2)이다.

1주차 소회

마음 놓고 공부만 할 수 있는 게, 그것도 내가 원하던 공부를 할 수 있는 게 행복하다. 어렵거나 이해가 되지 않던 부분들을 포기하지 않고 몇 시간이고 잡고 있다가 마침내 이해하고 해결하게 됐을 때 그 홀가분해지는 느낌이 참 좋았다.

그저께(목요일) 1주차가 끝나고 2주차가 시작되었지만 그와 동시에 코로나에 걸려버려서.. 오늘 오후까지 고통 받다가 좀 나아져서 이제야 늦은 회고를 올린다.. 😷

'dev-log > 크래프톤 정글' 카테고리의 다른 글

크래프톤 정글 4, 5주차 회고 (2)	2022.12.23
CSAPP 9장. 가상메모리 - 9.1 ~ 9.8 내용 정리 (0)	2022.12.05
크래프톤 정글 3주차 TWIL.. (1)	2022.12.01
크래프톤 정글 2주차 TWIL.. (1)	2022.11.18
크래프톤 정글 1주차 에세이 (8)	2022.10.31