분류 전체보기
-
가상화기술 Type2개발/가상화 2016. 9. 11. 19:12
가상화 기술 Type2는 가상화 기술을 애플리케이션의 형태로 구현하는 방식이다.대표적인 예로는 VMware, Virtual Box처럼 윈도우나 리눅스에 설치 할 수 있는 소프트웨어이다. 이러한 형태의 구현 방식은 기존 PC 시장에 쉽게 가상화 기술 소프트웨어를 도입 할 수 있다는 이점이 있다. 또한 Host OS가 제공하는 시스템콜과 하드웨어 제어권을 빌려오는 형태여서 여러가지 요소들을 신경쓰지 않고 구현(실제로는 생각을 많이 써야 하지만 처음부터 다 만들어 가는것은 아니기 때문에)할 수 있다. 애플리케이션 형태이기 때문에 안전성에 문제가 생겨도 Host OS 자체의 안정성은 침해하지 않는다는 장점이 있다. 하지만 위 방식은 느리다. 가상화 소프트웨어가 하드웨어를 직접 통제하는 것이 아니기 때문에 하드웨..
-
가상화 기술의 유형개발/가상화 2016. 9. 6. 19:24
가상화 기술은 어떤 방식으로 구현하느냐에 따라 크게 Type 1& Type 2로 나뉜다. 직관적으로 이해하기 위해 먼저 그림으로 표현하면 다음과 같다. 위 두 그림의 가장 큰 차이점은 Hypervisor(가상머신)의 존재 형태이다, Type1에서는 Hypervisor가 하드웨어를 관리하는 운영체제의 일종으로 보이고, Type2에서는 Host OS의 application과 동등한 형태를 띄는 것으로 보인다. 가상화 기술은 "Hypervisor를 어떠한 형태로 개발할 것이냐"에 따라 두가지로 나눌 수 있다. - Type1 : Hypervisor를 OS의 형태로 개발한다. - Type2 : Hypervisor를 Application의 형태로 개발한다. 아마 대부분의 사람들에게 익숙한 형태는 Type2일 것이다..
-
1937알고리즘/acmicpc 2016. 9. 6. 18:50
모든 경로를 탐색하려고 하면 경우의 수가 무척 많아져서 어렵다. 여기서는 문제의 조건을 잘 살펴야 한다. - 판다는 상,하,좌,우 중 하나의 경로로 이동한다 - 대나무의 양은 증가하는 순서여야 한다. 위 두가지 조건만을 이용해서 dp를 만들어 줄 수 있다. dp[x][y]는 어떤 위치(x,y)로 도달 할 때 판다가 최대 살 수 있는 일 수를 가지고 있다고 하자. 그럼 다음과 같은 점화식을 적용 할 수 있다. dp[x][y] = (상하좌우에 있는 대나무중 현재 위치의 대나무보다 양이 작은 값들의 dp중 가장 큰 것) + 1 이해를 돕기 위해 그림으로 부연 설명을 하면.. 파란색으로 칠해둔 위치의 dp값을 업데이트 하려고 한다. 이때 파란색 위치로 접근 할 수 있는 경로는 (x,y)위치의 상하좌우중 (x,y..
-
4095알고리즘/acmicpc 2016. 8. 15. 21:54
행렬안에서 1로 이루어진 최대 정사각형을 찾는문제. 가장 쉽게 생각한다면 모든 점에서 만들 수 있는 최대 정사각형을 탐색해보는 방법이 있지만 이럴경우 O(N^4)로 시간초과가 날 수 밖에 없다. 하지만 구하고자하는 사각형의 형태가 정사각형인점을 잘 이용하면 다이나믹 프로그래밍을 이용해 O(N^2)안에 해결 할 수 있다. 어떠한 위치에서 정사각형을 만들 때, 이전에 만들어진 정사각형의 정보를 활용할 수 있는 방법을 생각해보자. 4번(X, Y) 위치를 꼭지점으로 하는 정사각형을 만들려고하자. 그러면 4번위치 주위에 1, 2, 3번의 사각형들을 생각해볼 수 있다. - 1번은 (X-1, Y-1)을 오른쪽 아래 꼭지점으로 할 때 가장 큰 정사각형이다. - 2번은 4번에서 위로 그을 수 있는 최대 선분의 길이다. ..
-
회전초밥알고리즘/algospot 2016. 8. 1. 23:06
항상 이런 DP문제들을 보면 어떤 값을 배열의 index로 표현할까가 나의 관심사였다. 가장 배열에 넣을 만한 값들은 예산에 해당하는 값들이었고 이 값들이 배열의 최대 범위를 초과하지 않기를 기도할 뿐이었다. 하지만 최대 범위를 초과한다면.. 그 문제는 내겐 그때부터는 DP문제가 아니였다. 어떻게 최적화 할 것인가 머리를 짜매다가 풀지 못한 문제로 남아버렸다. 책에서본 회전초밥문제도 그랬다. 단순 DP문제로 풀 수 있을 줄 알았는데 예산의 범위가 10^9이하여서 배열로 넣기는 무리였다. 문제의 힌트로 가격이 항상 100의 배수라 10^7정도는 배열에 넣으면 되겠다 생각했는데 메모리의 크기 제한이 64MB였다. int형으로 배열의 크기가 10^7로 잡자니 메모리가 초과할 것 같고 그렇다고 최대한 메모리를 ..
-
블록게임알고리즘/algospot 2016. 8. 1. 22:11
조합게임의 예제로 나온 문제. 모두가 최선을 다했을 때 이길 수 있는 경우에 대한 것은 앞에서 설명했으니 넘어가고 블록과 보드게임의 상태를 비트 연산을 이용해 어떻게 깔끔히 표현했는지에 주목하자. void precalc() { for(int y = 0; y < 4; y++) for (int x = 0; x < 4; x++) { vector cells; for (int dy = 0; dy < 2; dy++) for (int dx = 0; dx < 2; dx++) cells.push_back(cell(y + dy, x + dx)); int square = cells[0] + cells[1] + cells[2] + cells[3]; for (int i = 0; i < 4; i++) moves.push_back..
-
가상화 기술이란?개발/가상화 2016. 7. 31. 23:22
대학교 1학년때 컴퓨터에 대해서 관심을 갖기 시작할 시절, 동기중 한 명이 Virtual Box라는 것을 이용하면 하나의 PC로 여러개의 운영 체제를 구동 할 수 있다는 것을 알려 주었다. 그 친구는 자신의 집에서는 윈도우 위에 우분투라는 것을 올렸다며 엄청난 기술이라고 호들갑을 떨었는데 당시 나는 전공 초짜였지만 기술 지식에서 뒤쳐지는게 싫어서 "오 그래? 대단한걸? 나도 집에가서 해봐야겠다!"라고 말해놓고 우분투는 대체 뭐고 왜 하나의 PC에 여러 개의 운영체제를 올려야 하냐며 혼잣말을 했었던 기억이 난다. 하지만 운영체제 수업에서 리눅스라는 환경을 처음으로 경험하게 되고 후에 RoR(Ruby on Rails), NodeJs등을 이용해 개발하는 일이 늘어나면서 리눅스는 나와 뗄레야 뗄 수 없는 사이가..
-
11437알고리즘/acmicpc 2016. 7. 30. 14:21
LCA를 푸는 문제다. LCA 최적화 알고리즘은 이미 정리해두었으니 넘기자. 문제에 주어진 간선을 가지고 어떻게 트리의 형태로 만드느냐가 LCA를 풀기 위한 조건이다. 일반적으로 간선에 대한 자료구조들은 2차원 배열을 이용해서 표현하지만 N이 10000을 넘어가면 2차원 배열의 최대 크기를 초과하게된다. C++에서는 vector를 사용해서 위와같은 문제를 간단히 해결 할 수 있지만 경우에 따라서 vector를 사용하지 못하는 상황도 존재한다. 간선 정보들을 필요할 때 마다 신속히 접근하는 자료구조가 중요한데 매번 모든 간선 정보O(N)를 찾아볼 수도 없을 노릇이다. 이런 경우에는 특정 경우 대해서 정렬을 해주는 방법이 유용하다. 간선에 대한 정보를 from들에 대해서 정렬을 해주고 각각의 시작점을 확인해..