크래프톤 정글 - TIL

스택과 레지스터 스택(stack) 프로시저 호출 시 지역변수와 매개변수를 저장하기 위한 메모리 공간 선언되는 순서와 반대로 메모리가 해제되는 LIFO(LastInFirstOut)구조용도 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장 함수의 제어흐름 관리 : 함수가 다른 함수를 호출할 때, 반환주소와 이전함수의 스택프레임 정보가 스택에 저장장점 동적으로 메모리를 할당하고 해제할 수 있음 구현이 간단하며, 메모리 관리 overhead가 낮음 레지스터(register) 프로세서 내부의 고속작동 메모리로, 프로시저 실행 중. 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용 용도 중간 연산결과의 저장 : 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용 빠..

3.7 프로시저 프로시저 호출은 소프트웨어에서의 주요 추상화 인자를 받을 수 있고 값을 리턴할 수 있는 코드 블럭(특정 기능이 구현된)의 추상화 함수, 메소드, 서브 루틴, 핸들러 등으로 사용 특징 프로시저가 다른 프로시저를 호출하고 리턴하는 일련의 동작은 다음과 같은 특징을 하나 이상 가질 수 있음 제어권 전달 프로그램 카운터(pc)는 호출되는 프로시저에 대한 코드의 시작주소로 설정 리턴할 때는 호출 인스트럭션 다음의 인스트럭션으로 설정 데이터 전달 호출자는 하나 이상의 매개변수를 피호출자에 제공할 수 있어야 함 피호출자는 호출자에게 하나의 값을 리턴할 수 있어야 함 메모리 할당과 반납 피호출자는 지역변수를 위한 공간을 할당할 수 있음 리턴할 때 이 공간을 반납할 수 있음 3.7.1 런타임 스택 3.7..

3.4.4 스택 데이터의 저장과 추출 스택(Stack) 스택은 프로시저 호출을 처리하는 데 중요한 역할 후입선출(Last In, First Out / LIFO) 형태로 추가, 제거되는 구조 제거하는 값이 가장 최근에 추가된 값 push : 데이터 추가 pop : 데이터 제거 스택은 탑(top) 원소가 모든 스택 원소 중에서 가장 낮은 주소를 갖는 형태 스택은 아래 방향으로 성장 스택 포인터(%rsp)는 스택 맨 위 원소(top)의 주소를 저장 pushq, popq 인스트럭션은 한개의 오퍼랜드를 사용 추가할 소스 데이터와 추출을 위한 데이터 목적지 # 쿼드워드 값을 스택에 추가하는 과정(push) subq $8,%rsp # 스택 포인터를 8만큼 감소 movq %rbp,(%rsp) # 쿼드워드를 새로운 탑에..

3.4 정보 접근하기 x86_64 CPU는 64비트 값을 저장할 수 있는 16개의 범용 레지스터를 보유 레지스터는 정수 데이터와 포인터를 저장 3.4.1 오퍼랜드 식별자 인스트럭션은 하나 이상의 오퍼랜드를 가짐 연산을 수행할 소스값과 그 결과를 저장할 목적지의 위치를 명시 결과값은 레지스터나 메모리에 저장 타입(Type) 상수(immediate) -> ‘$’ 기호 다음에 C 표준서식을 사용하는 정수 레지스터(register) -> 레지스터의 내용 메모리 참조 -> 유효 주소(effective address)에 의해 메모리 위치에 접근 일반적인 형태 Imm + R[rb] + R[ri]*s Imm : 상수 오프셋 rb : 베이스 레지스터 (64비트) ri : 인덱스 레지스터 (64비트) s : 배율 (1, ..

다이나믹 프로그래밍(DP : Dynamic Programming) 동적 계획법 목적 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장 한 번 해결한 문제는 다시 해결하지 않음 메모리를 사용해서 중복 연산을 줄임 배열 or 자료구조를 만듬 중복 연산을 줄여서 수행 속도를 개선 연산한 결과를 배열에 담음 기억하며 풀기(기억하기 알고리즘) 판단 기준 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 중복되는 부분 문제(Overlapping Substructure) 동일한 작은 문제를 반복적으로 해결 방식 탑 다운(Top-Down) : 하향식 -> 재귀로 구현 메모이제이션(Memoization) : 한 번 ..

LCS(Longest Common Subsequence) 최장 공통 부분수열(Longest Common Subsequence) : BCDF 또는 BCDE 최장 공통 문자열(Longest Common Substring) : BCD → F, E는 문자열을 건너뛰기 때문에 문자열로 인식하지 않음 점화식 if i == 0 or j == 0: # 마진 설정 LCS[i][j] = 0 elif string_A[i] == string_B[j]: # 문자열 앞에까지만 비교하고 마지막 끝에 값이 같으니 +1 LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) 1. LCS[i - 1][j]와 LCS[i][j - 1]는 어떤..

2637. 장난감 조립 위상 정렬(Topological Sort)를 사용해 구현 진입 차수(in-degree) 완성품(7번)부터 큐에 추가 비용을 저장하는 배열을 선언하고 시작 지점(7번)의 비용을 1로 초기화(나머지는 0) 큐에 넣은 것을 빼고 인접한 노드들을 탐색하면서 비용을 갱신 갱신한 노드들의 진입 차수를 -1하고 진입 차수가 0인 것을 다시 큐에 추가하고 반복 cost[목적지] += cost[출발지] * 가중치(비용) arr2 배열을 통해 진입 차수가 없는 기본 부품을 판별하여 출력 import sys from collections import deque input = sys.stdin.readline n = int(input()) m = int(input()) arr1 = [[] for _ i..