메타 스터디 그룹

[자료구조 목차]

1. 다익스트라 알고리즘 개요

1) 다익스트라 알고리즘 정의

• 너비우선탐색(BFS) 기반으로 하나의 시작 정점에서 부터 다른 모든 정점들까지 증가하는 거리의 순으로 최단 경로를 찾는 탐색 알고리즘
• 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘

2) 다익스트라 알고리즘의 특징

• 방향/무방향그래프 관계없이 사용가능
• 가중치가 음수인 edge 가 존재할 경우 사용이 불가함

3) 다익스트라 알고리즘 활용

• 네비게이션의 도시간 최단 거리 탐색
• 미로탐색 알고리즘
• 리우팅(OSPF) 프로토콜
• 공업입지론에서 최소 운송비 지점 구하기
• 루빅스 규브 해법
• A* 알고리즘 : 다이스트라 알고리즘 확장

2. 다익스트라 알고리즘 절차

1) 그래프 탐색과정 

2) 그래프 수행 절차

초기화 : 시작노드를 제외한 모든 노드의 거리정보를 무한대로 설정

시작노드를 기준으로 BFS 탐색으로 이웃 노드의 거리정보를 Update하여 최단거리 노드 탐색 및 방문을 반복적으로 수행

3. 계산 복잡성 및 단점

1) 계산 복잡성

• BFS 적용 미방문노트 탐색 O(V), 한노드당 엣지의 기대값 E / V
• 평균 복잡성 O(V2)  [ O(V2+E) ]

2) 단점 및 해결방법

• 가중치가 음수인 경우 탐색 불가
• 해결방법 양수화(모든 거리에 |음수거리|+한후 적용이 끝나면 절대값 - )

참조: 다익스트라 알고리즘 · ratsgo's blog

[자료구조 목차]

1. 버블 정렬

• 왼쪽끝에서부터 시작해서 인접하는 두 항목의 값을 비교하여 원하는 순서(오름차순 또는 내림차순)로 되어있지 않으면 서로 위치를 교환하는 정렬
• Sorted flag를 이용하여 정렬이 완료되었는지를 판단 -> 교환이 한번도 발생하지 않는다면 정렬이 완료된 것임
• 이웃노드간 비교 if A[i] < A[i+1] -> 비교횟수 O(N^2), 이동횟수 O(N^2), 도중 정렬 완성시 멈출 수 있음 - 최선O(N)

2. 선택 정렬

• 주어진 리스트 중에서 최소값(또는 최대값)을 찾고 그 값을 맨 앞에 위치한 값과 교체함으로써 정렬을 완성하는 알고리즘
• 최소값/최대값(Min/Max) 찾아 교체 -> 비교횟수 O(N^2), 이동횟수 O(N^2)

3. 삽입 정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 데이터를 정렬된 데이터에 삽입해 나가는 방법 -> 비교횟수 O(N^2), 이동횟수(최악 O(N^2), 최선 O(1)-발생 않할때) 

4. 쉘 정렬

• 특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어 각 부파일을 삽입 정렬하는 방식 - O(N^2)

5. 퀵 정렬

• 입력자료를 Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬하며, 분할된 각 부분 리스트에 대해 반복적으로 퀵 정렬을 수행하는 정렬 알고리즘
• 최악 -> 정렬된 입력데이터 O(N^2), 평균: O(N log N), 분할,정복 기법

6. 힙(Heap) 정렬

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법 - 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하여 정렬
• 완전이진트리, 힙의 삭제 이용(최대힙 - 내림차순) -> 평균,최악 O(N log N)

7. 합병 정렬

• 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 두 개 파일 합쳐 한개 파일 만듬. 추가적 메모리 필요, 2배 공간 -> N개 레코드 있을때, 2C(N/2) + N - 1, 평균, 최악 O(N log N)

※ 정렬(sort) 정리

버블정렬?  이웃노드간 비교 if A[i] < A[i+1] -> 비교횟수 O(N^2), 이동횟수 O(N^2), 도중 정렬 완성시 멈출 수 있음 - 최선O(N)

선택정렬? 최소값/최대값(Min/Max) 찾아 교체 -> 비교횟수 O(N^2), 이동횟수 O(N^2)

삽입정렬? 데이터를 정렬된 데이터에 삽입해 나가는 방법 -> 비교횟수 O(N^2), 이동횟수(최악 O(N^2), 최선 O(1)-발생 않할때)  

쉘정렬? 데특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어 각 부파일을 삽입 정렬하는 방식 - O(N^2)

퀵정렬? Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬 - 최악 -> 정렬된 입력데이터 O(N^2), 평균: O(N log N), 분할,정복 기법

힙정렬? 완전이진트리, 힙의 삭제 이용(최대힙 - 내림차순) -> 평균,최악 O(N log N)

2-Way merge? 두 개 파일 합쳐 한개 파일 만듬. 추가적 메모리 필요, 2배 공간 -> N개 레코드 있을때, 2C(N/2) + N - 1, 평균, 최악 O(N log N)

기수 정렬? 공간복잡도 큼, 비교없이 분배 -> O(N)

[CA/OS 목차]

스토리지 가상화 (Storage virtualization)

1. 이기종 스토리지 통합기술, 스토리지 가상화 개념

• 여러 대의 이기종 저장 장치를 저장 풀 하나로 만들어 여러 기기 간 데이터 이동 및 복제, 이기종 서버 간 블록 단위의 데이터 공유 등을 제공하는 기술
• 가상화 기능을 제공하는 소프트웨어 또는 별도의 하드웨어 장비 등을 통해 이기종 스토리지를 통합하는 기술
• (특징) 공유(Sharing), 단일화(Aggregation), 에뮬레이션(Emulation), 절연(Insulation)

• 공유 : 서버 내의 논리적 분할, 가상머신(VM), 가상 디스크, 가상 LAN(VLANs)
• 단일화 : 공유와 반대되는 개념으로 여러 자원에 걸쳐 가상화 공간 생성 가능
• 에뮬레이션 : 물리적으로는 존재하지 않는 기능을 가지는 것
• 절연 : 가상화 자원과 물리자원의 상호 맵핑,  RAID 스토리지 컨트롤러(장애 방지)

2. 스토리지 가상화 유형

1) 스토리지 가상화 유형

• 관리를 용이하게 하고, 애플리케이션의 가용성을 증가시키기 위해 가상화를 활용

2) 스토리지 가상화 세부 유형

유형	구현도	설명
블록 가상화		- 물리적으로 다른 스토리지 컨트롤러에 들어있는 유휴 디스크 조각을 모아서 가상 디스크를 생성 - 어플라이언스 형태(예, IBM SAN Volume Contoller 또는 IBM SVC), 지능적인 SAN 스위치(예, EMC의 Invista), 스토리지 컨트롤러 자체에 임베디드된 형태(예, 히타치의 TagmaStore)
파일 가상화		- 이기종 서버 간 파일공유를 통해 동일한 파일명을 사용하여 공통된 파일 그룹 접근 - 서로 다른 서버들간에도 HA(Hardware Address)를 위한 클러스터가 가능
테이프 가상화		- 디스크를 테이프 드라이브 자원인 것 처럼 에뮬레이션 하여 실제 데이터를 백업받는 기술 - 데이터 고속 백업 가능

3. 스토리지 가상화 사용 기술

[CA/OS 목차]

I. 칩 속의 시스템, SoC 개요

-. 하나의 칩 내에서 CPU, GPU, NPU, RAM, ROM, 컨트롤러 등의 다양한 역할을 구현하는 체제

-. 정보통신기기의 핵심기능을 처리하는 메모리, 디지털 회로, 아날로그회로, CPU, 센서, 안테나 소자 등이 하나의 칩에 집적된 시스템 

II. SoC의 특징

III. SoC 구조 및 기능

가. SoC 구조

나. SoC 기능

다. 주요 기술

IV. SoC 발열 문제 및 해결법

가. SoC 발열 문제

나. SoC 발열 문제 해결법

V. SoC 장단점

[CA/OS 목차]

개념 : 입출력 시간의 개선을 위한

• CPU가 주변장치를 제어하고 데이터를 처리하기 위해 입출력제어

필요성

- 데이터 처리에서 입출력은 반드시 필요하지만 중앙처리장치에 비해 많은 시간적 차이 있으며 또한 입출력 장치는 자율적으로 동작하므로 중앙처리장치에서처럼 동기화시켜 일률적 제어할 수 없음

- 입출력동작시간은 전체데이터처리시간에 비해 큰비중을 차지하기 때문에 입출력장치가 효율적으로 동작할수 있도록 제어하는 것이 매우 중요

입출력 제어방식 유형

• CPU 와 주변 장치의 처리 속도 차이로 인해, 주변장치와 시스템 특성에 따른 적절한 입출력 방식 필요

• I/O제어방식 중 DMA방식과 채널 제어방식이 대표적임

프로그램 입출력(PIO, Programmed I/O)

• 입출력 동작의 모든 과정을 CPU가 통제하고 개입하는 가장 단순한 방식

인터럽트 구동 입출력(Interrupt driven I/O)

• CPU는 I/O 모듈에 입출력 명령을 보낸 후, 입출력장치가 입출력 준비를 할 때까지 신경쓰지 않고 다른 작업을 수행
• 입출력 장치가 입출력 준비를 하게 되면 I/O 모듈이 인터럽트를 요청
• 인터럽트가 발생하면 CPU는 수행하던 작업을 멈추고 데이터 전송에 개입

(1) 데이지 체인(Daisy Chain)

• CPU는 인터럽트 요청(INTR)에 대한 응답으로 인터럽트 승인(INTACK) 신호 전송
• INTA 출력선을 I/O 제어기들에 직렬로 접속하는 방식

(2) 다중 인터럽트

• 각 I/O 제어기와 CPU 사이에 별도의 인터럽트 요구(INTR)선과 인터럽트 확인(INTA) 선을 접속하여 장치별 인터럽트 처리

(3) 소프트웨어 폴링(Polling)

• CPU가 모든 I/O 제어기들에 접속된 TEST I/O 선을 이용하여 인터럽트를 요구한 장치를 검사하는 방식

직접 메모리 접근(DMA, Direct Memory Access)

• CPU의 개입 없이, 기억장치와 입출력 모듈 간의 데이터 전송을 별도의 하드웨어인 DMA 제어기가 처리

• DMA 제어기가 버스 제어권을 획득하여 중앙처리장치의 개입 없이 주변장치와 메모리간 직접 데이터를 전송하는
  입출력 제어 방식

채널 제어방식

• 여러 주변장치가 연결되어 있는 채널제어기에 입출력 명령을 전달하여 CPU 의 개입없이 입출력을 수행하는 방식