Han's Tech LAB

논리 설계 관례 "edge-triggered clocking" 방법론은 경쟁 관계, 즉 race를 발생시키지 않으면서 같은 클럭 사이클에 상태소자를 읽고 쓸 수 있도록 해준다. 경쟁 관계가 발생하면 이상한 데이터 값이 된다. 물론 활성화 클럭 edge에서 입력값이 안정되도록 클럭 사이클이 충분히 길어야 한다. 상태소자가 edge 구동 방식이므로 1 클럭 사이클 내에서 피드백은 일어날 수 없다. 만약 피드백이 가능하다면 이 설계는 제대로 작동하지 못 할 것이다. 이 장과 다음 장에서의 설계는 edge 구동 타이밍 방법론과 이 그림과 같은 구조를 사용한다. 이 방법은 레지스터 내용을 읽고 그 값을 조합회로로 보내고 같은 레지스터에 쓰는 작업 모두가 한 클럭 사이클에 일어나는 것을 허용한다. 데이터패스 만들기..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 오늘도 DP 문제를 가져와 보았다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 연산을 사용하는 횟수의 최솟값을 출력하는 것이다. 입력으로 주어는 값을 x에 넣는다. 재귀를 이용하여 구현해준다. 해당 코드는 하향식으로 제일 큰 값에서 작은 값으로 바뀌도록 구성되었다. x=int(input()) dp={1:0} def rec(n): if n in dp.keys(): return dp[n] if n%3==0 and n%2==0:..

프로세서의 상태 전환에 대해 알아보자. 종료 상태 Terminated 종료 시그널을 수신했을 때 메인 함수에서 리턴했을 때 exit 함수를 호출했을 때 프로세서의 제어 -> Unix는 C 프로그램을 이용해서 다음과 같은 프로새스 제어 기능을 제공한다. process ID를 가져온다 프로세스를 만들거나 종료한다 자식 프로세스를 제거한다 reaping child processes 프로그램의 로딩 및 실행 * Process ID 가져오기 각 프로세스는 프로세스 ID를 갖는다. pid_t getpid(void) pid_t getppdi(void) => 호출한 프로세스 또는 그 부모 프로세스의 PID 를 리턴 int fork(void) 호출하는 프로세스(부모 프로세스)와 동일한 새 프로세스(자식 프로세스)를 생성..

시스템 프로그래밍의 예외적인 제어 흐름에 대해 알아볼 것이다. 컴퓨터는 단순한 한 가지 일만 한다. 전원이 들어간 후 instruction들만 반복적으로 한 번에 한 개씩 실행한다. => 이러한 명령어의 실행 흐름을 시스템의 물리적인 제어흐름이라고 한다. 제어흐름을 변경하는 방법에는 무엇이 있을까? jumps와 branches 명령어 Stack을 사용한 Call과 return 명령어 가 존재한다. BUT, CPU가 시스템의 상태변화에 대응하도록 하기는 아직 어렵다. 여러 가지 예외적인 상황이 존재한다. 이를 테면, 하드 디스크나 네트워크 어뎁터에 데이터가 수신된 경우 0으로 나누기를 시도할 때 사용자가 ctrl-c를 눌렀을 때시스템 타이머가 초과되었을 때 시스템은 예외적인 제어흐름을 위한 메커니즘을 필요..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 오늘은 DP 문제를 풀어보고자 한다. 배낭 문제(knapsack)을 풀어보려 고한다. 배낭에 넣을 수 있는 최대값이 나오고 한도 안에 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 최적화 문제이다. 짐을 쪼개지 않고 푸는 문제이므로 DP로 문제를 해결한다. 코드는 아래와 같다. import sys N, K = map(i..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net Floyd Warshall Algorithm 을 이용하여 구현하였다. import sys INF = sys.maxsize N, M = map(int, input().split()) s = [[INF] * N for i in range(N)] for i in range(M): num1, num2 = map(int, input().split()) s[n..

오늘의 공부는... 파이프라인 해저드에 대해 알아보자. 파이프라인 해저드란? -> 다음 명령어가 다음 클럭 사이클에 실행될 수 없는 상황이 있다. 이러한 사건을 해저드(hazard)라 부른다. 이는 세 가지 종류가 있다. 첫 번째는 구조적 해저드(strcutural hazard)이다. 주어진 클럭 사이클에 실행되도록 되어 있는 명령어 조합을 하드웨어가 지원하지 못해서 계획된 명령어가 적절한 클럭 사이클에 실행될 수 없는 사건이다. 천천히 살펴보자. 이는 같은 클럭 사이클에 실행하기를 원하는 명령어의 조합을 하드웨어가 지원할 수 없다는 것을 의미한다. 이것은 필요한 자원이 바쁘게된다면 발생한다. 이후 스케줄된 파이프라인 계획이 틀어진다. RISC-V 명령어 집합은 파이프라이닝하도록 설계되었기 때문에 설계자..

문제 경로 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬에 대한 백준 문제이다. 위상정렬(Topological Sorting) 이란? 문제 상황 -> 비순환 유향 그래프(DAG : directed acyclic graph)가 주어질 때 방향성을 거스리지 않게 모든 정점들을 나열하는 것 예제 프로젝트 관리 선수 과목 요리하기 위상정렬 특징 # 그래프가 사이클을 가질 경우 DAG를 만족하지 ..

Network flow 문항을 찾다가 Max flow문제를 발견하였다. https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 시간 복잡도 : O(VE^2) 정점 중 Capacity가 주어진 파이프 그래프가 주어졌을 때, 정점 start_node에서 정점 end_node까지의 최대 flow를 출력하는 문제이다. Edmonds_Karp Algorithm을 적용하여 풀이하였다. 코드를 조금씩 살펴보도록 하자. import sys from c..

NetWork Flow Algorithm # 네트워크 전송 및 통신 분야에서 사용하는 Algorithm 아래 그림과 같이 간단하게 용량과 유량을 표시합니다. 그림에서 가장 손실 없이 유량을 전달할 때, 가장 적합한 유량은 몇 일까요? 만약 5를 유량으로 보내게 된다면, 5는 b에서 c를 갈 때, 3만큼만 갈 수 있으므로, b에서 2만큼의 손실이 발생하게 됩니다. 따라서, 위 그림에서 손실 없이 유량을 보내는 방법은 3을 보내는 것입니다. 그리하여 최대한 낭비되는 것 없이 유량을 보낼 수가 있습니다. 이를 Max Flow Problem(최대 유량 문제)라고 합니다. 이렇게 최대 유량 문제 란 네트워크 상에서 얼마나 많은 데이터를 흘려 보낼 수 있는지를 나타냅니다. 최대 유량 문제 는 각 간선에 정해진 용량..