정글

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, ..

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..

2178. 미로탐색 BFS(Breadth First Search, 너비 우선 탐색)으로 해결 시작점을 1로 두고 기존값을 더해가면서 최단 거리 계산 import sys from collections import deque input = sys.stdin.readline y, x = map(int, input().split()) graph = [list(map(int, input().strip())) for _ in range(y)] for i in range(y): for j in range(x): if graph[i][j] == 1: graph[i][j] = 0 else: graph[i][j] = -1 visited = [[0] * x for _ in range(y)] deq = deque() dx =..

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 장점 M개의 문자로 구성된 문자열을 추가와 탐색하는 시간 복잡도는 O(M) 문자열을 빠르게 탐색할 수 있음 단점 필요한 메모리의 크기가 너무 큼 모두 소문자로만 이루어졌다고 해도, 26개의 공간이 필요 플로이드 와샬(Floyd-Warshall) 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 알고리즘(방향, 음수 상관없음 / 싸이클이 발생하면 안됨) 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘 수행 2차원 테이블에 최단 거리 정보를 저장 DP 알고리즘에 해당 시간 복잡도는 O(N^3) 노드의 개수가 N개 일 때, N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. ..