본문 바로가기

알고리즘

분할정복(Divide and Conquer) #include #include #define SIZE 16 using namespace std; template void merge_sort(data *arr, int size); int main() { int arr[SIZE]; srand(time(0)); for(int i = 0 ; i < SIZE ; i++) { arr[i] = rand()%100 + 1; cout 더보기
메모리 계층(Memory Hierarchy) 메모리 종류 : 1. 메인(Main) 메모리 : 램(RAM) (D램) 2. 레지스터(Register) : CPU 안에 내장되어 있어서 연산을 위한 저장소 제공 3. 캐쉬(Cache) : S램. CPU와 램사이에서 중간 저장소 역할 4. 하드디스크(Hard Disk)와 이외 장치 : 하드 디스크, I/O 장치 등등 메모리 계층 구조(Memory Hierarchy) : 메모리들은 프로그램이 실행하는 동안 데이터의 입력 및 출력을 담당한다. 메모리들의 차이는 CPU 와의 거리에서 온다. CPU와의 거리가 가까울수록 빠르고 용량이 작으며 멀수록 느리고 용량이 크다.(기술과 돈의 문제) 하드디스크에 있는 내용은 프로그램의 실행을 위해 메인 메모리로 이동한다. 메인 메모리에 있는 일부 데이터도 실행을 위해 L2 캐.. 더보기
base64 인코딩 알고리즘 base64 개념 : 64진수를 베이스로 하여 정보를 표현한다.(컴퓨터는 2진수 기반) 따라서 최소비트 (64=2^6) 6 비트를 가진다. 하지만 컴퓨터는 기본이 되는 정보를 1 바이트(8 비트)를 사용하여 표현한다. (2=2^1 1 비트이지만... ASCII 코드 1바이트 사용) 그래서 6 과 8의 최소공배수인 24 비트(3 바이트)를 기준으로 하여 정보를 표현한다. 24비트는 6비트씩 4개가 나오므로 base64로 인코딩된 값의 길이는 4의 배수이다. 위의 그림과 같이 값을 24비트에 걸쳐서 표현한다. 앞에서부터 6비트씩 짤라서 4개의 문자를 만든다. 여기에 심볼을 대입한다. base64 심볼 : (ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234.. 더보기
스케줄링 알고리즘과 우선순위 우선순위(Priority) 스케줄링(Scheduling) 알고리즘 : 각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행한다. 우선순위가 다른 두 프로세스를 동시 실행할 때, 우선순위가 높은 프로세스가 작업을 마치지 않는다면(블로킹 상태가 되거나 I/O 작업을 하지 않는다면) 우선순위가 낮은 프로세스는 절대로 실행되지 않는다. (기아 상태 : Starvation) 라운드 로빈(Round-Robin) 스케줄링 알고리즘 : 우선순위가 동일한 프로세스들의 형평성 유지를 위해 정해진 시간 간격(타임 슬라이스(Time Slice), 퀀텀(Quantum))만큼만 실행하고 CPU 할당을 넘긴다. 타임 슬라이스 ↑ -> 반응속도 ↓ 타임 슬라이스 ↓ -> 성능 ↓ (잦은 컨텍스트 스위칭 발생으.. 더보기
DFS를 이용한 스도쿠 문제 풀이 알고리즘 #include using namespace std; int sdocu[9][9]={0}; // 정답을 저장할 배열 int success = 0; // 성공변수 int dfs(int c, int r) { if(c==9) // 끝에 도달시 { success = 1; return 0; } if(sdocu[c][r]!=0) // 숫자가 있다면 { if(r==8) { c++; r=0; } else { r++; } dfs(c, r); if(success==1) { return 0; } if(r==0) // 되돌아가기 { c--; r=8; } else { r--; } return 0; } else { int temparr[9]={1,2,3,4,5,6,7,8,9}; // 빈칸에 들어갈 수 있는 숫자배열 for(int.. 더보기