메타 스터디 그룹

[자료구조 목차]

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)

[Site Map]

* 토픽 각 단락 당 3줄 간격 유지
* 꼭 포함되어야 하는 중요 단어는 굵게 + 빨간게 표시
* 최대 44자 이상이 안되도록 주의

ISO 56000 - 혁신경영의 국제표준

- 조직이 혁신관리 시스템을 구현, 관리 및 개선할 수 있는 프레임워크를 제공하도록 설계된 국제표준

버추얼 휴먼

가상 인간, 디지털 휴먼, 메타 휴먼, 사이버 휴먼 등 다양한 명칭인, 실존 인물이 아닌 소프트웨어로 만든 가상의 인간

TTS(Text to Speech)

문서, 웹페이지, E-BOOK등에서 텍스트를 읽고 컴퓨터 스피커를 통해 합성된 음성생성기술

O-RAN/Open-RAN(Radio Access Network) - RAN 가상화 Whitebox

운영효율성을 높이고 종속성(Lock-in)을 탈피하기 위하여 인터페이스, 운영체제 등을 개방형 표준으로 구축한 통신 기지국 네트워크

DAO(Decentralized Autonomous Organization)

중앙 주체의 개입 없이 개인이 모여 자율적으로 제안, 투표, 의사결정, 운영하는 탈 중앙화 자율조직

와이파이 7

VR, AR, 게이밍, 클라우드 컴퓨팅에 적용 가능한 30Gbps 이상의 처리량을 갖고 대기 시간이 매우 짧으며 가장 빠른 WiFi 표준

메디컬 트윈

현실세계의 건강정보로부터 가상의 의료환경에서 질병의 진단 및 예후를 판단하는 디지털 의료 지능화 융합 기술

VE(Value Engineering, 가치 공학)

- 소비자 관점에서 제품이나 서비스의 가치를 극대화할 수 있도록 공학적인 기법을 활용한 경영기법

ISO/IEC 18013-5

2021년 9월 의결된 개인의 신원 및 자격을 증명하는 모바일 운전면허증 전용 국제표준 (Mobile driving license (mDL) application)

표준특허

해당 특허를 침해하지 않고는 제품의 제조.판매나 서비스 제공이 불가능한 특허로 국제표준화기구(ISO,ITU등) 에서 제정한 표준규격에 포함되는 특허

[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 장단점