1. 배열 요소를 역순으로 정렬하기
- 맨 앞의 요소와 맨뒤에 요소 교환
- 교환 횟수 : 요소개수/2
- 요소 개수가 n인 배열 요소를 역순으로 정렬하는 코드
for(int i=0; i<n/2; i++)-> 왼쪽 요소의 인덱스 i (n이 7이면 0->1->2)
-> 오른쪽 요소의 인덱스 n-i-1 (n이 7이면 6->5->4)
- 두값의 교환
for(int i=0; i<n/2; i++) {
int t=a[i];
a[i]=a[i-i-1]; //a[i]와 a[n-i-1]값을 교환
a[n-i-1]=t;
}- 배열 요소를 역순으로 정렬
#include <stdio.h>
#include <stdlib.h>
//type형 x값과 y값을 교환
#define swap(type,x,y) do { type t= x; x=y; y=t;} while(0)
//요소개수가 n인 배열 a의 요소를 역순으로 정렬
void arr_reverse(int a[], int n)
{
for(int i=0; i<n/2; i++)
swap(int, a[i], a[n-i-1]);
}
int main()
{
int nx; //배열 x의 요소 개수
printf("요소 개수:");
scanf("%d",&nx);
int *x = (int*)calloc(nx,sizeof(int));
for(int i=0; i <nx; i++)
{
printf("x[%d]:",i);
scanf("%d",&x[i]);
}
arr_reverse(x,nx); //배열 x의 요소를 역순으로 정렬
printf("배열의 요소를 역순으로 정렬했습니다.\n");
for(int i=0; i <nx; i++)
{
printf("x[%d]= %d\n", i, x[i]);
}
free(x); //배열 x 해제
return(0);
}
2. 기수 변환하기
- 10진수 정수를 n진수 정수로 변환
- 정수를 n으로 나눈 나머지를 구하는 동시에 그 몫에 대해 나눗셈 반복
- 위 과정을 몫이 0이 될때까지 반복
- 구한 나머지를 거꾸로 늘어놓은 숫자가 기수로 변환한 숫자
ex) 59를 16진수로 변환
- 기수 변환 수행
//읽은 10진수를 2진수 ~36진수로 기수 변환하여 표시
#include <stdio.h>
//type형 x값과 y값을 교환
#define swap(type,x,y) do { type t=x; x=y; y=t;} while(0)
//정수값 x를 n진수로 변환한 숫자 문자의 정렬을 배열 d에 저장
int card_conv(unsigned x, int n, char d[])
{
char dchar[]="0123456789ABCDEFGHIJKLMNOPQEARUVWXYZ";
int digits = 0; //변환 후 자리수
if(x==0) //0이면
d[digits++] = dchar[0]; //변환후에도 0
else
while(x){
d[digits++] = dchar[x%n]; //n으로 나눈 나머지를 저장
x/=n;
}
for (int i=0; i < digits/2; i++) //배열 d를 역순으로 정렬
swap(char, d[i], d[digits-i-1]);
return digits;
}card_convr 함수
- 정수 x를 n진수로 변환한 숫자 문자의 정렬을 char형 배열 d에 저장하고 그 자릿수(배열에 저장한 문자수)를 변환
-먼저 x를 n으로 나눈 나머지를 인덱스로 하는, 배열 dchar 안의 문자 dchar[x%n]을 배열 d의 요소 d[digits]에 대입하고
digits 값을 증가
- x를 n으로 나눔
- 이 작업을 x가 0이 될때까지 반복
int main(void)
{
puts("10진수를 기수 변환합니다.");
int retry;
do {
unsigned no; //변환하는 정수
int cd; //기수
char cno[512]; //변환한 값의 각 자리의 숫자를 저장하는 문자 배열
printf("변환하는 음이 아닌 정수: ");
scanf("%u", &no);
do{
printf("어떤 진수로 변환할까요?(2-36): ");
scanf("%u", &cd);
}while(cd <2 || cd >36);
int dno = card_conv(no, cd, cno); //no를 dno자리의 cd진수로 변환
printf("%d진수로는", cd);
for(int i=0; i <dno; i++) //각 자리의 문자를 차례로 출력
printf("%c", cno[i]);
printf("입니다.\n");
printf("한번 더 할까요? (1 예/0 아니오); ");
scanf("%d", &retry);
} while(retry==1);
return 0;
}
cf. 전위형 증가 연산자 ++a
-식 전체를 평가하기 전에 피연산자의 값을 증가
- a=3 이고 b=++a
-> a가 증가한 값인 4가 됨, 그런 다음 ++a를 평가한 값 4를 b에 대입
cf. 후위형 증가 연산자 a++
- 식 전체를 평가한 후에 피연산자의 값을 증가
- a=3이고 b=a++
-> a++를 평가한 값 3을 b에 대입, 그런 다음 ++가 수행되어 a는 4가 됨
3. 소수 나열하기
- 소수 : 자신과 1 이외의 정수로 나누어 떨어지지 않는 정수
- 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않음
-1000 이하의 모든 소수를 나열(버전1)
#include <stdio.h>
int main(void)
{
unsigned long counter=0; //나눗셈 횟수
for(int n =2; n <= 1000; n++) {
int i;
for(i=2; i<n; i++) {
counter ++;
if(n%i==0) //나누어 떨어지면 소수가 아님
break; //더 이상의 반복은 불필요
}
if(n==i) //마지막까지 나누어 떨어지지 않음
printf("%d\n", n);
}
printf("나눗셈을 실행한 횟수: %lu\n", counter);
return 0;
}ex) 9일때 소수인지 판단하는 방법
- 안쪽의 for문에서 i값을 2,3,...8로 증가 9는 i가 3일 때 나누어떨어지므로 break문이 동작하여 for문 중단
- 나눗셈은 2와 3일 때 2회만 진행
- for문을 벗어날 떄의 i값은 3
ex) 13일때 소수인지 판단하는 방법
- 안쪽의 for문에서 i값을 2,3,..12로 증가 13은 한 번도 나누어떨어지지 않음
- 11회 나눗셈이 모두 수행
- for문을 벗어날 떄의 i값은 13
n이 소수인 경우 : for문이 끝까지 수행됨 -> i는 n과 같은값
n이 합성수인 경우 : for문이 중단됨 -> i는 n보다 작은 값
- n이 2또는 3으로 나누어떨어지지 않으면 2x2인 4또는 2x3인 6으로도 나누어 떨어지지 않음
-> 불필요한 나눗셈 실행
-> ex) 7이 소수인지는 7보다 작은 소수 2,3,5로 나눗셈을 실행하면 충분
3.1 알고리즘 개선 (1)
- 소수를 구하는 과정에서 그때까지 구한 소수를 배열 prime의 요소로 저장
- n이 소수인지를 판단할 때 쌓아 놓은 소수로 나눗셈 수행
- ptr : 배열에 저장한 소수의 개수를 나타내는 변수
//1000 이하의 소수를 나열(버전 2)
#include <stdion.h>
int main(void)
{
int prime[500]; //소수를 저장하는 배열
int ptr = 0; //이미 얻은 소수의 개수
unsigned long counter = 0; //나눗셈 횟수
prime[ptr++] = 2; //2는 소수입니다
for(int n= 3; n <=1000; n+=2){ //홀수만을 대상
int i;
for(i=1; i<ptr; i++) { //이미 얻은 소수로 나눔
counter++;
if(n% prime[i]==0) //나누어떨어지므로 소수가 아님
break;
}
if(ptr==i) //마지막까지 나누어떨어지지 않으면
prime[ptr++] = n; //배열에 저장
}
for(int i=0; i <ptr; i++)
printf("%d\n", prime[i]);
printf("나눗셈을 실행한 횟수: %lu\n", counter);
return 0;
}
ex) 3이 소수인지 판단 ( n=3, ptr 1->2)
- n값 3이 prime[1]에 저장
ex) 5가 소수인지 판단 (n=5이고 ptr 2->3)
- prime[1]에 저장한 3으로 나눗셈을 실행, 나누어 떨어지지 않으므로 소수라고 판단
- n값 5를 prime[2]에 저장
ex) 7이 소수인지 판단(n=7이고 ptr 3->4)
-prime[1]에 저장한 3과 prime[2]에 저장한 5로 나눗셈 실행 , 나누어 떨어지지 않으므로 소수라고 판단
- n값 7을 prime[3]에 저장
ex) 9가 소수인지 판단 (n=9이고 ptr 4->5)
- prime[1]에 저장한 3으로 나눗셈 실행
- 3으로 나누어 떨어지므로 합성수로 판단
3.2 알고리즘 개선(2)
- 100의 약수 (2,4,5,10,20,25,50,100)
(2x50), (4x25), (5x10). (10x10), (20x5), (25x4), (50x2)
- 정사각형 (10x10)을 중심으로 대칭
- 10까지만 소수로 나눗셈을 시도하고 그 과정에서 나누어 떨어지지 않으면 소수라고 판단해도 됨
n의 재곱근 이하의 어떤 소수로도 나누어 떨어지지 않으면 소수
prime[i]의 제곱이 n 이하인가?
//1000 이하의 소수를 나열 (버전3)
#include <stdio.h>
int main(void)
{
int prime[500]; //소수를 저장하는 배열
int ptr =0; //이미 얻은 소수의 개수
unsigned long counter = 0; //곱셈과 나눗셈의 실행 횟수
prime[ptr++] =2; //2는 소수
prime[ptr++] =3; //3은 소수
for(int n=5; n <=1000; n+=2) { //홀수만을 대상
int i;
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(int i=0; i<ptr; i++)
printf("%d\n", prime[i]);
printf("곱셈과 나눗셈을 실행한 횟수: %lu\n", counter);
return 0;
}
cf. 쉼표 연산자
opt1, opt2
- opt1을 평가하고 그 다음에 opt2를 평가
- 이 식 전체를 평가하여 얻은 값은 오른쪽 피연산자 opt2를 평가하여 얻은 자료형을 가진 값
counter ++. prime[i]*prime[i] <=n-> counter을 증가시키고 prime[i]*prime[i] <= n을 평가
-> for문의 반복을 계속할지는 prime[i]*prime[i]<=n의 값에 달려 있음
4. 다차원 배열 만들기
-2차원 배열 int a[3][3];
-2차원 배열의 요소는 1차원 배열
| a[0] | a[0][0] |
| a[0][1] | |
| a[0][2] | |
| a[1] | a[1][0] |
| a[1][1] | |
| a[1][2] | |
| a[2] | a[2][0] |
| a[2][1] | |
| a[2][2] |
-행의 개수 (a의 요소 개수) / 열의 개수 (요소의 요소 개수)
5. 날짜를 계산하는 프로그램 만들기
- 년, 월, 일의 3개 값이 주어지면 이를 이용해 연도의 지난 날 수를 구하는 프로그램
- issleap 함수
-> 매개 변수 year로 받은 연도가 윤년이면 1, 평년이면 0을 반환
- mdays[0] 평년
mdays[1] 윤년
- 윤년 구하기
-> 4의 배수 가운데 100의 배수를 제외하고, 제외한 배수 가운데 400의 배수를 다시 포함
year%4==0 && year %100!=0 || year %400 ==0;ex) 4월 15일
- 1월 날 수 + 2월 날 수 + 3월 날수 +15
//한 해의 지난 날 수를 구하여 출력
#include <stdio.h>
//각 달의 날 수
int mdays[][12] = {
{31,28,31,30,31,30,31,31,30,31,30,31},
{31,29,31,30,31,30,31,31,30,31,30,31}
};
//year년이 윤년인가?
int isleap(int year)
{
return year%4==0 && year %100 !=0 || year %400 ==0;
}
//y년 m월 d일의 그 해 지난 날 수를 구함
int dayof_year(int y, int m, int d)
{
int days= d;
for(int i=1; i<m; i++)
days +=mdays[isleap(y)][i-1];
return days;
}
int main(void)
{
int retry;
do {
int year,month, day; //년,월,일
printf("년: "); scanf("%d", &year);
printf("월: "); scanf("%d", &month);
printf("일: "); scanf("%d", &day);
printf("%d년의 %d일쨰입니다.\n", year, dayof_year(year,month,day));
printf("다시 할까요?(1 예/0 아니오): ");
scanf("%d",&retry);
} while(retry==1);
return 0;
}
'C언어 > 자료구조' 카테고리의 다른 글
| 3-2장 선형 검색 (0) | 2023.07.25 |
|---|---|
| 3-1장 검색 알고리즘이란? (0) | 2023.07.25 |
| 2-2 구조체란? (0) | 2023.07.24 |
| 2-1 장 배열(1) (0) | 2023.04.08 |
| 1장 기본 알고리즘 (0) | 2023.04.06 |
