공부할 책 : 자료구조와 함께 배우는 알고리즘 입문 - C언어 편
내년 2학년때 자료구조랑 알고리즘 배운다! 예습해둬야지 히히
알고리즘
문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합
최댓값
Q1. 네 값의 최댓값을 구하는 함수 max4를 작성하세요.
#include <stdio.h>
int max4(int a, int b, int c, int d)
{
int max = a;
if (b > max) max = b;
if (c > max) max = c;
if (d > max) max = d;
return max;
}
int main(void)
{
int a, b, c, d;
scanf_s("%d %d %d %d", &a,&b,&c,&d);
printf("최댓값은 %d입니다.\n", max4(a, b, c, d));
}Q2. 세 값의 최솟값을 구하는 min3 함수를 작성하세요.
#include <stdio.h>
int min3(int a, int b, int c)
{
int min = a;
if (min > b) min = b;
if (min > c) min = c;
return min;
}
int main(void)
{
int a, b, c;
scanf_s("%d %d %d", &a,&b,&c);
printf("최솟값은 %d입니다.\n", min3(a, b, c));
}Q3. 네 값의 최솟값을 구하는 min4 함수를 작성하세요.
쉬우니 생략
중앙값
Q4. 세 값의 대소 관계 13종류의 모든 조합에 대해 중앙값을 구하여 출력하는 프로그램 작성
#include <stdio.h>
int min3(int a, int b, int c)
{
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (a < c)
return c;
else
return b;
}
int main(void)
{
printf("min3(%d, %d, %d) = %d\n", 3, 2, 1, min3(3, 2, 1)); /* [A] a > b > c */
printf("min3(%d, %d, %d) = %d\n", 3, 2, 2, min3(3, 2, 2)); /* [B] a > b = c */
printf("min3(%d, %d, %d) = %d\n", 3, 1, 2, min3(3, 1, 2)); /* [C] a > c > b */
printf("min3(%d, %d, %d) = %d\n", 3, 2, 3, min3(3, 2, 3)); /* [D] a = c > b */
printf("min3(%d, %d, %d) = %d\n", 2, 1, 3, min3(2, 1, 3)); /* [E] c > a > b */
printf("min3(%d, %d, %d) = %d\n", 3, 3, 2, min3(3, 3, 2)); /* [F] a = b > c */
printf("min3(%d, %d, %d) = %d\n", 3, 3, 3, min3(3, 3, 3)); /* [G] a = b = c */
printf("min3(%d, %d, %d) = %d\n", 2, 2, 3, min3(2, 2, 3)); /* [H] c > a = b */
printf("min3(%d, %d, %d) = %d\n", 2, 3, 1, min3(2, 3, 1)); /* [I] b > a > c */
printf("min3(%d, %d, %d) = %d\n", 2, 3, 2, min3(2, 3, 2)); /* [J] b > a = c */
printf("min3(%d, %d, %d) = %d\n", 1, 3, 2, min3(1, 3, 2)); /* [K] b > c > a */
printf("min3(%d, %d, %d) = %d\n", 2, 3, 3, min3(2, 3, 3)); /* [L] b = c > a */
printf("min3(%d, %d, %d) = %d\n", 1, 2, 3, min3(1, 2, 3)); /* [M] c > b > a */
return 0;
}Q5. 중앙값을 구하는 함수는 다음과 같이 작성할 수 있다. 그러나 med3함수에 비해 효율이 떨어지는데 그 이유를 설명하시오.
int med3 (int a, int b, int c)
{
if ((b >= a && c <= a) || (b <=a && c>= a))
return a;
else if ((a > b && c < b) || (a < b && c > b))
return b;
return c;
}내 답안 : 모르겠음..
모범답안 : 첫 번째 if가 성립하지 않는 경우 두 번째 if 에서도 같은 판단을 하므로 효율적이지 않다.
반복문
Q6 생략
Q7. n이 7이면 '1+2+3+4+5+6+7 = 28' 로 출력하는 프로그램 작성
#include <stdio.h>
int main(void)
{
int num1, sum = 0;
scanf_s("%d", &num1);
for (int i = 1;i <= num1;i++) {
sum += i;
printf("%d ",i);
if (i != num1) {
printf("+ ");
}
}
printf("= %d", sum);
}Q8. 가우스의 덧셈이라는 방법으로 1부터 n까지 정수합 구하는 프로그램 작성
#include <stdio.h>
int main(void)
{
int num1;
scanf_s("%d", &num1);
printf("%d", (1 + num1) * 5);
}Q9. 정수 a,b 포함하여 그 사이 모든 정수의 합 구하는 함수 작성
쉬워서 생략
Q10. 정수 a,b를 입력하고 b-a를 출력하는 프로그램 (조건 : a<b , do while 사용)
#include <stdio.h>
int main(void)
{
int a, b;
scanf_s("%d", &a);
do{
scanf_s("%d", &b);
if (a > b) {
printf("a보다 큰 값을 입력하세요!");
}
} while (a > b);
printf("%d", b - a);
}Q11. 양의 정수 입력후 자릿수 출력하는 프로그램
#include <stdio.h>
int main(void)
{
int a,b=0;
scanf_s("%d", &a);
while (a > 0) {
a = a / 10;
b++;
}
printf("그 수는 %d자리 입니다.", b);
}구조적 프로그래밍
하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법을 구조적 프로그래밍이라 한다. 구조적 프로그래밍은 순차, 선택, 반복이라는 3종류의 제어 흐름을 사용한다.
Q12~Q16 쉬워서 생략
Q17. n단의 피라미드 출력
#include <stdio.h>
void spira(int n) {
for (int i = 0;i < n;i++) {
for (int j = n - i;j > 0;j--) {
printf(" ");
}
for (int k = 0;k < (i + 1) * 2 - 1;k++) {
printf("*");
}
printf("\n");
}
}
int main(void)
{
int a;
scanf_s("%d", &a);
spira(a);
}Q18. n단의 숫자 역피라미드
#include <stdio.h>
void spira(int n) {
for (int i = 0;i < n;i++) {
for (int j = 1;j <= i;j++) {
printf(" ");
}
for (int k = 1+i*2;k <= n * 2 - 1;k++) {
printf("%d", i+1);
}
printf("\n");
}
}
int main(void)
{
int a;
scanf_s("%d", &a);
spira(a);
}자료구조
데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
배열
같은 자료형의 변수로 이루어진 요소가 모여 직선 모양으로 줄지어 있는 자료구조
배열 요소의 자료형은 int형이나 double형 등 상관 없음
그러나 배열 선언 시 요소 개수는 상수만 사용 가능. int a[n] 처럼 사용 불가
그런데 마치 변수를 사용해 배열을 선언한 것처럼 할 수 있다.
메모리 할당
형식 :
void *calloc(size_t nmemb, size_t size);
void *malloc(size_t size);calloc 함수 : 크기가 size인 자료가 nmemb개만큼 들어갈 메모리를 할당한다. 할당한 메모리 영역은 모든 비트가 0으로 초기화된다.
malloc 함수 : 크기가 size인 메모리를 할당한다. 할당한 메모리의 값은 정의되지 않는다.
C언어의 메모리 구조
데이터(Data) 영역 - 전역 변수와 정적 변수가 할당되는 영역
스택(Stack) 영역 - 함수 호출 시 생성되는 지역 변수와 매개변수가 저장되는 영역
힙(Heap) 영역 - 필요에 따라 동적으로 메모리 할당. 프로그램 실행 중에 결정
여기서 calloc, malloc 함수는 힙(heap)이라는 특별한 빈 공간에 기억 장소를 확보한다. 이때 확보한 메모리가 불필요하면 그 공간을 해제해야 한다. 이를 위해 제공되는 함수가 free 함수이다.
형식 :
void free(void *ptr);실습 코드 1 :
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int * x;
x = calloc(1, sizeof(int)); /* int형 포인터에 메모리 할당 */
if (x == NULL) {
puts("메모리 할당에 실패했습니다.");
}
else {
*x = 57;
printf("*x = %d\n", *x);
free(x); /* int형 포인터에 할당한 메모리 해제 */
}
return 0;
}실습 코드 2 :
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i;
int *a; /* 배열의 첫 번째 요소의 포인터 */
int na; /* 배열 a의 요솟수 */
printf("요솟수 : ");
scanf("%d", &na);
a = calloc(na, sizeof(int)); /* 요소 개수가 na인 int형 배열을 생성 */
if (a == NULL)
puts("메모리 확보에 실패했습니다.");
else {
printf("%d개의 정수를 입력하세요.\n", na);
for (i = 0; i < na; i++) {
printf("a[%d] : ", i);
scanf("%d", &a[i]);
}
printf("각 요솟값은 아래와 같습니다.\n");
for (i = 0; i < na; i++)
printf("a[%d] = %d\n", i, a[i]);
free(a); /* 요소 개수가 na인 int형 배열을 해제 */
}
return 0;
}void 포인터 :
모든 자료형의 메모리 확보 또는 해제에 사용한다. 이때 특정 자료형의 포인터를 주고받을 때 자료형이 서로 맞지 않으면 문제가 발생하므로 void 포인터를 반환하거나 받는 데 사용한다. void 포인터는 모든 형의 객체를 가리킬 수 있다. void 포인터의 값을 모든 자료형의 포인터에 대입할 수 있고, 거꾸로 모든 자료형의 포인터 값을 void 포인터에 대입할 수 있다.
쉬운건 생략
Q1. 최솟값 구하는 프로그램 작성
/* 배열 요소의 최댓값을 구합니다(값을 입력합니다). */
#include <stdio.h>
#include <stdlib.h>
/*--- 요솟수가 n인 배열 a의 요소의 최댓값을 구합니다. ---*/
int minof(const int a[], int n) {
int min = a[0];
for (int i = 1;i < n;i++) {
if (min > a[i]) min = a[i];
}
return min;
}
int main(void)
{
int i;
int *height; /* 배열의 첫 번째 요소의 포인터 */
int number; /* 인원 = 배열 height의 요소 개수 */
printf("사람 수 : ");
scanf_s("%d", &number);
height = calloc(number, sizeof(int)); /* 요솟수가 number개인 배열을 생성 */
printf("%d 사람의 키를 입력하세요.\n", number);
for (i = 0; i < number; i++) {
printf("height[%d] : ", i);
scanf_s("%d", &height[i]);
}
printf("최댓값은 %d입니다.\n", minof(height, number));
free(height); /* 배열 height를 해제 */
return 0;
}Q3,Q4 비슷해서 생략
Q5. 역순 정렬
#define swap(type, x, y) do { type t = x; x = y; y = t;} while (0)
void ary_reverse(int a[], int n)
{
int i;
for (i = 0;i < n/2;i++) {
for (int j = 0;j < n;j++) {
printf("%d ", a[j]);
}
printf("\n");
swap(int, a[i], a[n - i - 1]);
printf("a[%d]와 a[%d]를 교환합니다.\n", i, n - i - 1);
}
printf("역순정렬 종료!\n");
}
int main() {
int i;
int* x;
int nx;
scanf_s("%d", &nx);
x = calloc(nx, sizeof(int));
printf("배열 입력 :\n");
for (i = 0;i < nx;i++) {
scanf_s("%d", &x[i]);
}
ary_reverse(x, nx);
for (i = 0;i < nx;i++) {
printf("%d\n", x[i]);
}
free(x);
}소수의 나열
버전1.
#include <stdio.h>
int main() {
int i, n;
unsigned long counter = 0;
for (n = 2;n <= 1000;n++) {
for (i = 2;i < n;i++) {
counter++;
if (n % i == 0)
break;
}
if (n == i)
printf("%d\n", n);
}
printf("나눗셈을 실행한 횟수 : %d", counter);
return 0;
}나눗셈 실행 횟수 : 78022
버전 2.
#include <stdio.h>
int main() {
int i, n;
int prime[500];
int ptr = 0;
unsigned long counter = 0;
prime[ptr++] = 2;
for (n = 3;n <= 1000;n += 2) {
for (i = 1;i < ptr;i++) {
counter++;
if (n % prime[i] == 0)
break;
}
if (ptr == i)
prime[ptr++] = n;
printf("%d\n", n);
}
printf("나눗셈 실행 횟수 : %lu\n", counter);
}나눗셈 실행 횟수 : 14622
버전 3.
#include <stdio.h>
int main(void)
{
int i, n;
int prime[500];
int ptr = 0;
unsigned long counter = 0;
prime[ptr++] = 2;
prime[ptr++] = 3;
for (n = 5;n <= 1000;n += 2) {
int flag = 0;
for (i = 1;counter++, prime[i] * prime[i] <= n;i++) {
counter++;
if (n % prime[i] == 0) {
flag = 1;
break;
}
}
if (!flag)
prime[ptr++] = n;
}
for (i = 0;i < ptr;i++)
printf("%d\n", prime[i]);
printf("곱셈과 나눗셈을 실행한 횟수 : %lu\n", counter);
return 0;
}곱셈/나눗셈 실행한 횟수 : 3774
흔한 컴공러 / 3학년