전기다람쥐의 개발 블로그

https://www.acmicpc.net/problem/12851 # 풀이과정 (BFS 이용)수빈이가 이동하는 방법은 앞으로 한칸, 뒤로 한칸, 현재 칸의 두배 위치로 점프, 이렇게 3가지이다.각 위치에 도달하기 위한 최소 시간을 나타내는 리스트를 하나 설정최단 시간을 구해야 하기에, 현재까지의 최소시간을 의미하는 전역변수 maxCnt를 설정함최단 기록의 경우의 수를 나타내는 변수 num을 설정함BFS를 이용하여 큐에 수빈이가 동생을 잡기위해서 현재까지 소요된 시간 및 현재위치를 넣음이것을 반복하여 동생의 위치에 도달하게 되면, 그때를 기준으로 소요된 시간이 총 걸린 시간임maxCnt보다 현재 소요된 시간이 크다면, 해당 경우의수는 더이상 계산하지 않음각 위치별로 도달에 필요한 최소 시간을 나타내는 리..

[Argument가 4개 이상이면?] - 초과하는 Argument들은 스택에 쌓아준다 EX) Argument가 6개일 때 1. Caller - 6th argument : $sp , 5th argument : $sp - 4 2. Callee - 6th argument : $sp - {frame크기} , 5th argument : $sp - {frame크기} - 4  [PC-relative addressing] - TA = $pc + (offset * 4) - beq로 어딘가로 점프할 때, $pc에는 beq다음 명령문의 주소를 저장한뒤에 점프한다. - beq로 가능한 주소 범위(16비트) : -2^15 ~ 2^15 - 1   [Jump addressing] - 어떤 주소로 점프하는 명령문이 있으면, 점프할 ..

[Jump 명령어] 1. jal : (SIC의 JSUB이라고 생각하면 됨) - " jal func " 의 형식으로 사용 - PC+4값을 $ra에 저장하고, func로 점프함. 2. jr : (SIC의 RSUB이라고 생각하면 됨) - " jr $ra " 의 형식으로 사용 - $ra에 저장된 주소로 이동(=복귀)  [레지스터 역할] - $a0~$a3 : Arguments - $v0~$v1 : Results (함수의 반환 값 저장용도)  [Caller save 레지스터] - $t0~$t9 레지스터 - 반드시 값을 보존할 필요 없음 (일종의 약속임) - 다른 함수로 갔다왔을때 그 값이 보장이 되지 않음.- 만약 그 값을 유지하고싶으면 함수 호출전에 메모리에 sw로 저장했다가 함수가 끝나고 돌아와서 lw로 다시 ..

https://www.acmicpc.net/problem/11404 # 풀이과정 (플로이드-워셜 알고리즘 이용)N개의 도시를 하나씩, 순차적으로 중간 노드로 설정중간노드를 거쳐가는 경로가 기존 경로보다 짧으면 업데이트모든 도시를 대상으로 한 작업이 끝나면, 그 때의 거리가 최단 거리임최단거리 출력 [플로이드-워셜 알고리즘을 이용한 코드 - 성공]# ex_11404import sysn = int(sys.stdin.readline())m = int(sys.stdin.readline())distance = [[1e9 for _ in range(n)] for _ in range(n)] # 거리를 저장하는 리스트for _ in range(m): a,b,c = map(int,sys.stdin.readli..

https://www.acmicpc.net/problem/11054 # 풀이과정DP로 각 지점에서의 증가길이를 찾는다DP로 각 지점에서의 감소길이를 찾는다. (수열의 뒤에서부터 거꾸로 증가하는 것으로 찾으면 쉬움)두 값의 합이 가장 큰 지점이 중앙임그 값에서 1을 빼서 출력하면 그것이 최장 바이토닉수열 길이임 [DP를 이용한 코드 - 성공]# ex_11054import sysn = int(sys.stdin.readline()) # 길이nums = list(map(int,sys.stdin.readline().split())) # 수열increase = [1 for _ in range(n)]decrease = [1 for _ in range(n)]for i in range(n): for j in ..

[Integer Addition] - 덧셈  -  결과가 정수형 표현 가능한 범위를 벗어나면 오버플로우(overflow) 발생피연산자가 각각 양수와 음수인 덧셈에서는 오버플로우가 발생하지 않는다.피연산자 2개가 모두 양수라면 오버플로우가 발생할 수도 있다.부호비트(MSB)로 1이 넘어가면서 음수가 된다.피연산자 2개가 모두 음수라면, 언더플로우 발생할 수 있다.부호비트(MSB)가 기존 1인 상태에서 1이 추가로 넘어오면서 0이 되어 양수가 된다.  [Integer Subtraction] - 뺄셈 2진수끼리의 뺄셈은 빼는수의 0과 1을 서로 뒤바꾼다.그것의 마지막 비트에1을 더해준다.그다음 2진수의 덧셈을 진행한다. (이때, 맨앞의 비트는 무시한다.)만약 결과가 음수이면 마지막 결과의 마지막 비트에서 1을..

A컴퓨터가 알아들을수있는 instruction set과 B컴퓨터 알아들을수있는 instruction set이 다르다. [Computer “Architecture” defines(컴퓨터 아키텍쳐 정의)] 1. Instruction set architecture (ISA)] - Instruction set : 명령어 세트 - Operand types : 피연산자 유형 - Data types (integers, floating points, …) : 데이터 유형(정수, 부동 소수점, ...) - Memory addressing modes, … : 메모리 주소 지정 모드 등등.. 2. Registers and other state(레지스터 및 기타 상태) 3. Memory management and protec..

https://www.acmicpc.net/problem/10830     # 풀이과정주어지는 제곱수의 범위가 최대 10억이기에, 이걸 전부 수행하면 시간초과가 발생한다.따라서, 분할정복을 이용하여 지수를 나누어서 계산해줘야함 이를 정리하면 다음과 같다.expon이 1이면 현재 그래프 g를 그대로 반환expon이 2면 g와 g를 한번 행렬곱한 결과를 반환expon이 1,2가 아니면 아니라면?expon을 절반의 정수값으로 줄여서 main함수를 호출해서 반환받은 값을 temp로 저장expon이 짝수이면 temp와 temp를 행렬곱한 결과를 반환expon이 홀수이면 temp와 temp를 행렬곱하고, 거기에 g를 행렬곱한 결과를 반환main함수로부터 반환받은 그래프의 요소들을 1000으로 모듈러 연산 수행한 값..

[CPU구성]프로세서① Datapath - CPU에서 데이터와 주소를 처리하는 요소② Control - 연속된 Dataoath, 메모리 등등③ Cache memory - 작고 빠른 SRAM 메모리메모리① DRAM(Dynamic RAM)② SRAM(Static RAM)보조기억장치① Magnetic disk (HDDs)② Optical disk (CD-ROM, DVD)③ Flash, Solid-state drives (SSDs)[집적도] - 칩이커지면 전자 이동속도 down → 칩의 집적도가 높아지면 이동속도 up [무한하게 빨라질수없는이유] ※ Power = (Capacitive load) X (Voltage)^2 X (Frequency) - 전압을 낮춰야한다. (But 한계가 있음)- 클럭( Freque..

https://www.acmicpc.net/problem/5639  # 풀이과정전위 순회는 루트, 왼쪽, 오른쪽의 순서대로 노드를 방문한다. 그렇기에 맨 처음 주어지는 노드는 루트이고, 그 이후에는 하위 노드들이라고 볼 수 있다.또한, 이진 트리이기에 한 노드의 왼쪽 서브트리의 모든 노드들은 해당 노드보다 작고, 오른쪽 서브트리의 모든 노드들은 해당 노드보다 크다는 사실을 인지해야한다. 그렇다면 차례대로 주어지는 노드들이 어떤 위치에 속해야 하는지는 어떻게 판단해야 할까?이때 우리는 여러가지 경우의 수를 생각해 보아야한다.우선, 부모로 예측되는 노드보다 크기가 작은 노드가 주어진다면, 해당 노드는 부모의 왼쪽 자식 노드이다.반대로, 부모보다 크기가 큰 노드가 주어진다면, 해당 노드는 부모로 예측되는 노드..