본문 바로가기

분류 전체보기172

[이산수학 #11] 트리 트리 즉, 어떤 순환도 존재하지 않는 연결 그래프 트리의 성질 1. 순환 존재하지 않음 2. 유일한 루트 노드 3. 내차수가 0인 노드는 only 루트 노드, 나머지의 내차수는 1 트리의 용어 루트노드, 부모 자식노드, 터미널(리프 노드)는 제외 - 레벨 - 루트 노드의 레벨 = 0 - 어떤 노드의 레벨이 i일때, 자식의 레벨을 i+1 - 높이 - 정점들 중 최고의 레벨 (그래프 당 한 개) - 정점의 차수 - 특정 정점의 부분 트리 개수 (유향, 무향 다 가능) - 트리의 차수 - 모든 정점들의 차수 중 최대값 - n트리 - 모든 정점들의 자식이 최대 n개 - 리프 노드 외의 모든 정점들의 자식이 n개이면, 완전 n트리 - 예) 완전 이진트리 - 순서 트리 - 유향 그래프에서 같은 레벨에서 정점의 자식.. 2023. 11. 29.
[알고리즘] 최소신장트리 (작성중) # 가중 그래프 : 간선에 가중치 (weight)를 가지는 그래프 예) 거리, 비용, 시간 # 최소신장트리 - 신장 부그래프 : 그래프의 모든 정점들을 포함하는 부그래프 - 신장트리 : 트리인 신장 부그래프 - 최소신장트리(Minumum Spanning Tree, MST) : 간선 무게가 최소인 신장트리 # 최소신장트리의 속성 ## 1. 사이클 속성 T: 가중그래프 G의 최소신장트리 e: 최소신장트리 T에 존재하지 않는 G의 간선 C: e를 T에 추가하여 형성된 사이클 => C의 모든 간선 f에 대해, weight(f) e를 포함하는 최소신장트리가 반드시 존재 # 탐욕법 (그리디) ### [ 요소 ] 1. 구성: 다양한 선택, 모음, 찾아야할 값들 2. 목표: 구성에 할당된 점수를 최대화, 최소화하는 것.. 2023. 11. 23.
[컴구] 프로세서 - 2 Pipelining - Non-stop: 2n/0.5n + 1.5 = 4 MIPS Pipeline Step 1. IF: Instruction Fetch from Memoty 2. ID : Instruction Decode & Register Read 3. EX : Execute Opration or Calculate Address 4. MEM : Access Memoty Operand 5. WB : Write Result Back to Register Pipeline 성능 [ 가정 ] - register Read, Write : 100ps - other : 200ps 위 표를 토대로 Single-Cycle과 Pipelined를 비교해보자. - Pipelined가 더 빠른 것을 쉽게 알 수 있음. [ 시간.. 2023. 11. 21.
[알고리즘] 방향그래프 방향그래프 - 모든 간선이 방향간선 방향그래프의 속성 - 모든 간선은 한 방향으로만 - G가 단순(간선이 많지 않음) : M v인 방향경로가 존재하면, "u는v에 도달한다" , "v는 u로부터 도달 가능하다" 강연결성 어느 두 정점 u, v 간에 u에서 v 도달가능 이고 v에서u 로 도달가능이면 강연결 강연결 검사 알고리즘 1. 임의 정점 v 선택 2. v에서 DFS 실행 3. 간선들 방향을 역행시킨 그래프 G'을 얻음 4. G'에서 v에서부터 DFS 수행 -> O(n+m) 강연결 요소 - 최대한 모든 정점을 도달할 수 있는 부그래프 a->f로 간다고 하면, a로 다시 올 수 없음. 이행적폐쇄 다음 성질을 만족. 1. G'은 G와 동일한 정점들로 구성 2. G의 u에서 v(v!=u)로의 경로가 존재하면 .. 2023. 11. 21.
[컴구] 프로세서 - 1 MIPS의 Type 명령어 실행 Program Counter: instruction Memory에서 Instruction Fetch Register Numbers: Register File, Read Registers에서 사용 Instruction Class에 따라 다음을 이용 ALU 사용 Load/Store을 통해 Data Memoty에 접근 PC상대주소법 사용 CPU의 전반적인 구조 여기서 충돌이 발생하는 지점에 MUX를 이용해 처리하면 된다. 이곳에 컨트롤까지 추가하면 설계가 완성된다. # 기본적인 이론 [ 정보를 이진으로 Encode 하는법 ] - Low Voltage = 0 / Higj Voltage = 1 - 1비트 당 하나의 wire [ Combinational element ] - 현재 주.. 2023. 11. 16.
[그리디 #2] BOJ1541 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 첫번째 시도 덧셈을 먼저 진행 후, 나중에 뺄셈을 진행해야 한다고 생각해서 operands, operations Vector를 두 개 만들어 덧셈->뺄셈 순서로 진행하는 방법을 생각했지만 매우 비효율적인 방법으로 생각되어 다른 방법을 생각함 두번째 시도 뺄셈이 나오면 뒷부분의 +는 -로 바꾸어 계산하는 방법을 생각함. 그런데 -의 경우, 부호를 바꾸면 +가 되기 때문에 이를 고려해야 한다고 .. 2023. 11. 12.

티스토리툴바