개념 유닉스 및 유닉스 계열 운영 체제에서 파일 또는 파이프나 네트워크 소켓과 같은 기타 입출력 리소스에 대한 프로세스 고유 식별자이자 핸들이다. 일반적으로 음수가 아닌 정수 값이며, 음수는 에러를 나타내기 위해 예약되어있다. 추가 설명 전통적인 유닉스 구현에서 파일 디스크립터 (이하 fd) 는 커널에 의해 유지되는 프로세스별 fd 테이블에 색인되고, 이 테이블은 다시 모든 프로세스에서 열린 파일 테이블에 색인되고, 파일이 열린 모드(읽기, 쓰기, 등)가 기록된다. 이 테이블은 또 파일의 데이터의 속성(변경 시간, 권한 등)과 파일 위치가 적혀있는 inode 테이블에 색인된다. 입력 또는 출력을 수행하기 위해 프로세스는 시스템 콜을 통해 fd를 커널에 전달하고 커널은 프로세스를 대신하여 파일에 액세스한다..

switch문은 정수 인덱스 값에 따라 다중분기 기능을 제공한다. GCC는 case 값의 밀집도와 case의 수를 고려해서 switch문의 번역 방법을 선택한다. 장점 switch문을 사용하면 C 코드를 읽기 쉽게 해줄 뿐만 아니라 점프 테이블을 사용해서 효율적인 구현을 가능케 한다. 다단계의 if-else문을 사용하는 것보다 switch문을 실행하는 데 걸리는 시간이 case 수에 관계없다는 장점이 있다. 예제 (a)는 C로 구현한 간단한 switch문 예제 (b)는 (a)를 컴파일할 때 생성된 어셈블리 코드의 동작을 C로 나타낸 것 점프 테이블인 배열 jt는 7개의 원소를 가지고 있으며, 이들은 각 코드 블록의 주소다. jt의 비어있는 원소에는 default 블록 주소를 넣는다. 컴파일러는 먼저 인자..

설명 void echo() { char buf[8]; // 대충 buf에 사용자 입력 값 삽입하는 코드 } void caller() { echo(); } char buf[8] 선언 시 여러 상태정보와 함께 스택에 24바이트 할당한다. buf와 저장된 리턴 포인터 사이의 16바이트는 사용되지 않는다. echo()의 buf에 8문자(널 문자 포함)를 입력하면 buf에 할당된 공간에 알맞게 저장한다. 하지만 보다 긴 문자열을 입력하면 스택에 저장된 정보의 일부를 덮어쓰게 된다. 23개 까지는 심각한 결과가 발생하지 않지만, 이 이상부터는 리턴 포인터의 값과 저장 상태까지도 손상된다. 리턴 주소가 손상되면 ret instruction이 프로그램을 전혀 예상하지 못한 곳으로 점프하게 한다. 저장 공간을 오버플로우..

실수를 표현하는 방식으로 꽤 많은 종류의 형태가 제안되었지만, 현재까지 가장 많이 사용하는 방식은 IEEE 표준 754 부동 소수점 표현이다. 십진수 표기법 이진수 표기법 (비트) 이진수 표기법의 한계 0.2 같은 경우에는 이진수 표기법으로 정확하게 표기가 불가능하다. 매우 큰 수를 표현하기에 부적합하다 : 예를 들어 5 * 2^100은 101000000000…. (0이 100개 필요) IEEE 부동소수점 S는 숫자가 음수인지 양수인지 결정, 해당 비트는 MSB(Most Significant Bit) 처리 M은 분수 이진수 (가수부) E는 2의 거듭제곱인 가중치 단정밀도 (float) : 앞 8비트 = 지수, 뒤 23비트 = 분수 배정밀도 (double) : 앞 11비트 = 지수, 뒤 52비트 = 분수 ..

개념 해시 함수를 이용하여 키(key)를 index로 만들어 배열의 해당 index에 데이터를 보관하는 자료구조 보통 키(key)로 값(value)을 맵핑하는 식으로 사용한다. C++ STL의 unordered_map, unordered_set, 그리고 여러 언어들의 Dictionary나 HashMap, HashSet 등이 포함된다. 특징 - 배열의 각 요소는 키와 값 등으로 이루어진 구조체(및 클래스)로 이루어져 있다. - key를 index로 변환시키는 다양한 해시 함수가 존재하며, 이의 성능에 따라 더욱 성능이 좋아질 수 있다. - 특정 요소 삽입, 삭제, 탐색이 O(1)이며, 최악의 경우 O(N)이다. 장점 특정 요소를 탐색할 때 O(1)으로 굉장히 빠르다. 단점 1. 충돌 가능성을 줄이기 위해 ..

개념 각각의 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지고 있는 이진 트리 구조다. 데이터를 삽입할 때, 각각의 노드와 비교하며 삽입할 데이터가 노드의 데이터보다 작을 시 왼쪽 자식으로, 클 시 오른쪽 자식으로 내려가며 비어있는 곳까지 내려가 삽입된다. 특징 1. 트리에서 데이터를 검색할 때 이진 탐색 알고리즘과 동일한 시간 복잡도의 성능을 가진다. 2. 중위 순회로 데이터들을 정렬된 상태로 순회할 수 있다. 3. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다. 4. 요소의 삽입, 삭제, 접근은 O(logN), 최악의 경우 O(N) 이다. 장점 1. 특정 데이터를 검색할 때 꽤나 빠른 편이다. O(logN)..

개념 덱은 양방향 큐 (Double Ended Queue)의 줄임말이다. 이름 그대로 큐 구조가 양방향으로 되어있다. 즉, 데이터의 삽입, 삭제가 맨 앞과 맨 뒤에서 이루어지는 구조다. (큐는 먼저 추가한 데이터부터 삭제하는 구조, 선입 선출) 한글 발음으로 덱, 데크로 불린다. 특징 1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다. 2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다. 3. 요소의 삽입은 맨 앞, 맨 뒤에 삽입할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다. 요소의 삭제는 맨 앞, 맨 뒤를 삭제할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다...

개념 가변 배열이라고도 불리며, 크기가 고정되어 있지 않은 배열이다. 배열을 조금 더 쉽고 활용도 높게 사용하기 위한 자료구조다. C++ STL에서의 vector, Java에서의 ArrayList 등이 해당된다. 특징 1. 배열이기 때문에 메모리가 연속적이다. 2. 일반 배열과는 다르게 배열의 데이터가 용량보다 많아지는 순간 배열을 더욱 크게 재할당 한다. 3. 일반 배열과는 다르게 중간에 데이터 삽입이 가능하며 데이터 손실이 없다. 4. 일반 배열과는 다르게 중간의 데이터 삭제가 일어날 경우, 빈 공간 없이 한 칸씩 당겨진다. 5. 요소의 삽입은 맨 뒤에 삽입할 경우 O(1), 이외에는 O(N) 이며 요소의 삭제는 맨 뒤를 삭제할 경우 O(1), 이외에는 O(N) 이다. 특정 원소 접근은 O(1) 이다..