최단경로 구하기 (Shortest Path) 어떤 그래프 G의 정점 A에서 다른 어떤 정점 B로의 최단경로는 A에서 B로가는 경로를 가운데 가장 작은 가중치 합을 가지는 경로를 말한다. 1. 최단경로를 구하는 방법최단 경로는 앞에서 살펴본 최소 비용 신장트리와 같이 그리디 알고리즘으로 구할 수 없다. 그리디 알고리즘을 사용하면 왜 구할 수 없는지를 생각해보자. 그리디 알고리즘은 현재 상태에서 가장 최적의 것을 선택해 나가는 방법이다. 그러나, 특정한 두 점사이를 연결하는 여러개의 경로들이 있을때, 가장 작은 가중치 합을 가지는 경로를 찾는 것은 이 경로들의 공통되는 끝점에서 가장 짧은 에지만을 선택해서는 찾을 수 없다. 즉, 최단경로는 자기 자신의 가중치는 높아도 전체적인 경로가중치를 줄여주는 간선이 있..
출처: http://en.wikipedia.org/wiki A-star algorithm은 초기노드에서 목표노드까지의 경로를 찾는 graph searching algorithm. Best-first search의 한 종류인데, 그러면 best-first search는 과연 무엇인가? Best-first search : 어떤 rule에 따라서 가장 promising하다고 판단된 노드부터 먼저 방문하는 depth-first search를 최적화하는 graph search 알고리즘이다. 이때 어떤 rule이란, 노드에 대한 extra 정보를 의미함으로써, heuristic function을 정의한다. Dijkstra의 shortest path finding 알고리즘도 best-first search의 종류에 ..
Von Neumann & Harvard Architecture
Von Neumann architecture 컴퓨터 아키텍쳐의 한 종류로서 데이터는 메모리에서 읽거나 메모리에 쓰기도 하는 반면, 명령어는 메모리에서 읽기만 하는 구조를 말한다. 이를 처음 고안한 폰 노이만의 이름을 따서 폰 노이만 아키텍쳐라고 부르며 현대 컴퓨터는 거의 대부분 이 방식을 따른다. 특징 1. 프로세서에게 메모리 특정 지점부터 실행하도록 지시할 수 있다. 이 때 데이터와 명령어 사이에 뚜렷한 구분이 없어서 주어진 내용을 무조건 실행한다. 2. 데이터 자체에 고유 의미가 없다. 즉, 이를 해석하는 프로그램에 의해 의미가 달라진다. 3. 데이터와 명령어는 메모리를 공유한다. 특정 프로그램에서 명령어인 내용은 다른 프로그램에서 데이터일 수 있다. Harvard architecture 하바드 아키..
RAID10과 0+1은 비슷하면서도 다릅니다. 비슷한면으로는 1. 용량이 같다. 2. 속도가 같다. 정도 입니다. 다른면으로는 1. 기술적으로 RAID10이 복잡한 반면 RAID0+1은 단순하다. 2. RAID10은 안정성이 높으나 RAID0+1은 상대적으로 낮다. 입니다. 지금부터 그 구조를 알려드리겠습니다. 두 레이드는 기본적으로 RAID0 과 RAID1의 조합으로 이루어진다는것에는 차이가 없습니다. 즉, 속도의 향상과 안정성의 향상이라는 두가지를 합쳐둔것입니다. 그러나 그 사소한 차이가 큰 결과를 만들어내는것이 어느것이 먼저냐는것입니다. 먼저 RAID0+1에 대해서 설명드리면, RAID0으로 구성한 다음 RAID1으로 미러링을 하는 구조입니다. 말로 설명하면 이해가 잘 안가니 그림 비슷한것을 그려서..
RAID 1+0 과 0+1의 공통점 과 차이점
RAID1+0 (혹은 10)과 0+1의 공통점 1. 용량이 같다. 2. 속도가 같다. RAID1+0 (혹은 10)과 0+1의 차이점 1. 기술적으로 RAID10이 복잡한 반면 RAID0+1은 단순하다. 2. RAID10은 안정성이 높으나 RAID0+1은 상대적으로 낮다. RAID 0+1 구성 RAID 1+0 구성 *" RAID 10 "이 좀더 안정성이 높은 이유!! RAID 0+1은 번 멤버중 하나 와 번 멤버중 하나가 동시에 장애가 생기면 데이타를 모두 잃을수 있다. 그러나 , RAID 1+0은 로 구성된 4개의 그룹(위의경우)중 각각 한개씩만 디스크가 정상이면 된다. 물론 디스크 멤버 2개가 동시에 고장 (즉 그룹단위로 고장)나면 데이타를 잃지만, 여러 경우의 수를 따져 확률적으로 계산 해보면 확률적..
RISC [ reduced instruction set computer ] 범용 마이크로프로세서의 명령세트를 축소하여 설계한 컴퓨터. 범 용 마이크로프로세서를 구성하는 요소에는 명령세트, 레지스터, 메모리 공간 등이 있다. 이중 명령세트는 RISC와 CISC(complex instruction set computer)의 2가지로 크게 분류할 수 있다. CISC란 소프트웨어 특히, 컴파일러 작성을 쉽게 하기 위해 하드웨어화할 수 있는 것은 가능한 모두 하드웨어에게 맡긴다는 원칙 아래 설계된 컴퓨터이다. 반면 RISC는 실행 속도를 높히기 위해 가능한 한 복잡한 처리는 소프트웨어에게 맡기는 방법을 택한 컴퓨터이다. RISC 의 특징을 CISC와 비교하여 알아보면 다음과 같다. 첫째, 명령의 대부분은 1머신 ..
