본문 바로가기

CS

 (43)
Chap 5-2.연속 행렬 곱셈 연속 행렬 곱셈(Chained Matrix Multiplication) 문제 = 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제 행렬 곱셈 (1) 두 행렬의 곱셈이란? 두 행렬 A, B가 있다. A = 10 x 20 B = 20 x 5 라면 총 곱셈의 횟수 = 10 * 20 * 5 = 1000이다. (2) 3개의 행렬 곱셈 A = 10 x 20 B = 20 x 5 C = 5 x 15 행렬의 곱셈은 결합법칙 성립하므로 (A* B) * C , A * ( B * C) 이 둘 다 성립한다. 하지만 둘의 결과값는 같지만 곱셈의 횟수는 전자가 더 적다.(과정이 다르다) [ 행렬 곱셈의 주의점 ] 주어진 행렬의 순서를 지켜서 “반드시 이웃하는 행렬끼리” 곱해야 한다. 동적 알고리즘 적용 (1) ..
Chap 6. 프로그램 실행 [ 프로그램의 실행 ] 시스템 콜을 통해 커널 함수를 호출한다. → 그러면 커널 모드가 된다. 유저모드와 커널 모드가 반복된다 os는 block 단위로 읽어들인다. (timer 시간) [ 저장장치 계층구조 ] primary (Executable) [Registers] CPU안에 있음 공간은 적지만 빠른 속도로 처리를 한다. [1 Cache Memory] ISA에 포함되지 않을 수도 있고 포함될 수도 있다 메모리에서 레지스터로 올리는데 많은 내용을 올릴 때 시간이 많이 걸릴 것이다. 하지만 캐시에 저장했다가 다시 사용하고 싶으면 메인 메모리에서 레지스터로 바로 가는 것이 아니라 캐시에 저장된 값을 바로 사용하는 것이다. → 속도가 더 빨라진다. 메인메모리 보다는 빠르고 레지스터보다는 느리다. 버퍼같은 중간..
Chap 5. 컴퓨터 시스템 구조 위의 그림을 바탕으로 자세하게 설명할 수 있다. -cpu의 작업 공간이 메모리이기 때문에 cpu는 매 클럭 사이클마다 메모리에서 기계어를 하나씩 읽어서 실행을 하게 된다. -맨오른쪽에 4가지 세로로 그림이 나열되어 있다. 이들은 IO 디바이스이며 input을 담당하는 키보드, output을 담당하는 모니터, 프린터가 있다. 맨 위에 있는 것은 하드디스크인데 이는 보조 기억 장치로 볼 수 있고 IO device라고 볼 수도 있다. 왜냐하면 디스크에 있는 메모리를 읽어서 메모리로 읽어들이기도 하고(input device), 동시에 처리 결과를 디스크에 있는 파일 시스템에 저장을 하는 역할(output device)을 하기 때문이다. -device controller는 각각의 IO디바이스들은 그 디바이스를 전..
Chap 4. 운영체제란? 1. 운영체제란 ? 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 (소프트웨어이긴 하지만 실제론 시스템 소프트웨어라고 함) 즉, application과 하드웨어를 연결하는 중간자 역할 좁은의미(협의의 운영체제) = 커널 학문적 관점에서는 운영체제를 커널로 포커싱 함 운영체제의 핵심 부분으로 메모리에 상주하는 부분 넓은 의미(광의의 운영체제) = 커널 + 알파 커널 뿐 아니라 각종 주변 시스템 유틸리티를 포함한 개념 *시스템 유틸리티 : 사용자가 사용할 수 있는 프로그램을 의미하며 주변 장치를 컨트롤하는 드라이버 같은 것들이 깔려 있다. 2. 운영체제의 목적 크게 2가지의 목적이 있다. (1) 하드웨어를 편리하게 사용할 수 있는 환경을 제공 a. ..
Chap 3 - 3. static 라이브러리와 shared 라이브러리 씨언어를 사용하여 화면에 결과를 출력할 때 printf를 사용한 경험이 있을 것이다. printf를 사용하기 위해 #include 라는 헤더 파일을 선언해야 했다. 이때, 헤더 파일에는 함수가 있다는 정보만 선언되어 있고 실제 코드는 "라이브러리 파일"에 있다. 즉, 헤더 파일과 라이브러리 파일 둘 다 있어야 printf 함수를 실행할 수 있다는 것이다. 자세하게 보자면, 헤더 파일[ stdio.h ] 에는 라이브러리 함수의 선언만 있다. [ extern printf(); ] /usr/include 혹은 /usr/include/sys 에 미리 정의된 헤더파일들이 있음 (ex) stdio.h 실제 함수의 정의(디테일한 내용)는 라이브러리 파일에 있다. ex) printf의 함수가 어떤 일을 하는지, 함수의..
Chap 3 - 2. 부분 컴파일 부분 컴파일이란? = 여러 개의 파일들을 각각 컴파일하고 링커를 통해 합쳐져서 실행 파일로 만드는데, 여러 개의 파일들을 각각 컴파일하는 것을 부분 컴파일이라고 한다. - 부분 컴파일을 하게 되면 symbol table이 만들어지게 된다. 심볼 테이블은 각각의 변수들은 어떤 것을 사용하는지에 대해 정리되어 있다. 그것들을 이용해서 컴파일을 한 오브젝트 파일들 몇개를 서로 링크하여 하나의 실행 파일로 만드는 것이다. -변수나 함수는 거의 비슷한 개념이다. ⇒ symbol이라고 함 (변수나 함수 등의 이름을 말한다.) int a = 1; // 변수 선언 void func(int a) // 함수 선언 { a++; } -변수 선언을 할 때는 변수에 해당되는 메모리의 주소를 가리키고 있는 것이 'a' 라고 할 수..
Chap 3. 고급 언어의 기계어 변환 및 실행 고급 언어에서 기계어로 변환되는 과정을 설명 고급언어 -> 기계어로 변환되는 과정 “고급 언어 프로그램(source file)” → [컴파일러] → “어셈블리 프로그램” → [어셈블러] → “기계어 프로그램(object file)” or “기계어 프로그램(object file 또는 library file)” → [링커(linker)] → “기계어 프로그램(executable file)” or “공유 라이브러리” → [로더(loader)] ⇒ “메모리” 먼저, 각 변환기에 대해서 살펴보자. [ 컴파일러 ] 고급 언어 프로그램을 어셈블리 프로그램으로 바꾸는 것이다. 여기서 고급 언어 프로그램으로 작성한 것은 시스템 종류에 무관하다. ex) 씨언어로 작성된 파일인 a.c라는 소스파일을 각 시스템들이 가지고 있..
Chap 5-1. 0-1 배낭 문제 0, 1 배낭 문제 조건 4kg을 담을 수 있는 배낭 넣을 수 있는 물건 A, B, C가 있다. B의 무게 = 4, 가치 = 30 C의 무게 = 3, 가치 = 20 A의 무게 = 1, 가치 = 15 가장 단순한 방법은 모든 물건의 조합을 시도를 해서 총 가치를 구한 다음에 가장 가치가 높은 경우를 선택하는 것이다. 이렇게 한다면 지수 시간의 시간 복잡도를 갖는 문제이다. 2^n의 경우의 수이다. 이 문제를 (1) 재귀 방법으로 풀 수 있고 (2) DP방법으로도 풀어볼 수 있다. (1) 재귀 방법 #include #define MAX(a, b) ((a) > (b) ? (a) : (b)) int knapSack(int W[], int V[], int n, int c) { if(n 다음 물건으로 넘어감, 배낭..
1. 블록체인의 동향 중요한 5가지 혼자하는 비즈니스가 아니라 여러 비즈니스 간의 협업해서 이루어지는 비즈니스임 참여자들이 가지고 있는 유무형의 자산을 스마트 컨트랙 기반으로 거래를 투명하게 공유하는 기술 블록체인의 동향 토큰 경제학 = 토큰 관련된 영역들이 많은데 그 중에 중요한 용어 중에 하나가 tokenization이다. 우리가 가지고 있는 자산을 디지털로 표현하는 것 이렇게 되면 자산은 소유권과 권한들을 가질 수 있는데 이러한 권한들을 블록체인 기반의 디지털로 표현하는 프로세스를 토큰화라고 한다. 일반적으로 토큰화라고 하면 자산의 종류가 6가지 있는데 그 중에 중요한 영역인 4가지에 대해서 살펴보자. 1. 암호화폐 퍼블릭 블록체인인 이더리움 토큰의 하나의 자산이다. 하지만 암호화폐는 실질적으로 법적 화폐 역할을 할 수..
Chap 5. 동적 계획 알고리즘 Dynamic Programming(DP) 알고리즘 -입력 크기가 작은 부분 문제들을 해결한 후에 -그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해어 -최종적으로 원래 주어진 입력의 문제를 해결 [문제] n개의 원소를 갖는 문제 같은 형태로 문제를 해결해나가지만 n개보다 작은 값으로 (작은 문제로 ) 만들어서 푸는 방법 (1) 최적의 하위구조 특성 k < n 인 k개의 원소를 갖는 문제를 정의하고 문제를 풀었더니 그것이 최적의 풀이법이고 점점점 작은 문제들을 결합해서 최종 풀이법이 완성되어지는 형태의 특성을 갖는 문제를 “최적의 하위구조 특성을 갖는 문제”라고 부른다. 예시) 두 도시를 자동차로 갈 수 있는 최단 경로 A도시 B도시 C도시가 있는데 A에서 C로 가기 위해서는 A-B의 최단 경로를..

티스토리툴바