Backtracking
Backtracking Backtracking을 통해 미로에서 길을 찾는다고 생각해 보자. Dead End에 도달할 때까지 경로를 따라간다. Dead End에 도달하면 Fork지점까지 되돌아간다(Backtrack). 1에서 선택한 경로와 다른 경로를 선택한다. 만약 어떤 경로가 Dead End로 도달할 것을 미리 알 수 있는 sign이 있다면? 특히 이런 sign이 경로의 초반부에서 발견될수록 많은 탐색 시간을 절약할 수 있다. Backtracking Technique 어떤 집합…
Deadlock(1)
Deadlock - Deadlock conditions 프로세스는 한정적인 resource를 사용한다. 이때 다른 프로세스가 사용중인 resource를 요구할 수 있다. 이 때 발생하는 문제에 대해 좀 더 직관적으로 살펴보기 위해 system model관점에서 살펴보자. System Model 시스템은 resource와 process로 구성된다. resource들은 Resource Type으로 분류한다.(R1, R2, R3, ... , Rm) 각 Resource Type들은 CPU cyc…
소프트웨어시스템설계 2023-05-01 수업정리
Flow Review - SDLC Review - White Box Testing Black Box Testing Review - SDLC 어느 정도의 규모가 있는 조직에서는 implementation을 담당하는 개발자, 설계를 검토하는 설계자, PM이 모두 따로 존재한다. 각각의 단계에 대해서 테스트를 담당하는 사람 역시 따로 존재한다. 일반적으로 unit test 단계까지는 코드를 설계한 프로그래머가 담당한다. Review - White Box Testing 소스코드를 이용하여…
Nachos(2)
#1 코드 selfTest2 메소드와 SimpleThread클래스를 아래와 같이 작성하여 Round-Robin 스케줄링을 구현할 수 있다. selfTest2() public static void selfTest2() { Lib.debug(dbgThread, "Enter KThread.selfTest2"); int timeslice; int numberOfThreads; int burstTime1; int burstTime2; String fileName = &q…
Greedy Algorithm - Dijkstra Algorithm
Review Prim's Algorithm vs Kruskal Algorithm Prim's Algorithm Time Complexity : n*n Kruskal's Algorithm Time Complexity : m*log m(n-1 <= m <= n(n-1)/2) Sparse graph : Kruskal Algorithm Kruskal Algorithm(n*log n) is faster than Prim's Algorithm Highly connected graph :…
Greedy Algorithm - Kruskal Algorithm
Kruskal's Algorithm 그래프의 개별 노드로 구성된 V개의 subset을 생성한다. edge들을 weight에 따라 오름차순으로 정렬한다. edge를 선택했을 때 두 개의 서로 다른 V를 연결한다면, 해당 edge를 final edge set에 추가시키고, 두 V를 merge 한다.(이제 두 subset은 하나의 집합으로 인식한다.) subset의 집합이 하나만 남을 때까지 3을 반복해서 수행한다. 다음 그래프에 대해 Kruskal Algorithm을 적용해 보자. …
Greedy Algorithm - Prim Algorithm
Prim's Algorithm 그래프에서 하나의 꼭짓점을 선택한다. 꼭짓점과 edge를 구성하는 vertex중 edge의 weight이 가장 작은 vertex를 선택한다. 2에서의 vertices와 edge를 구성하는 vertex중 edge의 weight이 가장 작은 vertex를 선택한다. 더 이상 선택되지 않은 vertex가 없을 때까지 1~3을 반복한다. Code /* Code by https://4legs-study.tistory.com/m/112 */ #include <ios…
Greedy Algorithm
Greedy Algorithm Greedy Algorithm은 "순간순간 선택의 시점마다 항상 그 상황에서 최선인 선택을 하는" 알고리즘이다. 아래는 Greedy Algorithm의 예시이다. >10원, 50원, 100원, 500원 동전이 무한 개 있다. 코인의 개수를 가장 적게 선택하여 730원을 지불하려면 어떻게 해야 하는가? 이를 해결하기 위해서는 동전의 선택 시점마다 항상 선택 가능한 동전 중 금액이 가장 큰 동전을 선택하면 된다. Greedy Algorithm…
소프트웨어시스템설계 2023-04-24 수업정리
Flow SDLC Unit Testing JUnit 을 이용한 Unit Testing SDLC(Software Developement Life Cycle) 구조도의 그림이 V형태여서 V-model이라고도 한다. Acceeptance Testing의 경우에는 defect를 찾는 것이 목적이 아니다. User Requirements에 부합하는지 검사하는 것이 목적이다. System Testing, Integration Testing, Unit Testing은 defect를 찾는 것이 목적이다…
Mac Setting
Flow Terminal Setting Drive Setting Flow Applications Communicative Applications Other Applications Terminal Setting iterm iterm2 Download Oh-my-zsh Oh-my-zsh sh -c "$(curl -fsSL https://raw.githubusercontent.com/ohmyzsh/ohmyzsh/master/tools/install.sh)" Themes…
프로그래밍언어론 2023-04-18 수업정리
Flow Extended BNF Syntax Chart Recursive-Descent Parser Extended BNF BNF(Backus-Naur-Form에서 추가로 몇 가지 meta-symbol이 추가된 표기법이다. $\epsilon, \lambda$ 등 아무 것도 없음을 나타낼 경우 그냥 공백으로 표기한다. optional Elements [ ... ] <number> ::= <digits>[.<digits>] 숫자의 옵션으로 소수점및 소수 부…
프로그래밍언어론 2023-04-13 수업정리
Flow Review Prolog Intro SWI-Prolog & Demo Review Axiomatic System(공리계) 공리의 유한 집합, 사실(fact)과 추론 규칙(rules)로 구성된다. 사실(predicate) : 아래와 같이 표현 가능하다. 항상 참이다.$$\frac{true}{fact}$$ 추론 규칙(rules) : 가정(hypothetics) 술어들을 바탕으로 결론 술어를 도출해 내는 규칙이다. 아래와 같이 표현 가능하다.$$\frac{predicate^{\…
Synchronization(2)
Synchronization Hardware Lock critical section으로 진입하지 못하도록 key를 이용하여 lock하는 것 hardware의 atomic instruction을 사용하여 구현한다. 대부분의 현대 기기들은 atomic hardware instruction을 지원한다. high level코드를 non-interruptable하게 만드는 역할을 한다. test와 set를 사용하여 구현하거나 swap을 이용하는 방법으로 lock을 구현한다. test, set, swa…
프로그래밍언어론 2023-04-11 수업정리
Flow PL Review Axiomatic System PL Review Programming Language는 Syntax와 Semantic으로 나타내어진다. Syntax : CFG(Grammar)로 표기 Semantic Static Semantic Attribute Grammar : 속성 문법, (문법 규칙 + 속성 계산 규칙)을 통해 컴파일 이전에 의미에 대한 정의를 끝낸다. Dynamic Semantic Operational Semantics : 추상기계의 상태변화로 의미…
Synchronization(1)
Critical Section Problem The Problem of Concurrency(동시성 문제) 아래와 같은 프로그램에서, OS는 한 번에 여러 작업에 대해서 연산한다.(juggling)#include <stdio.h> #include <stdlib.h> #include "common.h" volitale int counter = 0; int loops; void worker*(void * arg) { int i; for(i = 0; i…