[알고리즘 + 자료구조]/[Do it 자료구조와 함께 배우는 알고리즘]
[알고리즘] Do it 자료구조와 알고리즘 1장 정리
Hevton
2020. 10. 7. 19:30
반응형
연습문제_Q1 > 네 값의 최댓값을 구하는 함수 max4
#include <stdio.h>
int max4(int a, int b, int c, int d)
{
int arr[4] = {a, b, c, d};
int max = arr[0];
for(int i=1; i < sizeof(arr)/sizeof(int);i++)
{
if(max<arr[i])
max = arr[i];
}
return max;
}
int main()
{
printf("%d", max4(5, 6, 3, 2));
return 0;
}
연습문제_Q2 > 세 값의 최솟값을 구하는 함수 min3
#include <stdio.h>
int min3(int a, int b, int c)
{
int arr[3] = {a, b, c};
int min = arr[0];
for(int i=1; i < sizeof(arr)/sizeof(int);i++)
{
if(min>arr[i])
min = arr[i];
}
return min;
}
int main()
{
printf("%d", min3(5, 6, 3));
return 0;
}
연습문제_Q3 > 네 값의 최솟값을 구하는 함수 min4
#include <stdio.h>
int min4(int a, int b, int c, int d)
{
int arr[4] = {a, b, c, d};
int min = arr[0];
for(int i=1; i < sizeof(arr)/sizeof(int);i++)
{
if(min>arr[i])
min = arr[i];
}
return min;
}
int main()
{
printf("%d", min4(5, 6, 3, 2));
return 0;
}
연습문제_Q4 > 세 값의 대소관계 13종류의 모든 조합에 대해 중앙값을 구하여 출력
#include <stdio.h>
int mid3(int a, int b, int c)
{
if(a>=b)
{
if(b>=c)
return b;
else if(a>=c)
return c;
else
return a;
}
else if(a>=c)
return a;
else if(b>=c)
return c;
else
return b;
}
int main()
{
printf("mid3 (%d %d %d) = %d입니다.\n", 3, 2, 1, mid3(3, 2, 1)); /* [A] a > b > c */
printf("mid3 (%d %d %d) = %d입니다.\n", 3, 2, 2, mid3(3, 2, 2)); /* [B] a > b = c */
printf("mid3 (%d %d %d) = %d입니다.\n", 3, 1, 2, mid3(3, 1, 2)); /* [C] a > c > b */
printf("mid3 (%d %d %d) = %d입니다.\n", 3, 2, 3, mid3(3, 2, 3)); /* [D] a = c > b */
printf("mid3 (%d %d %d) = %d입니다.\n", 2, 1, 3, mid3(2, 1, 3)); /* [E] c > a > b */
printf("mid3 (%d %d %d) = %d입니다.\n", 3, 3, 2, mid3(3, 3, 2)); /* [F] a = b > c */
printf("mid3 (%d %d %d) = %d입니다.\n", 3, 3, 3, mid3(3, 3, 3)); /* [G] a = b = c */
printf("mid3 (%d %d %d) = %d입니다.\n", 2, 2, 3, mid3(2, 2, 3)); /* [H] c > a = b */
printf("mid3 (%d %d %d) = %d입니다.\n", 2, 3, 1, mid3(2, 3, 1)); /* [I] b > a > c */
printf("mid3 (%d %d %d) = %d입니다.\n", 2, 3, 2, mid3(2, 3, 2)); /* [J] b > a = c */
printf("mid3 (%d %d %d) = %d입니다.\n", 1, 3, 2, mid3(1, 3, 2)); /* [K] b > c > a */
printf("mid3 (%d %d %d) = %d입니다.\n", 2, 3, 3, mid3(2, 3, 3)); /* [L] b = c > a */
printf("mid3 (%d %d %d) = %d입니다.\n", 1, 2, 3, mid3(1, 2, 3)); /* [M] c > b > a */
return 0;
}
연습문제_Q5 > 중앙값 구하는 함수의 다른 예로 아래 코드가 있다. 연습문제 4보다 효율이 떨어지는 이유는?
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;
}
/*
예상) 연습문제 4는 최소 2번~4번이면 모두 끝나는데, 여긴 연산이 최소 2번~4번이상 이여서?
정답) if에서 b>=a와 b<=a 판단의 반대판단인 b<a와 b>a을 else if에서 또 명시적으로 판단과정을 거치므로
*/
연습문제_Q6 > while문이 종료될 때 변수 i의 값이 n+1이 됨을 확인(i값 출력하도록 프로그램 코딩)
#include <stdio.h>
int main()
{
int i, n;
int sum;
puts("1부터 n까지의 합을 구합니다.");
printf("n의 값 : ");
scanf("%d", &n);
sum = 0;
i = 1;
while(i<=n) {
sum +=i;
i++;
}
printf("1부터 %d까지의 합은 %d입니다.\n", n, sum);
printf("i : %d", i);
return 0;
}
연습문제_Q7 > n이 7이면 '1 + 2 + 3 + 4 + 5 + 6 + 7 = 28'로 출력하는 프로그램 작성
#include <stdio.h>
int main()
{
int n, sum=0;
puts("1부터 n까지의 합을 구합니다.");
printf("n 값 : ");
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
sum+=i;
if(i<n)
printf("%d + ", i);
else
printf("%d = %d", i, sum);
}
}
연습문제_Q8 > 가우스의 덧셈 방법을 사용하여 1부터 n까지의 정수의 합을 구하는 프로그램 작성
#include <stdio.h>
int main()
{
int n;
puts("1부터 n까지의 합을 구합니다.");
printf("n값 : ");
scanf("%d", &n);
/*
가우스의 덧셈
ex) n = 3;
3 2 1
1 2 3
+
4 4 4
12 -> 1부터 n까지를 두번 더해준 것이므로
나누기 2를 해주면, 원하는 값이 나온다.
-> n*(n+1)/2의 식이 나온다
*/
printf("%d", n*(n+1)/2);
return 0;
}
연습문제_Q9 > 정수 a,b를 포함하여 그 사이의 모든 정수의 합을 구하는 함수 sumof를 작성
#include <stdio.h>
int sumof(int a, int b)
{
int init, n, sum=0;
if(a>=b) {
n = a;
init = b;
} else {
n = b;
init = a;
}
for(int i=init;i<=n;i++)
{
sum+=i;
}
return sum;
}
int main()
{
printf("%d", sumof(3, 5));
}
연습문제_Q10 > 두 변수 a, b에 정수를 입력하고 b - a를 출력하는 프로그램 작성
#include <stdio.h>
int main()
{
int a, b;
printf("a의 값 : ");
scanf("%d", &a);
do {
printf("b의 값 : ");
scanf("%d", &b);
if(a>=b)
puts("a보다 큰 값을 입력하세요!");
} while(a>=b);
printf("b - a는 %d입니다.", b-a);
return 0;
}
연습문제_Q11 > 양의 정수를 입력하고 자릿수를 출력하는 프로그램 작성
#include <stdio.h>
int main()
{
int n, count=0;
scanf("%d", &n);
while(n>0)
{
count++;
n/=10;
}
printf("그 수는 %d자리입니다.", count);
return 0;
}
연습문제_Q12 > 위쪽과 왼쪽에 곱하는 수가 있는 곱셈표 출력 프로그램 작성
#include <stdio.h>
int main()
{
printf(" |");
for(int i=1; i<=9; i++)
{
printf(" %2d", i);
}
printf("\n---+----------------------------\n");
for(int i=1; i<=9; i++)
{
printf(" %2d |", i);
for(int j=1; j<=9; j++)
{
printf(" %2d", i*j);
}
putchar('\n');
}
return 0;
}
연습문제_Q13 > 12번과 동일하되 곱셈이 아닌 덧셈을 출력
#include <stdio.h>
int main()
{
printf(" |");
for(int i=1; i<=9; i++)
{
printf(" %2d", i);
}
printf("\n---+----------------------------\n");
for(int i=1; i<=9; i++)
{
printf(" %2d |", i);
for(int j=1; j<=9; j++)
{
printf(" %2d", i+j);
}
putchar('\n');
}
return 0;
}
연습문제_Q14 > 입력한 수를 한 변으로 하는 정사각형 * 출력
#include <stdio.h>
int main()
{
int n;
printf("입력할 수 : ");
scanf("%d", &n);
for(int i=0; i<n;i++)
{
for(int j=0;j<n;j++)
{
printf("*");
}
putchar('\n');
}
}
연습문제_Q15 > 높이와 너비에 맞는 직사각형 * 출력
#include <stdio.h>
int main()
{
int r, c;
puts("직사각형을 출력합니다.");
printf("높이 : ");
scanf("%d", &r);
printf("너비 : ");
scanf("%d", &c);
for(int i=0; i<r;i++)
{
for(int j=0;j<c;j++)
{
printf("*");
}
putchar('\n');
}
return 0;
}
연습문제_Q16 > 직각 이등변 삼각형을 출력하는 triangleLB 프로그램 작성
#include <stdio.h>
void triangleLB(int n)
{
for(int i=0; i<n; i++){
for(int j=0; j<=i; j++){
putchar('*');
}
putchar('\n');
}
}
int main()
{
triangleLB(5);
return 0;
}
연습문제_Q16-1 > 왼쪽 위, 오른쪽 위, 오른쪽 아래가 직각인 이등변 삼각형 출력하는 함수 작성
#include <stdio.h>
void triangleLU(int n)
{
for(int i=n; i>0; i--){
for(int j=0; j<i; j++){
putchar('*');
}
putchar('\n');
}
}
void triangleRU(int n)
{
for(int i=n; i>0; i--){
for(int x=0; x<n-i; x++)
putchar(' ');
for(int j=0; j<i; j++){
putchar('*');
}
putchar('\n');
}
}
void triangleRB(int n)
{
for(int i=0; i<n; i++){
for(int x=0; x<n-i-1;x++)
putchar(' ');
for(int j=0; j<=i; j++){
putchar('*');
}
putchar('\n');
}
}
int main()
{
triangleRU(5);
//triangleLU(5);
//triangleRB(5);
return 0;
}
연습문제_Q17 > n단의 피라미드 출력 함수 프로그램 작성
#include <stdio.h>
void spira(int n)
{
for(int i=1; i <=n; i++){
for(int x=0; x<n-i; x++)
putchar(' ');
for(int j=0; j<i*2-1; j++)
putchar('*');
putchar('\n');
}
}
int main()
{
spira(4);
return 0;
}
연습문제_Q18 > 아래를 향한 n단의 숫자 피라미드 출력 함수 작성
#include <stdio.h>
void nrpira(int n)
{
for(int i=n; i>0; i--){
for(int x=0; x<n-i; x++)
putchar(' ');
for(int j=0; j<i*2-1; j++)
printf("%d", (n-i+1)%10);
putchar('\n');
}
}
int main()
{
nrpira(22);
return 0;
}
/*
아래 코드는 i의 값을 n부터가 아닌 1부터로 변경한 방법. 출력은 동일
#include <stdio.h>
void nrpira(int n)
{
for(int i=1; i<=n; i++){
for(int x=0; x<=i; x++)
putchar(' ');
for(int j=0; j<(n-i+1)*2-1; j++)
printf("%d", i%10);
putchar('\n');
}
}
int main()
{
nrpira(5);
return 0;
}
*/
< 16주로 공부단위를 나눔 >
알고리즘 : 문제 해결 순서
자료구조 : 컴퓨터에 정보를 효율적으로 저장하고 관리하는 방법.
자료구조를 만드는 과정은 알고리즘으로 순서화되어 있으며, 다시 이 자료구조를 가지고 효율적인 알고리즘을 구현
-> 알고리즘과 자료구조는 상호보완관계
논리 연산자의 단축 평가
|| : 왼쪽 피연산자 x와 오른쪽 피연산자 y중 어느 하나라도 0이 아니면 논리식 x||y는 참이므로,
왼쪽 피연산자를 평가한 값이 1이면 오른쪽 피연산자는 평가하지 않는다.
&& : 마찬가지로 &&인 경우엔 왼쪽 피연산자를 평가한 값이 0이면 오른쪽 피연산자는 평가하지 않는다.
이처럼 논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피연산자의 평가를 수행하지 않는데, 이를 단축평가라고 한다.
드모르간 법칙
각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.
• x && y와 !(!x || !y)는 동일
• x || y와 !(!x && !y)는 동일
공부 출처 - 'Do it! 자료구조와 함께 배우는 알고리즘 입문 C언어 편' 도서
반응형