자료구조 개념 및 구현 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..
자료구조 개념 및 구현 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..
# 재귀 호출의 개념 - 재귀 호출: 함수가 실행 중에 자기 자신을 다시 호출하는 상황 - 종료 조건을 가지는 동일한 task가 반복될 때 가능 // 종료 조건: 함수가 끝나야하기 때문에 필요 > 종결 조건은 재귀 호출에 반드시 포함되어야하며 잘못 설정할 경우 프로그램이 무한 반복에 빠질 수 있음 - 시스템 입장에서는 새로운 함수가 불리는 것과 같음 - 함수 실행 중 또 다른 함수가 실행되면 함수의 컨텍스트(context), 정보(지역변수, 복귀주소)를 활성 레코드(activation record)에 저장하여 보관하여야 함 - 활성 레코드는 함수의 환경 정보를 담고 있는 구조체이며 실행되는 함수마다 1개씩 생성되어 시스템 스택에서 저장 관리됨 - 시스템 스택은 함수 호출을 관리하기 위해 프로그램에서 사용..
자료구조 개념 및 구현 Chapter 2. C언어 기초 - 연습문제 Q1. 주어진 코드를 사용하여 다음 세부 기능을 구현하시오 (1) 배열의 각 원소의 주소와 저장된 값을 출력한다 (2) 각 원소의 자료형 별로 할당되는 바이트 크기를 출력한다 [코드] #include #define SIZE 20 void printArray(int *ptr,int size); int main() { int list[SIZE], i; for(i=0;i
자료구조 개념 및 구현 Chapter 1. 자료구조 개요 - 연습문제 Q1. 알고리즘이 성립되기 위한 조건은 무엇인가? - 명시적 입력은 없어도 된다 - 하나 이상의 출력이 있어야 한다 - 모호하지 않은 명령문으로 표현되어야 한다 - 유한한 수의 명령어 실행 이후에 종료되어야 한다 Q2. 알고리즘과 일반 프로그램과의 차이점은 무엇인가? - 프로그램은 개별적 기능을 지칭하고, 알고리즘은 그 프로그램을 처리하는 절차이다 Q3. 소프트웨어 개발 주기를 적고 블랙박스 시험과 화이트박스 시험을 각각 설명하시오 - 소프트웨어 개발 주기: 요구사항 → 분석 → 설계 → 검증 - black box: 입력 값으로부터 발생하는 출력 값을 보고 정확도를 판단 - white box: 프로그램 내부 루틴을 포함하여 오류를 검사..
# 팩토리얼 - 팩토리얼이란? > n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말 # 반복문으로 팩토리얼 구현하기 [코드] #include void factorial(int n); int main() { factorial(20); } void factorial(int n) { int i, j; int total; for (i = 2; i main 함수에서 GetFactorial(5)를 호출하면 매개 변수 n은 0이 아니므로 else 블록에서 n*GetFactorial(n-1)이 실행됨 > 또 다른 GetFactorial 함수가 실행되고 인자 4가 전달됨 > 이를 그림으로 정리하면 다음과 같음 > n이 0에 도달하면 if 블록이 실행되어 1이 반환되면서 더 이상 함수..