# 유클리드 호제법 - 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나 - 호제법이란? > 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 나타냄 - 내용 > 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 함 (이때 a>b) > a와 b의 최대공약수는 b와 r의 최대 공약수와 같음 > 위의 성질에 의해 b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복함 > 위의 과정에서 나머지가 0이 될 때 나누는 수가 a와 b의 최대 공약수가 되는 것 # 최대 공약수 (greatest common divisor) gcd(x,y) = gcd(s,x%y) if y>0 gcd(x,0) = x - 최대 공약수를 구하는 알고리즘 > y가 0이면 x를 ..

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

# Polynomial A(x) = 3x^20 + 2x^5 + 4 - a sum of terms(항), ax^e (x: variable, a: coeffiecient(계수), e: exponent(지수)) ​ ​ # Operations of Polynomial ADT - Zero(): 다항식을 0으로 만듦 ::= return 다항식, p(x) = 0 - IsZero(poly): 다항식이 0인지 검사 ::= if(poly) return FALSE else return True - Coef(poly, expon): 다항식에서 지수가 expon인 계수를 반환 - Lead_Exp(poly): 다항식에서 가장 큰 차수(지수의 값)를 반환 - Attach(poly, coef, expon): 계수가 coef이고 지수..

자료구조 개념 및 구현 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

# 볼링 게임 점수 계산 - 볼링 게임은 총 10프레임으로 구성되고 매 프레임에 최대 2번까지 볼을 던질 수 있다. 첫 번째 던진 공이 10개 핀을 모두 쓰러뜨리면 '스트라이크(strike)'라고 부르고, 공을 2번 던져서 10개 핀을 모두 쓰러뜨리면 '스페어(spare)'라고 한다. [점수 계산 규칙] 1. 스트라이크(strike)를 친 경우는 이후 2회 공을 던져서 넘어진 핀의 수를 더해서 점수를 계산한다 2. 스페어(spare)를 친 경우는 이후 1회 공을 던져 넘어진 핀의 수를 더해서 점수를 계산한다 3. 1번과 2번에 해당되지 않는 경우는 해당 프레임에 넘어진 핀의 수를 더해서 점수를 계산한다 4. 마지막 10프레임에 스트라이크를 친 경우에는 2회의 보너스 드로우를, 스페어를 친 경우에는 1회의..

# 배열 - 자료형이 동일한 원소(element)들의 유한 집합 - 연속적인 메모리상에서 표현되며 각 원소의 값은 고유의 인덱스(index)를 사용하여 접근 - 선형의 1차원 배열, 표 형식의 2차원 배열, 6면체 형태의 3차원 배열이 있음 - 2차원 이상의 배열은 다차원 배열(multi-dimensional array)라고 부름 - 배열의 인덱스는 0부터 1씩 증가하며, 2차원 배열은 (행, 열) 순서쌍으로 인덱스를 표현 - 배열은 선언된 이후에 배열의 크기(원소의 수)를 변경할 수 없기 때문에 필요한 원소의 수를 잘 예측해야 공간 부족 또는 메모리 낭비를 예방할 수 있음 > 1차원 배열: 8개의 원소로 구성되는 배열 > 2차원 배열: 8행 5열로 구성되는 배열 > 3차원 배열: 6행 6열이며 폭의 길..

# 포인터 - 포인터: 메모리 주소를 값으로 갖는 변수 - 간접 참조를 통하여 원본 데이터를 복사하거나 공유할 수 있음 - 메모리 주소를 직접 다루기 때문에 잘못 사용할 경우 예기치 못한 상황으로 시스템이 다운되거나 문제가 발생할 수 있음 - 함수 간의 매개 변수 참조 전달(call by reference), 연결 리스트에서 동적 메모리 관리(dynamic memory management) 등에 사용됨 - *(asterisk)와 &(ampersand) 연산자 > *은 사용되는 위치에 따라 의미가 달라지며 포인터형 변수에만 적용 가능 → 아래 소스코드 (1), (2), (3), (4) 참고 > &는 모든 변수에 붙일 수 있는 주소 연산자 [코드] #include void main() { int i = 3,..

# 구조체 - 구조체는 자료형이 상이한 복수의 멤버들을 하나의 자료로 묶어 처리할 수 있는 복합 자료형 - 선언 위치: 전처리기와 main 사이 - 예약어: struct - 예시: 나이(age), 학년(grade), 전공(major) 세 개의 멤버를 갖는 학생(student) 구조체를 정의 // 구조체의 선언 1. 구조체의 이름을 줄 수 있음 struct student { int age; int grade; char major[20] }kim, lee; // 구조체의 선언 2. 구조체 이름을 생략하고 구조체 변수를 생성 struct { int age; int grade; char major[20]; }kim, lee; // 구조체의 선언 3. 구조체 변수명이 생략되어 선언된 경우 --> struct 키워..

자료구조 개념 및 구현 Chapter 1. 자료구조 개요 - 연습문제 Q1. 알고리즘이 성립되기 위한 조건은 무엇인가? - 명시적 입력은 없어도 된다 - 하나 이상의 출력이 있어야 한다 - 모호하지 않은 명령문으로 표현되어야 한다 - 유한한 수의 명령어 실행 이후에 종료되어야 한다 Q2. 알고리즘과 일반 프로그램과의 차이점은 무엇인가? - 프로그램은 개별적 기능을 지칭하고, 알고리즘은 그 프로그램을 처리하는 절차이다 Q3. 소프트웨어 개발 주기를 적고 블랙박스 시험과 화이트박스 시험을 각각 설명하시오 - 소프트웨어 개발 주기: 요구사항 → 분석 → 설계 → 검증 - black box: 입력 값으로부터 발생하는 출력 값을 보고 정확도를 판단 - white box: 프로그램 내부 루틴을 포함하여 오류를 검사..

# Huffman Coding Tree - 데이터 문자의 출현 빈도에 따라 가변 길이의 부호를 사용하는 압축 알고리즘 > 출현 빈도가 높은 문자가 짧은 부호로 변환됨으로써 전체 문장의 데이터 비트 수는 줄어들게 됨 - 장점: 공간의 효율성을 높일 수 있음 - 단점: 문장을 구성하는 문자의 빈도 횟수가 비슷하다면 크게 효율적이지 못함 - 문장 예시: "time and tide wait for no man" ① 각 문자의 출현 빈도를 출현 빈도 테이블로 나타냄 ② 각 문자를 출현 빈도에 따라 정렬함 ③ 각 문자와 출현 빈도를 계층적 자료구조 트리의 단말노드로 지정한 후 출현 빈도가 낮은 것부터 2개씩 짝짓는 과정을 합이 증가하는 순서로 반복 > 허프만 코딩트리를 사용하여 각 문자를 가변 길이 코드로 변환 >..