본문 바로가기

분류 전체보기

 (231)
06 - 메모리와 캐시 메모리 주기억장치에 RAM과 ROM 있다고 했는데, 여기서는 RAM 에 대해 먼저 정리한다그리고 캐시 메모리에 대해 정리한다. 06 - 1 RAM의 특징과 종류RAM의 특징 RAM에는 실행할 프로그램의 명령어와 데이터가 저장된다. RAM은 전원을 끄면 저장된 데이터와 명려어가 모두 날아간다. 그래서 휘발성 저장 장치라고 한다.전원이 꺼져도 유지되는 저장 장치는 비휘발성 저장 장치라고 한다. HDD, SSD, CO-ROM, USB 등이 있다.일반적으로 보조기억장치인 비휘할성 저장 장치에 보관을 하고 휘발성 장치에서 실행할 대상을 복사하여 저장한 뒤 그 데이터들을 가지고 프로그램을 실행한다.RAM의 용량과 성능RAM의 용량이 크면 저장할 수 있는 실행할 프로그램들의 데이터들이 많아 지기 때문에 그만큼 RAM이 보조..
05 - CPU의 성능 향상 기법 05 - 1 빠른 CPU를 위한 설계 기법 클럭컴퓨터의 논리회로에 가해지는 전기 신호의 단위로 Hz 로 표현한다.즉, CPU의 속도를 나타내는 단위이며, 이는 일정하지 않다. 최대 클럭 속도를 강제로 끌어올리는 것을 오버클럭킹이라고 한다.클럭 속도를 계속 높이면 발열 문제가 심각해진다. 따라서 클럭 만으로 CPU 속도를 올리는 것은 한계가 있다.코어와 멀티 코어코어 : 명령어를 실행하는 부품이다. 즉, CPU 안에 코어가 8개 있다면 명령어를 실행하는 부품이 8개라는 뜻이다. 이렇듯 2개 이상의 코어를 가지고 있으면 멀티코어 CPU,프로세서라고 부른다.코어를 계속 늘린다고 연산 처리 속도가 비례 증가 하지 않는다. 따라서, 중요한 것은 코어마다 처리할 명령어들을 적절하게 분산시키는 것이다.스레드와 멀티 ..
04 - CPU의 작동 원리 04 - 1 ALU 와 제어 장치 ALU   CPU 내부 계산을 담당한다.ALU가 받아들이는 정보피연산자 : 피연산자는 레지스터로부터 얻어온다.제어 신호 : 제어신호는 제어 장치로부터 얻어온다.ALU가 내보내는 정보결과 값 : 메모리로 바로 가지 않고 레지스터에 일시적으로 저장한다.플래그 : 플래그는 연산 결과에 대한 추가정보이다. 이 플래그는 플래그 레지스터에 저장된다.플래그 종류1. 부호 플래그 - 결과가 양수, 음수 인지 나타냄2. 제로 플래그 - 결과가 0인지 아닌지 나타냄3. 캐리 플래그 - 결과가 올림수나 빌림수가 발생했는지 나타냄4. 오버플로우 플래그 - 오버플로우가 발생했는지 나타냄5. 인터럽트 플래그 - 인터럽트가 가능한지 나타냄6. 슈퍼바이저 플래그 - 커널 모드, 사용자 모드 중 어떤..
동적계획법 메모리를 더 사용하여 이미 접근했던 배열을 추가 접근하지 않는 방식.  하향식 접근법 재귀에서 많이 사용 됨.dp 를 사용하는 알고리즘 이항 계수 ( 5 개 중 2 개 뽑는 경우의 수는?) 보통 이항 계수를 재귀로 푸는데 그러면 재귀 호출이 너무 많아진다.이를 방지하기 위해 메모이제이션이라는 방식을 이용한다.배열에 호출된 특정 방식에 대한 결과 값을 저장하여, 해당 특정 방식이 반복되어 호출 될 경우에 배열에 저장한 값을 가져오는 방식이 동적 계획법이다. int cache[50][50];int Combination(int n, int r){ // 기저 사례 if (r == 0 || n == r) { return 1; } // 이미 답을 구한 적 있으면 바로 반환 int& ret = cache[n][r]..
최소 신장 트리 최소 스패닝 트리 - 그래프/트리의 응용최소 스패닝 트리를 알아보기 위한 자료구조가 있다.상호 배타적 집합(Disjoint Set) -> 유니온-파인드 라고도 함.(합치기-찾기) 상호 배타적 집합 코드예로 알아본다. 리니지 배틀그라운드 라는 혼종을 만든다!혈맹전 + 서바이벌을 합치는 게임을 만든다면?1인 팀 1000명 (팀id 0 ~ 999 ) 고유 id 부여 동맹 시스템 있음 ( 1번팀 + 2번팀 = 하나의 팀 ) 이렇게 됨 일반적으로 팀 병합을 한다면 시간복잡도 O(n) 으로 안좋음void NewGame(){ struct User { // 내가 속해 있는 팀을 Id 로 구분 int teamId; // TODO }; // TODO : UserManager vector users; for (int ..
해쉬 테이블과 맵의 차이 해쉬 테이블 알아보기 해시 테이블에 관하여많이 나오는 질문 map vs hash_map(C++11 표준 unordered_map)map : 레드블랙트리.균형 이진 트리로 만들어져 트리 구조로 관리가 된다.그리고 균형을 맞추기 위해 트리의 한 계층으로 쏠리는 것을 방지하기 위한 조건과 알고리즘이 적용되어 있다.삽입/삭제/탐색 의 시간복잡도가 O(logN) 이다. 그런데 시간복잡도 상의 더 빠른 자료구조는 hash_map 이다.해쉬 맵은 메모리를 더 많이 사용하여 속도를 취하는 방식이다.다만, 충돌이 너무 많이 일어나지 않는다는 가정하에 해쉬 맵이 더 빠르다.충돌이 일어나면 다른 자리를 찾거나 체이닝 등에 의해 시간이 할애되기 때문이다. 충돌이 적다는 가정하에 hash_map 의 삽입/삭제/탐색의 시간복잡도는 O(1) 로 가장 ..
퀵 정렬 시간복잡도 : 최악의 경우 O(N^2) 평균적으로 O(NlogN) 이다. 데이터 복사가 없기 때문에 병합보다 일반적인 경우 더 빠름 시간복잡도 같아도pivot >= v[low] 이면 low 를 오른쪽 이동 반복pivot 1,2 의 반복문을 빠져나왔을때 low 1,2,3 반복low > high 가 되면 반복문 빠져나와서 v[pivot] 과 v[high] 스왑그 후 pivot 기준으로 나뉘어진 왼,오 를 다시 퀵 소트로 각각 pivot 다시 설정해서 정렬 반복void QuickSort(vector& v, int left, int right){ if (left > right) return; int pivot = v[left]; int low = left + 1; int hig..
병합 정렬 분할 정복이라는 개념이 들어간다. 분할 문제를 더 단순하게 분할정복 분할된 문제 해결결합 결과 취합 마무리3 단계로 이루어짐 만약 8개의 원소가 있다면 반으로 나눠서 각각 정렬한다.분할을 최대한 많이 함 그 다음 정렬된 각각의 문제들을 결합하여 다시 정렬.당연히 재귀적인 방식을 이용한다.시간 복잡도 : MergeResult 함수는 N 근데 MergeResult 를 반반씩 쪼개 질 때마다 사용하므로 logN 만큼 사용한다 즉, O(NlogN)이다. void MergeResult(vector& v, int left, int mid, int right){ int leftI = left; int rightI = mid + 1; vector temp; while (leftI mid) ..

티스토리툴바