재민의 IT 공부기록

연결 리스트에서 삽입은 어느 위치에 노드를 삽입하느냐에 따라 다르다. [중간 노드 삽입] 1. 삽입할 노드를 준비한다 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 삽입할 위치 앞 노드의 링크값이 된다. 4. 삽입할 위치 앞 노드에 새 노드를 연결한다. [첫번째 노드 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 head가 가리키고 있는 노드의 주소값이 된다. 4. head에 새 노드를 연결한다. [마지막 노드로 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드가 마지막 노드이므로 링크값으로 NULL을 지정한다. 4...

연결리스트에서 탐색은 다음과 같은 과정으로 이루어진다. 1. 헤드에서 시작 : 검색을 시작하기 위해 연결리스트의 헤드부터 탐색을 시작한다. 2. 노드 순회: 각 노드를 순차적으로 방문하면서 원하는 값을 찾을 때까지 계속 진행한다. 3. 비교 연산: 각 노드에서 찾고자 하는 값을 현재 노드의 데이터와 비교한다. 값을 찾을 경우 검색을 종료하고 노드의 위치를 반환하지만, 찾지 못할 경우에는 검색이 실패했다고 출력하게 된다. 다음은 자료구조 상에서 search 연산 예제이다. #include #include // 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* next; }; // 연결 리스트에서 값 검색하는 함수 struct Node* search(struc..

리스트는 자료를 구조화하는 가장 기본적인 방법으로서, 값들을 나열한다. 리스트에서는 새로운 항목을 리스트의 처음, 중간,끝에 삽입하여 저장할 수 있다. 그리고 리스트의 특정 부분을 추출하거나 특정 값을 삽입 혹은 삭제할 수 있다. 리스트는 구현이 간단하지만 삽입 삭제시 오버헤드가 발생할 가능성이 있는 Linear List와, 삽입 삭제가 효율적이지만 구현이 복잡한 Linked List로 나뉜다. Linked List에서 한 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시켜야만 한다. 삽입을 위해서는 먼저 원소를 삽입할 빈 자리를 만들어서, 빈 자리에 원소를 삽입한다. (빈 자리를 만들기 위해 기존의 원소들은 한칸씩 뒤로 이동시킨다) 즉 n+1개의 ..

하노이탑의 제약조건은 다음과 같다. - 한 번에 하나의 원판만 이동 가능 - 맨 위에 있는 원판만 이동 가능 - 크기가 작은 원판 위에 큰 원판을 쌓을 수 없음 원반 N개를 A에서 C로 이동시키려면, 우선 작은 원반 1개를 A에서 B로 이동시키는 과정이 선행되어야 한다(그래야 마지막 원반을 C에 놓고 다음 프로세스 진행 가능) 그 다음 큰 원반을 A에서 C로 이동시키고, 작은 원반 n-1개를 B에서 C로 이동시킨다. c로 구현시 핵심 코드는 다음과 같다 if (n == 1) printf("Disk1: %c > %c\n, from, to) else{ hanoi(n-1,from,to,tmp); print("Disk%d: %c > %c \n, from, to); hanoi(n-1,tmp,from,to); }

재귀함수(Recursion)은 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법을 의미한다. Ex) 팩토리얼 재귀함수는 스택에 저장하고(push) 빼내는(pop) 형식을 생각하면 이해하기 편한데, 이를 c 코드로 정리하면 다으모가 같다. void Rec(0){ if (n

[알고리즘 소개] 1) 이진탐색 알고리즘에서는 배열 인덱스의 시작과 끝을 각각 0과 마지막 값으로 둔다. 그리고 0과 마지막 값을 더한 값을 2로 나눈 결과값을 인덱스값으로 하여, 인덱스 값이 target값보다 큰지 작은지를 판단한다. 2) 1의 결과를 토대로 target값보다 크다면 오른쪽을, target값보다 작다면 왼쪽 절반을 취한다. 이를 반복한다. 3) 순차 탐색하는 것 보다 좋은 성능임을 확인한다.(순차 탐색보다 탐색량이 줄음) [구현] int Bsearch(int arr[],int len, int target) { int first = 0; int last = len - 1; int mid; while(first

우선순위 스케줄링이란 : 프로세스에 우선순위를 부여하는 스케줄링으로서, 프로세스는 대개 우선순위가 높을 수록 작은 우선순위 번호를 가진다. 그러면 CPU는 가장 높은 우선순위를 가진 프로세스에 CPU를 할당하는 구조이다. 우선순위의 정의는 내/외부적 요인이 작용한다. 내부적 요인으로는 시간 제한, 메모리 요구, open file 수, I/O와 CPU의 비율 등이 작용할 것이고, 외부족 요소로는 프로세스의 중요성, 비용의 유형과 액수, 그리고 정치적 요인이 작용할 것이다.

운영체제 상에서 가상메모리는 물리적 메모리에 backing store가 합쳐진 공간을 의미한다. 가상 메모리에서는 프로그램의 논리 메모리와 물리적 메모리를 분리하는데, 프로세스가 완전히 메모리에 적재되지 않아도 프로세스 실행을 허용한다. 가상 메모리에서는 물리적 메모리보다 크기가 큰 가상 메모리를 제공할 수 있는데, 프로그램의 크기가 물리적 메모리보다 클 수 있다. 또한 가상 메모리는 페이지 단위의 swap in/out을 진행하는데, 이를 통해 입출력 크기를 감소시킬 수 있다. 가상 메모리의 구현에는 요구 페이징과 요구 세그먼테이션을 이용한다. 가상메모리는 프로세스들이 메모리와 파일 공유를 가능하게 하는데, 이 과정은 공유 라이브러리와 공유 메모리를 통해 이루어진다.

파일에 대한 디스크 공간 할당 방법의 고려 사항으로는, 디스크 공간의 효율적인 이용 및 파일의 빠른 접근을 위해야 한다는 것이다. 이를 위해 3가지 주요 할당 방법을 사용한다 1) 연속 할당(contiguous allocation) 각 파일은 디스크의 연속된 블록들의 집합을 점유하는 방법이다. 최소 탐색시간과 간단하다는 점, 파일 접근이 쉽다는 점은 장점으로 작용하지만, 외부 단편화로 인한 저장공간이 낭비된다는 점, 그리고 파일 크기를 증가시킬 수 없다는 점은 분명한 단점이다. 2) 연결 할당(linked allocation) 각 파일은 디스크 블록들의 linked list로 구성되어, 블록 들이 디스크의 임의의 위치에 분산 가능하도록 하는 방법이다. 공간 낭비가 없다는 점은 장점이지만, 랜덤 접근이 불..

디스크 스케줄링은 디스크의 I/O 요청 처리 순서를 적절한 순서로 스케줄링하여 접근시간 및 대역폭을 향상시키는 방법이다. 디스크 스케줄링의 방법으로는 FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK 스케줄링이 있ㄸ. 1) FCFS : 선입선처리 스케줄링 FIFO 큐를 사용하여 요청한 순서대로 처리하는 방법이다. 빠른 서비스를 제공하지 못하며, 부하가 많은 경우 특히 비효율적이다. 2) SSTF: 최소 탐색 우선 스케줄링이다. (Shortest-Seek-Time-First Scheduling) 현재 헤드 위치에서 탐색시간이 최소인 위치의 요청을 먼저 선택하는 방법이다. FCFS방법보다 효율적이지만, 일부 요청의 기아 상태가 발생할 수 있다. 3) SCAN : 엘레베이터 알고리즘 디스크..