Chapter 08. 프로세스 리눅스 프로그래밍 원리와 실제 - 창병모 교수님 8.1 쉘과 프로세스 1) 쉘 - 쉘(Shell) 사용자와 운영체제 사이에 창구 역할을 하는 소프트웨어 사용자로부터 명령어를 입력받아 이를 처리하는 명령어 처리기(Command Processor) 역할 수행 * 프로세스: 실행 중인 프로그램 - 쉘의 실행 절차 쉘은 시작하면 실행 파일을 읽어 실행 시작 파일은 환경 변수와 같은 사용자의 사용 환경을 초기화하는데 주로 사용 bash의 경우 시스템 차원의 시작 파일로 /etc/profile과 /etc/bashrc를 사용하고 사용자 차원의 시작 파일로 ~/.bash_profile과 ~/.bashrc를 사용함 쉘은 시작 파일을 실행한 후에 프롬프트를 출력하고 사용자의 명령을 기다림 사..

↓Chapter 04. 변수 및 유효 범위 프로그래밍 언어론 원리와 실제 - 창병모 교수님 4.1 변수 선언 1) 변수 선언과 유효 범위 - 사용 전 선언(declaration before use): 변수는 사용하기 전에 선언되어야 함 - 변수의 유효 범위(scope) 선언된 변수가 유효한(사용될 수 있는) 프로그램 내의 범위/영역 변수 이름뿐 아니라 함수 등 다른 이름도 생각해야 함 - 정적 유효 범위(Static scope) 선언된 이름은 선언된 블록 내에서만 유효함 대부분 언어에서 표준 규칙으로 사용됨 2) 블록과 변수 선언 - 구문법 → ... | id = ; | let in end → { id [=];} → {} → int | bool | string - 의미 변수 id는 타입 변수이며 초기화가..

자료구조 개념 및 구현 Chapter 5. 선형 자료구조 - 연습문제 Q1. 아래와 같이 선언된 배열 A가 메모리 상에 행 우선과 열 우선 순서로 각각 저장된다고 가정할 때 배열 원소 A[2][3][4]의 주소를 계산하시오 (단, &A[0][0][0] = 1000이고, sizeof(int) = 4 이다) int A[9][7][8] ; (1) 행 우선 순서(row-major order)로 저장 시 - 1560 / 1000 + (2 * 7 * 8 + 3 * 8 + 4) * 4 (2) 열 우선 순서(column-mafor order)로 저장 시 - 1572 / 1000 + (2 * 7 * 8 + 3 + 4 * 7) * 4 Q2. 7x7 희소 행렬에서 0이 아닌 원소만을 3-순서쌍(row, column, val..

# 큐 - 큐: 처리를 기다리고 있는 작업(원소)들의 리스트 - 선입 선출(FIFO, First-In, First-Out) 방식 / FCFS (First-Come, First-Served) - 우선순위를 부여하지 않음 - 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고 큐의 맨 앞(front) 원소가 먼저 삭제됨 - insert된 순서대로 처리됨 - 스택과 달리 큐의 맨 앞 원소와 맨 뒤 원소를 가리키기 위한 두 개의 front와 rear 포인터가 필요 Q = [a0, a1, ..., an-1] # 큐의 구현 - front: delete할 때 사용 - rear: stack에서의 top과 같은 역할을하며 add할 때 사용 - front와 rear 포인터의 초기 값 = -1 ← 일반적으로 이렇게 설정 - 새..

# Matrix (m rows * n cols) - 2차원 배열: matrix[m][n] - Space complixity = S(m,n) = m*n → 얼마만큼의 기억장소를 필요로하는지 나타내는 척도 * 배열이 int 형일 때, S(m,n) = m*n*4 ex) 4 : 배열 안의 원소를 entry라고 하며 배열을 사용해 나타낼 때는 matrix[0][2]와 같이 나타냄 # Sparse Matrix - 희소 행렬: 행렬의 값이 대부분 0인 행렬 → 저장 공간은 큰데 의미있는 값은 적음 - A[m,n]: 대부분의 값이 0이며 이 행렬을 효과적으로 저장하는 방법을 찾아야함 → 중요한 목표 # Sparse Matrix solution - 0이 아닌 element만 저장한다 - 3튜플을 가지는 배열을 활용한다 ..

자료구조 개념 및 구현 Chapter 4. 알고리즘 분석 - 연습문제 Q1. 점근적 표기법(asymptotic notation)을 사용하는 이유를 적으시오. - 알고리즘의 성능을 비교하기 위해 사용함. 입력의 수가 매우 커질 때, 알고리즘의 복잡도가 증가하는 패턴을 살펴봄 Q2. 시간 복잡도와 공간 복잡도는 각각 무엇을 의미하는가? - 시간 복잡도: 프로그램이 수행을 완료하는데 걸리는 시간 - 공간 복잡도: 알고리즘 실행에 필요한 메모리 Q3. 시간 복잡도에 대한 점근적 표기법의 세 가지 종류를 각각 설명하시오 - 상한선(Big-Oh) 표기법: 시간 복잡도 함수 f(n) = Ο(g(n))이라고 표기할 수 있다면, 이 알고리즘의 수행 시간은 상한선 c·g(n)을 넘지 않는다는 의미 - 하한선(Big-Ome..

자료구조 개념 및 구현 Chapter 3. 재귀 호출 - 연습문제 Q1. 반복문(iteration)과 비교한 재귀문(recursion)의 장단점은 무엇인가? - 장점: 알고리즘을 명료하게 표현 가능 - 단점: 빈번한 함수 호출로 인한 스택 오버플로우 현상 발생 Q2. n개의 정렬된 정수에 대하여 반복문과 재귀 호출 함수를 각각 사용하여 이진 탐색하는 프로그램을 작성하시오. 재귀 호출 함수가 몇 번 호출되는지 변수를 추가하여 확인하시오. [코드] #include #include int binary_search(int list[], int item, int left, int right); int rbinsearch(int list[], int searchkey, int left, int right); int..

# 순열 - 어떤 원소 n개를 나열할 때 순서가 다르면 다른 순열로 간주함 (1) 집합 {'a', 'b', 'c'}에 대하여 찾을 수 있는 모든 순열 > P = {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)} > 3P3 = 3 * 2 * 1 = 3! = 6 (2) 집합 {'a', 'b', 'c', 'd'}의 순열 > 4! = 24 > 24개의 순열은 4개의 그룹으로 나뉘어질 수 있음 a) (a, Perm(b, c, d)) b) (b, Perm(a, c, d)) c) (c, Perm(a, b, d)) d) (d, Perm(a, b, c)) > 하나의 원소를 고정하고 그 뒤에 원소의 수만 다른 순열을 나타내는 함수를 호출함 > ex) P..

# 하노이 타워 (1) - 세 개의 기둥과 크기가 다양한 원판들이 존재 > 초기 상태: 한 기둥에 모든 원판이 꽂혀 있음 - 목표: 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥에 옮기는 것 - 조건 ① 한 번에 하나의 원판만 옮길 수 있다 ② 큰 원판이 작은 원판 위에 놓일 수 없다 - 알고리즘 더보기 세 개의 기둥 A, B, C가 있고 기둥 A에서 B로 n개의 원판을 옮긴다고 가정 1. 기둥 A에서 n-1개의 원판을 A, B가 아닌 기둥 C로 옮긴다 2. 기둥 A에 남은 1개의 원판을 B로 옮긴다 3. 기둥 C에 있는 n-1개를 기둥 B로 옮긴다 > 2번 과정: 1개의 원판이 이동하면 됨 > 1, 3번 과정: 원판의 수가 1개 줄어든 또 다른 하노이 타워 문제 → 재귀적인 방법으로 해결 가능 >..

# 재귀 호출의 개념 - 재귀 호출: 함수가 실행 중에 자기 자신을 다시 호출하는 상황 - 종료 조건을 가지는 동일한 task가 반복될 때 가능 // 종료 조건: 함수가 끝나야하기 때문에 필요 > 종결 조건은 재귀 호출에 반드시 포함되어야하며 잘못 설정할 경우 프로그램이 무한 반복에 빠질 수 있음 - 시스템 입장에서는 새로운 함수가 불리는 것과 같음 - 함수 실행 중 또 다른 함수가 실행되면 함수의 컨텍스트(context), 정보(지역변수, 복귀주소)를 활성 레코드(activation record)에 저장하여 보관하여야 함 - 활성 레코드는 함수의 환경 정보를 담고 있는 구조체이며 실행되는 함수마다 1개씩 생성되어 시스템 스택에서 저장 관리됨 - 시스템 스택은 함수 호출을 관리하기 위해 프로그램에서 사용..