자료구조 개념 및 구현 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개씩 짝짓는 과정을 합이 증가하는 순서로 반복 > 허프만 코딩트리를 사용하여 각 문자를 가변 길이 코드로 변환 >..

# 소수 판별 - 소수: 1과 자신 이외의 수로는 나누어지지 않는 수 [코드] int prime(int n) { if (n < 2) return 0; // n이 2보다 작으면 1이므로 소수가 아님 for (int i = 2; i < n; i++) { // 2부터 n-1까지의 수를 탐색 if (n % i == 0) return 0; // i로 나누어서 1이 되는 경우가 있다면 소수 X } return 1; } * n이 2인 경우에는 i

# 팩토리얼 - 팩토리얼이란? > 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이 반환되면서 더 이상 함수..

# 소프트웨어와 자료구조 - 자료: 측정되거나 수집된 값의 모음 → 한 가지 데이터로 다양한 문제 해결 가능 - 정보: 수집된 데이터를 분석하여 새롭게 알아낸 사실 - 알고리즘: 주어진 문제 해결에 필요한 절차를 체계적으로 구성해 놓은 명령어 - 프로그래밍: 프로그램을 설계, 구현하는 작업 - 컴퓨터 과학: 컴퓨터 하드웨어만을 다루지 않으며 컴퓨터를 활용하여 주어진 문제를 해결하기 위한 소프트웨어 이론과 방법에 대해 연구하는 학문 > 목표: 주어진 문제를 해결하기 위한 절차인 알고리즘을 개발하는 것 - 자료구조: 프로그램을 통해 다량의 데이터를 효과적으로 저장, 관리, 처리하기 위해 사용되는 구조체 및 방법론 Linear Data structures Array, Stack, Queue Non-Linear..