CS

해시 함수의 종류

MD4 와 MD5 ① MD(Message Digest)4 Rivest 가 1990년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다. 그러나 Dobbertin에 의해 MD4의 해시 값의 충돌을 발견하는 방법이 고안되어 현재는 안전하다고 할 수 없다. ② MD(Message Digest)5 MD4 를 만든 Rivest 가 1991년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다. 여기서 입력은 512-비트 블록들로 처리된다. 전수 공격과 암호해독에 대한 우려가 심각해진 최근 몇 년을 제외하면 MD5 는 가장 널리 사용되던 안전한 해시 함수이었다. (2005년 깨졌으나, 사용은 되고 있음) ③ MD4 와 MD5 의 비교 - MD4 는 16단계의 3라운드를 사용하나 MD5 는 16단계의 4..

내부 및 외부 단편화 (Internal/External Fragmentation)

내부 단편화 (Internal Fragmentation) 내부 단편화란 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남게 되는 현상을 말한다. 위와 같이 100MB의 메모리에 80MB 크기의 프로세스를 올리게 되면, 20MB의 내부 단편화가 발생하게 된다. 즉, 적은 크기의 잔여 메모리가 발생해 해당 메모리를 사용할 수 없게 된다. 외부 단편화 (External Fragmentation) 외부 단편화란 남아있는 총 메모리 공간이 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적(contiguous)이지 않아 발생하는 현상이다. 위와 같이 남아있는 메모리 공간은 50MB+50MB =100MB로 요청한 메모리 공간 80MB보다 크지만, 남아있는 공간..

OS가 하는 일 및 컴퓨터 구조

OS가 하는일 OS는 응용프로그램간 하드웨어 사용을 조정하고 데이터를 관리한다. 사용자 관점 사용자가 어떻게 사용하느냐에 따라 달라진다. 예를 들어 데스크탑 같은 범용 컴퓨터는 주로 사용의 용이성에 집중하고, 스마트폰 같은 경우는 배터리와 낮은 퍼포먼스 때문에 연산을 적게하고 들고다니며 사용하기 쉽게하기 위해 인터페이스를 간소화한다. 시스템 관점 자원을 어떻게 해야 효율적으로 관리할 지를 결정하는 역할을 한다. Computer System Operation 현대의 컴퓨터 구조는 CPU, 메모리, 디스크, USB, 그래픽 어댑터로 구성된다. 컴퓨터가 구동을 하기 위해선 하드웨어를 초기화 하고 OS를 메모리에 적재할 프로그램에 가지고 있어야하는데 이를 bootstrap program이라 부른다. bootst..

Overflow (오버플로우)

오버플로우(overflow)의 의미 - 각 데이터타입은 자료형에 맞는 저장의 최대/최소 범위가 존재한다. int number; 라고 선언하자. number는 변수의 이름이며 그 앞에 있는 int는 변수의 타입이다. int형 자료형은 4바이트의 정수형 타입으로 음수를 고려하고 있기 때문에 number가 저장할 수 있는 최대값은 2의31승-1이고, 이 값은 곧 2147483647 이다. (약 21억) 따라서 number 변수에는 약 21억까지 저장이 가능하다. 그런데 만일 코드에서 number 변수에 저 최대 숫자 이상을 넣는다면 어떻게 될까? 이와 같이 저장할 수 있는 최대범위를 넘어설때 이를 "오버플로우(overflow)" 라고 부른다. 오버플로우(overflow)의 법칙 - number의 최대저장가능값..

프로세서, 메모리, 캐시 개념 및 원리 (메모리 및 버스/연결 관한)

시스템 버스 시스템 버스는 하드웨어를 물리적으로 연결하여 서로 데이터를 주고받을 수 있게하는 통로 역할을 한다. 이때 버스는 데이터 버스, 주소 버스, 제어 버스로 나뉜다. 데이터 버스 프로세서와 메인 메모리 그리고 주변 장치들 사이에서 데이터를 전송할 때 쓰인다. 이때 버스는 데이터를 주고받아야 하므로 양방향이다. 주소 버스 프로세서에서 메모리의 주소를 지정할 때, 그 주소가 어디인지에 대한 정보를 보내는 버스이다. 즉, 프로세서에서 01110011이라는 위치에 데이터를 보내려면 데이터 뿐만 아니라 데이터의 목적지인 01110011도 버스를 통해 보내는데 이를 주소 버스를 통해 보낸다. 결국 프로세서가 주소를 지정하면서 보내는 버스이다. 이 버스는 주소를 보내면 되니 단방향이다. 제어 버스 프로세서가 ..

BSP(Binary Space Partitioning)알고리즘을 응용해 로그라이크류 게임 방만들기

이진 공간 분할법(Binary Space Partitioning, BSP) 은 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다. doom은 3차원처럼 보이지만 실제로는 2차원이고 그 2차원을 나타내기 위해 사용됐다. BSP알고리즘을 통한 로그라이크류 방만들기 0: 빈 공간 1 : 방, 3: 가로분할 길, 4: 세로분할 길 로그라이크 게임을 하다보면 일정한 맵을 돌려쓰는 게임도 있긴하지만 매번 새로운 맵을 생성하는 게임들이 존재한다. 매번 새로 맵을 생성할때 BSP알고리즘을 응용하여 새로 맵을 만들수 있다. 위에서 설명한 BSP알고리즘에서 둔각을 찾아 반복하여 나누는 방법이 아니라 2차원상에서 직사각형 모양으로만 방을 나눠..

프로젝트의 총 코드 라인 수를 확인하는 방법 (SourceMonitor)

우선 SourceMonitor을 다운로드 한다. 맨 하단 굴림으로 되어있는게 최신 버전이다. 다운로드가 다 끝났다면 File > New Project를 클릭한 후 프로젝트에 맞는 언어를 설정한다. 그 다음 프로젝트 파일 명칭이랑 경로를 설정한다. 여기서 All Subdirectories를 선택한다 즉 하위 폴더까지 다 추가한다는 뜻. 3개 다 체크한다 공백 문자, 중복된 헤더파일 등을 미포함 시킨다. New SourceMonitor project format을 선택한 후 Use this format when saving all projects를 체크한다. 한글이 있을 수도 있으니 UTF-8 파싱을 허용한다. 결과는 아래와 같다. Baseline 우클릭 또는 Views 탭 통해서 띄울 수가 있다.

시간 복잡도에 따른 알고리즘 목록

O(1) 배열 인덱스 접근 (예, arr[5];) 배열에 저장되있는 트리의 부모 또는 왼/오른쪽 자식 노드 검색 단일 연결 리스트에 노드를 삽입 이중 연결 리스트의 다음 또는 이전 요소에 접근 스택 푸시 팝 큐 삽입 삭제 해싱 (Hash Table) O(log n) 이중 탐색 이진 트리에서 최소 또는 최대값 검색 분할 정복 알고리즘 중 일차적인것들만 피보나치 수열 계산 O(n) 배열 순회 연결 리스트 순회 이진 검색 정렬이 되어있지 않은 연결 리스트 요소 제거 두 문자열간 비교 회문인지 검사 계수/버킷 정렬 O(n log n) 병합 정렬 힙 정렬 퀵 정렬 분할 정복 알고리즘 중 O(n^2)로 구현되있는것들 O(n^2) 버블 정렬 삽입 정렬 선택 정렬 단순한 2차원 배열 순회 O(n!) 브루트포스 탐색 방..

CPU의 역사

최초의 16비트 CPU: 인텔 8086 / 8088(1978년) 1971년에 출시된 인텔의 '4004'가 원조다. 하지만 이는 전자계산기와 같은 특정 목적 단말기용으로 주로 쓰였으며, 오늘날 우리가 쓰는 PC(퍼스널컴퓨터)용 CPU의 원조는 1978년에 나온 인텔의 16비트 CPU인 8086, 그리고 그 자매품인 8088이라 할 수 있다. 이 때문에 지금도 PC용 CPU는 ‘x86 계열’이라 부른다. 최초의 32비트 CPU: 인텔 80386(1986년) 1980년대에 들어 PC의 이용 범위가 급격히 넓어지면서 한층 고성능의 CPU가 요구되었다. 1986년에 출시된 인텔 80386은 32비트 명령어를 처리할 수 있는 최초의 x86계열 CPU로, 흔히 ‘386’이라는 이름으로 불리곤 했다. 80386이 큰 ..

유향 비순환 그래프 (DAG = Directed acyclic graph) 와 Khan 알고리즘을 이용한 위상 정렬 (Topological Sort)

DAG에 대한 토폴로지 정렬 알고리즘 위상 정렬이란 방향이 있는 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것이다. 싸이클이 없는(DAG, Directed Acyclic Graph) 그래프에선 가능하며 하나의 유향 그래프에서 여러 위상 정렬이 가능하다. 시간 복잡도 : O(V + E) / V (Vertex) : 노드, E (Edge) : 간선 => Best Case, Worst Case 동일. DFS와 관련된 다양한 유형의 에지의 출발 시간 사이의 관계이다. Tree edge (u, v): departure[u] > departure[v] Back edge (u, v): departure[u] < departure[v] Forward edge (u, v): dep..