전체 글(49)
-
[Operating System Concepts] Introduce_exercises
1.1 multiprogramming 환경과 time-sharing 환경에서 몇몇의 사용자들은 동시에 시스템을 공유한다. 이러한 상황은 다양한 보안 문제의 결과를 야기할 수 있다. a. 이러한 두 가지 문제는 무엇인가? ans -> 적절한 과정을 무시한 자원 분배 문제 및 데이터나 프로그램의 복사 혹은 강탈의 문제 등이 야기 된다. b. time-shared 시스템에서 전용 muchine와 같은 보안 수준을 제공할 수 있다고 확신 할 수 있나? ans -> 거의 불가능 할 것이라고 생각한다. 왜냐하면, 사람이 고안하여 만들어 낸 체계는 사람에 의해 해당 체계를 부술 수 있기 때문이다. 1.2 자원 사용 문제는 다양한 유형의 OS에 따라 다른 형식을 보여준다. 주어진 것들 중 어떤 자원이 가장 주의하여 다..
2019.12.27 -
[Graph] DFS와 BFS
DFS? Depth First Search의 약자이다. 즉, 깊이우선 탐색 알고리즘이다. 그렇다면 DFS 알고리즘은 어떻게 동작하는 지 알아보자. IDEA 위와 같이 생긴 그래프를 노드 0에서부터 깊이 탐색을 해보자. 1. 0 2. 0 -> 1 3. 0 -> 1 -> 5 5번 노드에서 갈 수 있는 노드가 없으므로 다시 뒤로 복귀한다. 4. 0 -> 1 -> 5 1번 노드 또한 더 이상 탐색할 수 있는 노드가 없으므로 0번으로 복귀한다. 5. 0 -> 1 -> 5 -> 2 0번에서 2번을 탐색할 수 있으므로 2번을 탐색한다. 6. 0 -> 1 -> 5 -> 2 -> 3 6. 0 -> 1 -> 5 -> 2 -> 3 -> 6 7. 0 -> 1 -> 5 -> 2 -> 3 -> 6 -> 7 7번 노드에서 0번으로..
2019.09.19 -
BOJ 백준 [11403] 경로 찾기
IDEA 문제를 탐색해보면 DFS로 문제를 풀 수 있다. CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #define MAX_NODE 100 #define INIT_PREV -1 int visited[MAX_NODE][MAX_NODE] = { 0, }; int adj[MAX_NODE][MAX_NODE]; int N; void dfs(int start, int prev, int now) { if (visited[start][now] == 1) { return; } if (prev != INIT_PREV) { //처음 탐색을 했을 때, start에서 now로 가는 경우는 start = now인 경우이다. //따라서, 본인에서 본인으로 갈 수 없..
2019.09.18 -
[Graph] 다익스트라
다익스트라 알고리즘? 그래프에서 노드들간의 최단 거리를 알아내기위해 사용하는 알고리즘이다. 다익스트라 알고리즘은 매우 직관적인 알고리즘이다. 그렇다면 다익스트라 알고리즘이 어떻게 동작하는지 알아보자. IDEA 예를 들어 아래와 같은 상황을 생각해보자. 위 와같은 지도를 보자. 집에서 각각의 상점까지의 최단거리를 알아내고자한다. 이때 다익스트라 알고리즘을 사용하여 해결해보자. 1. 처음 집에서 출발을 한다. 집에서 처음 출발할때, 가지고 있는 정보는 집에서 집으로 갈 때, 0이라는 시간이 소요된다는 것 뿐이다. 이제 집에서 바로 갈 수 있는 장소들에 대해 탐색해보자. 2. 집에서 바로 갈 수 있는 장소들 중 상점, 영화관, 은행의 경우 기존의 거리(INF)보다 집에서 집까지의 거리 + 집에서 각 위치들 까..
2019.09.18 -
BOJ 백준 [2156] 포도주 시식
IDEA 1 무식하게 풀기 재귀함수를 통해 완전탐색을 하여 문제를 해결해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #define MAX_WINE_CUP 10000 #define MAX_DRINK_CON 2 int wineAmount[10001] = { 0, }; int wineCupCount; int totalDrink; void drinkWine(int cupIndex, int drinkAmount, int continuous) { if (cupIndex > wineCupCount) { totalDrink = max(totalDrink, drinkAmount); return; } drinkWine(c..
2019.09.18 -
BOJ 백준 [2748] 피보나치 수
일반적으로 피보나치 수를 이용하여 문제를 해결하려고 해보면, 1 2 3 4 5 6 7 int getFibo(int n) { if (n long long 자료형을 사용해 주자. 그리고 시간 복잡도의 경우 2^n이므로 최악의 경우 2^90 = 1,237,940,039,285,380,274,899,124,224 이므로, 1초의 시간을 넘어 서게 된다. 위의 경우, 어떻게 문제를 해결해야 할까? IDEA 1 for 문으로 탐색해서 피보나치 값을 구해보자. 1 2 3 4 5 6 7 8 9 10 if(n
2019.09.12