[크래프톤 정글 3기] 10/14(토) TIL

ClassBinu·2023년 10월 14일
0

크래프톤 정글 3기 TIL

목록 보기
3/120

알고리즘 1주차

알고리즘

백준에서 input 받기_1

# 일반적일 방법, 시간 초과 발생할 가능성 있음.
a, b = map(int, input().split())

코드 분석

  • input()
    사용자에게 입력을 받는 함수이다. 주로 사용자와 상호작용할 때 사용된다. 사용자가 텍스트를 입력하고 Enter를 입력할 때까지 대기한다. 입력된 텍스트는 문자열로 처리된다.
  • split()
    문자열을 나눈다. 파라미터가 없는 경우 공백을 구분자로 사용한다. 리스트를 반환한다.
  • input().split()
    입력된 텍스트를 공백을 구분자로 해서 나눈다.
  • map
    입력된 데이터를 특정 함수를 통해 처리할 수 있다. 반복 가능한 객체를 사용한다. 이터레이터를 반환한다.
# map의 예시
# 입력된 문자열을 부동 소수점 숫자로 바꾼다.
map(float, input().split())

#입력된 문자열을 모두 대문자로 바꾼다.
map(str.upper, input().split())

  • 이터레이터
    데이터 스트림, 시퀀스에서 순차적으로 요소를 반복적으로 접근하기 위한 객체

  • map(int, input().split())
    input().splite()에서는 문자열이 공백을 기준으로 1개씩 분리되고 리스트를 반환한다. 그 후 map을 통해 리스트 안의 요소를 순회하면서 int를 적용하고 이터레이터를 반환한다. split()이 리스트를 반환하니까 반복가능한 객체이므로 map으로 순회할 수 있다. 만약 반환된 이터레이터를 리스트로 변환하려면 list()로 씌워야 한다.

map 함수 궁금한 점
첫 번째 파라미터가 int()가 아니라 int인 이유는?
-> int 는 함수 객체 자체를 나타내서 함수 객체 자체를 전달하는 것이다. int()는 함수 호출을 나타낸다.
(Python 함수는 일급 객체라고 하는데 일급객체에 대해서 추가로 공부하기)

일급객체?
컴퓨터 프로그래밍 언어 디자인에서, 일급 객체(영어: first-class object)란 다른 객체들에 일반적으로 적용 가능한 연산을 모두 지원하는 객체를 가리킨다. 보통 함수에 인자로 넘기기, 수정하기, 변수에 대입하기와 같은 연산을 지원할 때 일급 객체라고 한다.

백준에서 input 받기_2

# sys사용하기, 맨 뒤의 '\n'까지 입력받는다. 
import sys
n = int(sys.stdin.readline())

# 마지막 엔터를 제외하고 싶다면
n = int(sys.stdin.readline().split())

# input()대체해서 사용하면 된다.
a, b = map(int, sys.stdin.readline().split())

코드 분석

  • sys
    파이썬 표준 라이브러리 중 하나인 모듈
    시스템과 관련된 다양한 기능을 제공
    sys.version: 현재 파이썬 버전
    sys.plaffrom: 파이썬이 실행 중인 운영체제
    sys.exit(): 프로그램 종료, 에러 상황 표현

  • sys.stdin
    Standiart Input
    표준 입력 스트림을 나타내는 객체
    사용자가 키보드로 입력한 데이터를 읽는데 사용된다.
    파일 객체와 비슷하게 동작한다.(파일 객체에 적용할 수 있는 메서드와 속성 사용 가능)

  • sys.stdin.readline()
    사용자가 입력한(또는 파일에서) 한 줄의 텍스트를 읽어 온다.

readlin() 궁금한 점
input() 보다 sys.stdin.readline()이 빠른 이유는?

  • input(): 키 입력마다 읽기를 시도(불필요한 I/O 작업 수행)
  • realine(): 한 줄을 읽기 버퍼에 저장하고, 다음 줄 바꿈 문자가 나타날 때까지 버퍼에서 읽어 온다.
  • 읽기 버퍼
    소프트웨어 수준에서 관리되는 메모리 영역(물리 공간이 아님)
    데이터를 일시적으로 저장하고 관리하는 역할
    데이터를 블록 단위로 처리하여 성능을 향상

map함수 결과에 list()를 씌워야 하는 이유

# 런타임 에러가 발생한 코드
nums = map(int, sys.stdin.readline().split())

# 수정 코드
nums = list(map(int, sys.stdin.readline().split()))

위 코드에서 계속 런타임 에러가 발생했다. map함수를 제대로 이해하지 못해서 발생한 문제다.
map은 첫 번째 파라미터의 함수를 두 번째 파라미터 리스트에 적용하고 두 번째 파라미터 리스트를 반환하는 게 아니라 새로운 이터레이터를 반환한다. 반환된 이터레이터에 리스트 메서드를 쓰려면 list()를 씌워서 리스트로 변환해야 한다.

파이썬에서 아스키 코드 적용하기

# 문자 -> 아스키코드
# ordinal(순서) 문자의 유니코드 코드 포인트(정수) 반환
print(ord("A"))

# 아스키코드 -> 문자
# chracter(문자) 코드 포인트를 받아 해당하는 문자를 반환
print(chr(65))

아스키 코드
American Standard Code for Information Interchange
미국 정보 교환 표준 부호

알파벳, 숫자, 특수문자 128(0~127)개를 코드화 함.
8비트 중 7비트를 사용하고 나머지 1비트는 Parity Bit(에러 검출용)

Parity Bit: 7개 비트 중 1의 개수가 홀수면 1, 짝수면 0
전송 도중 신호가 변질된 것을 수신측에서 검출할 수 있다.

이 정도는 외워두기
0(48)
A(65)
a(97)

골드바흐의 추측

처음으로 나온 '중'수준 문제. 정답을 찾아보지 않고 풀었다.
풀이 과정은 복잡하지 않았지만 사소한 실수들이 많았다.
(예를 들어 // 대신 %를 입력)

접근 방법은 다음과 같다.
1. 소수를 구하는 함수를 구현한다.
2. 골드바흐 파티션을 구하는 함수를 구현한다.
2-1. N의 절반을 넘으면서 절반에 가장 가까운 수가 소수인지 체크한다.
2-2. N에서 a를 뺀 수가 소수인지 체크한다.
2-3. 두 수가 모두 소수이면 반환한다.
3. 입력값을 순회하면서 정답을 출력한다.

import sys

def checkPrimeNumber(n):
    if n <= 1:
        return False

    sqr = int(n ** 0.5)
    for i in range(2, sqr + 1):
        if n % i == 0:
            return False
    return True

def findGoldbachParition(n):
    half = n // 2
    for i in range(half, n):
        if checkPrimeNumber(i) and checkPrimeNumber(n - i):
            return [n - i, i]

T = int(input())
for _ in range(T):
    n = int(sys.stdin.readline())
    answer = findGoldbachParition(n)
    print(answer[0], answer[1])

재귀적으로 풀어 봄.(백코치님이 재귀적으로 푸는 것을 강력하게 추천하심.)
인터넷에서 찾은 팁!
재귀함수는 재귀적으로 생각하면 못 푼다.(실행 순서를 생각하는 게 아니다.)
1. 조건: 종료 조건 또는 기본케이스를 정의한다.
2. 분해: 문제를 작은 부분으로 나눈다.
3. 조합: 분해된 부분으로 전체 답을 구한다.

실행 순서를 생각하지 않고 조건만 지정하니까 팩토리얼 재귀 이해됨!

  • 재귀
n = int(input())

def fact(n):
    if n <= 1:
    	# return n은 n이 0일때 0이 반환되어 틀림.(1이 반환되어야 함.)
        return 1 
    return fact(n-1) * n

print(fact(n))

0!이 1인 이유: 그냥 수학적으로 정의됨.
1! = 1 x (1-1)!
1 x 0! = 1
정답: 0! = 1

하노이의 탑

  • 수학적으로 횟수만 구하기
# 단순 횟수만 구할 수 있으나 알고리즘과 무관함
print(2**n - 1)
  • 재귀 함수 구하기(백준 1914)
n = int(input())

def move(n, x, y):
    if n == 1:
        print(x, y)
        return 1
    
    count = 0
    t = 6 - x - y
    
    count += move(n-1, x, t)
    # 이 시점에서 프린트 해야 함. 바닥에 있는 기둥을 옮긴 것을 나타냄.
    print(x, y)
    count += 1
    count += move(n-1, t, y)
    return count

print(2 ** n - 1)
if n <= 20:
    move(n, 1, 3)

print(x, y)를 왜 재귀 함수 사이에 호출해야 하는지 이해하려고 1시간 이상 허비했다. 재귀적 사고를 못해서 생긴 문제다.
재귀 함수 사이의 print(x, y)는 지금 당장 옮기는 하나의 큰 원판의 위치를 출력하는 거였다! 난이도 '하'인데 어려웠음.
재귀적 사고에 대해서 조금 감잡음.

정렬(백준 2751)

  • 입력 함수 변경으로 문제 해결
    input(): 타임 오버
    sys.stdin.readline: 50초 정도 걸려서 정답
    (입력 값이 1,000,000 이하이다.)

  • 파이썬 내장 sort(), sorted() 정렬 방식
    파이썬의 정렬은 Timsort 알고리즘이다.(Tim Peters 창안)

  • Timsort 알고리즘

  1. '실제 데이터는 대부분 이미 정렬돼 있을 것이다'고 가정
  2. 삽입정렬과 병합정렬을 적절히 조합
  3. 협업에서 병합, 퀵보다 더 널리 쓰임.
    참고자료
  • 입력 함수 변경 방식으로 문제를 풀어도 될까?
    -> No!
    (순서대로 최선/평균/최악 시간복잡도)
    버블 정렬: n / n^2 / n^2
    삽입 정렬: n / n^2 / n^2
    힙 정렬: n / nlogn / nlogn
    머지 정렬: nlogn / nlogn / nlogn
    퀵 정렬: nlogn / nlogn / n^2
    팀 정렬: nlogn / nlogn / n^2

    최악의 경우 힙, 머지가 팀보다 빠르다. 힙이나 머지로 풀어야 될 것 같다.
    정렬 알고리즘 직접 구현해 보자!

set()

set()은 중복 제거 후 순서가 유지되지 않을 수 있다.

백준 2309(일곱 난쟁이)

아무리 풀어도 런타임 오류 발생한다.
인터넷에 돌아다니는 답안을 넣어도 계속 런타임 오류가 발생한다.
2309번 문제를 1181문제에 문제에 제출하고 있었음!!!!
(2시간 동안 삽질함)
그래도 덕분에 다양한 케이스 연습해 보았고, 이중 for문 탈출 코드 익힘.

N = 9
dwarfs = []
for _ in range(N):
    dwarfs.append(int(input()))
    
answer = dwarfs[:]
height_sum = sum(dwarfs)

found = False

for i in range(N-1):
    if found:
        break
    for j in range(i+1, N):
        a = dwarfs[i]
        b = dwarfs[j]
        if height_sum - (a + b) == 100:
            answer.remove(a)
            answer.remove(b)
            found = True
            break
            
for h in sorted(answer):
    print(h)

CSAPP

x86-64(1999년 발표)

인텔과 경쟁사에서 따르는 최신 기계어
인텔 명명법에 따라 이런 유형의 마이크로프로세서를 x86이라고 함.
표준 명칭은 AMD64
반도체 기술 발전에 따라 다음과 같이 발전함.
: 16비트 워드 -> 32비트 워드 -> 64비트 워드
범용 레지스터가 32비트에서 64비트로 확장
범용 레지스터가 8개에서 16개로 증가
발표 당시 가상 메모리 공간 48비트(256TiB)로 확장
-> 2021년 기준 표준은 가상 64비트(16EiB)
발표 당시 물리 메모리 공간 40비트(1Tib)로 확장
-> 발표 당시 1Tib는 매우 큰 용량이 었음.
-> 2021년 기준 표준은 물리 52비트(4PiB)
프로그램 카운터가 64비트이지만 메모리 공간에 제약을 두는 이유는?
: 메모리 포인터 숫자가 클 경우 페이지 테이블에 오버헤드가 커지기 때문
(굳이 큰 숫자를 쓸 필요 없음)
메모리 할당 방식(커널 영역): 메모리 주소 기준 맨 끝부분
메모리 할당 방식(사용자 영역): 처음 부분에 배치
NX bit 추가

NX bit(Never eXecute bit, 실행 방지 비트)

프로세서 명령어, 코드, 데이터 저장을 위한 메모리 영역을 따로 분리하는 CPU 기술
(인텔에서는 동일한 기능은 XD비트 라고 함)

컴퓨터 용량 정리(이진 접두어)

국제 전기 표준 회의(IEC)에서 정의함.

Ki 키비 2^10
Mi 메비 2^20
Gi 기비 2^30
Ti 테비 2^40
Pi 페비 2^50
Ei 엑스비 2^60
Zi 제비 2^70
Yi 요비 2&80

컴퓨터 시스템

하드웨어 + 시스템 소프트웨어 -> 응용 프로그램 실행

파일

hello.c처럼 아스키 문자로만 이루어진 파일 = 텍스트 파일
그 외의 모든 파일 = 바이너리 파일

비트

컴퓨터 시스템 내의 모든 정보는 비트로 표시된다
서로 다른 객체를 구분하는 방법은 이들을 바라보는 컨텍스트에 의해 결정된다.
동일한 바이트가 컨텍스트에 따라 정수, 부동소수, 문자열, 기계어 명령어를 의미할 수 있다.
컴퓨터 내의 숫자 표현은 일생생활의 숫자(정수, 실수)와 같지 않다!!

hello.c는 이렇게 저장된다.

소스 파일(프로그래머가 에디터에 입력할 때의 모습)

#include <stdio.h>

int main()
{
	printf("Hello, world\n");
    return 0;
}

아스키 텍스트 표시

#include <stdio.h>


35 105 110 99 108 100 32 60 115 116 100 111 46 104 62 10 10 ...

기계어 인스트럭션
명령어 레이아웃
하나의 명령어가 바이너리 필드들로 구성된 형식
Register-type, Immediate-type이 있다.
참고

컴파일 시스템 세부 단계

gcc -o hello hello.c
GCC 컴파일러 드라이버가 소스파일 hello.c를 읽어서 실행파일 hello로 번역
컴파일 시스템 4단계를 거쳐 실행됨
1. 전처리기
2. 컴파일러
3. 어셈블러
4. 링커

1. 전처리기
#으로 시작되는 디렉티브(전처리 지시문)에 따라 C 프로그램을 수정한다.
#include<stdio.h>는 전처리기에게 시스템 헤더파일 stdio.h를 프로그램에 삽입하라고 지시한다. hello.i가 생성된다.

C전처리기는 무슨 언어로 만들어졌을까?
c언어로 만들어졌다!!
자기 자신을 컴파일하는 프로그램을 자기 자신으로 만든다?!

2. 컴파일
hello.i를 hello.s 텍스트 파일로 번역
이때 어셈블리어 프로그램이 저장된다.

main:
	subq $8, %rsp
    movl $.LCO, %edi
    call puts
    movl $0, %eax
    addq $8, %rsp
    ret

3. 어셈블리
hello.s를 hello.o 기계어 인스트럭션으로 번역

4. 링크
printf함수는 이미 컴파일이 완료된 printf.o에 이미 들어 있다.
hello.o와 printf.o가 결합되어야 한다.
링커가 hello.o와 printf.o를 통합시켜 hello 파일을 생성한다.

프로세서

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

시스템 하드웨어 구성

1. 버스
시스템 내를 관통하는 전기적 배선군
컴포넌트 간의 바이크 정보들을 전송
워드라고 하는 고정 크기 바이트 단위를 전송
워드 크기는 시스템 변수, 현대 컴퓨터는 32비트(4바이트) or 8바이트(64비트)

2. 입출력 장치
입출력 버스와 컨트롤러 or 어댑터를 통해 연결
컨트롤러: 디바이스 자체가 칩쳇 or 마더보드에 장착
어댑터: 마더보드 슬롯에 장착되는 카드

3. 메인 메모리
데이터와 프로그램을 저장하는 임시 저장 장치

4. 프로세서
CPU(주처리장치) or 메인 메모리에 저장된 인스트럭션들을 해독(실행)하는 엔진
레지스터(워드 크기)와 프로그램 카운터(PC)
끊이 없이 PC가 가리키는 곳의 인스트럭션을 반복적으로 실행하고 PC값을 다음 인스트럭션으로 업데이트

실행 과정
인스트럭션1 -> 인스트럭션2 -> 인스트럭션3 -> ... -> 인스트럭션n
(한 개의 인스트럭션을 실행하기 위해 여러 단계를 수행함)

ALU(산술논리장치): 새 데이터와 주소 값을 계산

인스트럭션의 요청에 의해 CPU가 실행되는 과정
1. 적재(Load): 메인 메모리 -> 레지스터(덮어쓰기 복사)
2. 저장(Store): 레지스터 -> 메인 메모리(덮어쓰기 복사)
3. 작업(Operate): 2개의 레지스터 값을 ALU로 복사, 수식연산 -> 레지스터 덮어쓰기 저장
3. 점프(Jump): 인스트럭션 자신에서 한 개의 워드를 추출 -> PC(덮어쓰기 복사)

레지스터 파일은 소프트웨어 수준이 아니라 CPU내에 존재하는 물리적인 다수의 레지스터

hello 프로그램 실행 과정 설명

1. "./hello" 키보드에서 읽어 들이기
(쉘 프로그램 입력을 기다리는 상태)

데이터 전송 과정
키보드
-> USB 컨트롤러
-> I/O버스
-> I/O 브릿지
-> 시스템 버스
-> (CPU)버스 인터페이스
-> (CPU)레지스터 파일
-> 시스템 버스
-> I/O 브릿지
-> 메모리 버스
-> 메인 메모리(문자열 "hello" 적재)

2. 실행파일 디스크에서 메인메모리 로딩
쉘은 파일 내의 코드와 데이터를 복사하는 일련의 인스트럭션 실행
실행 파일 hello를 디스크에서 메인 메모리로 로딩
데이터는 직접 메모리 접근 기법에 의해 프로세서를 거치지 않고 디스크에서 메인 메모리로 직접 이동

데이터 전송 과정
디스크
-> 디스크 컨트롤러
-> I/O 버스
-> I/O 브릿지
-> 메모리 버스
-> 메인 메모리

3. 출력 스트링을 메모리에서 화면으로 기록
프로세서는 hello 프로그램의 main 루틴의 기계어 인스트럭션을 실행

데이터 전송 과정
메인 메모리
-> 메모리 버스
-> I/O 브릿지
-> 시스템 버스
-> 버스 인터페이스
-> 레지스터 파일
-> 버스 인터페이스
-> I/O 브릿지
-> I/O 버스
-> 그래픽 어댑터
-> 디스플레이

캐시 메모리(캐시)

L1 캐시
수천 바이트 저장
거의 레지스터 파일만큼 빠름
CPU 칩 내부
SRAM 기술로 구현됨

L2 캐시
수백 킬로바이트 ~ 수 메가 바이트
프로세서와 전용 버스를 통해 연결
L1 보다 5배 정도 느림
메인 메모리보다는 5배 ~ 10배 빠름
SRAM 기술로 구현됨

프로그래머는 캐시를 활용하여 프로그램 성능을 10배 이상 개선할 수 있다.

저장장치 계층 구조

L0: 레지스터
L1: L1 캐시(SRAM)
L2: L2 캐시(SRAM)
L3: L3 캐시(SRAM)
L4: 메인 메모리(DRAM)
L5: 로컬 보조 저장장치
L6: 원격 보조 저장장치(클라우드)
한 레벨의 저장장치는 다음 하위 레벨 저장장치의 캐시 역할을 한다

웹에서 서버의 데이터를 브라우저에 저장하는 것도 캐시다!

profile
ClassBinu
이전 포스트

[크래프톤 정글 3기] 특별한 과제

다음 포스트

[크래프톤 정글 3기] 10/15(일) TIL

0개의 댓글