C언어 알고리즘(8)
-
ETC./Algorithm
2019.07.08
[Algorithm] 이진탐색 알고리즘
이진탐색이란? 이진탐색(이분검색)은 말 그대로 검색할 자료를 반씩 나누어 그 중간값을 찾는 대상값과 비교하는 작업을 반복하여 자료를 찾는 검색을 뜻하며 빠른속도로 자료를 찾을 수 있습니다. 단 이진탐색을 하기위해서는 데이터가 정렬되어있어야 합니다. 이진탐색 과정 이진탐색을 할 데이터들이 위와 같이 정렬되어있다고 가정하고 숫자 7을 찾는 이진탐색과정을 알아보겠습니다. 1. 첫번째 주소와 마지막 주소의 위치를 활용하여 중간 위치를 계산합니다. 중간위치 = (0+9)/2 = 4.5 -> 소수점절삭 -> 4 2. 중간위치 4번째주소에 있는 값 8이 찾으려는 값인지 확인합니다. 7은 8보다 작으므로 찾으려는 값의 범위는 0~4번째 주소입니다. 3. 찾으려는 범위의 첫 번째 주소와 마지막 주소의 위치를 이용하여 중..
-
ETC./Algorithm
2019.07.06
[Algorithm] 입력받은 그레이코드를 2진수로 변환하기
입력받은 그레이코드를 2진수로 변환하기 그레이 코드를 이진수로 변환할 때는 첫번째 이진수는 그레이 비트를 그대로쓰고, 두번째 이진수 비트부터는 왼쪽에 구해놓은 2진수와 변경할 그레이코드를 XOR연산하여 씁니다. [C언어] 입력받은 2진수를 그레이코드로 변환하기 C언어 / C++ 코드 #include main(){ int i; int input[4], cont[4]; printf("그레이코드: "); for(int i=0; i
-
ETC./Algorithm
2019.07.03
[Algorithm] 입력받은 2진수의 보수 구하기
입력받은 이진수의 보수구하기 1의 보수는 0은 1로 1은 0으로 변경하면 되고, 2의 보수는1의 보수에 1을 더하면 됩니다. 즉 01100의 1의 보수는 10011이고, 2의 보수는 10100입니다. 이 로직을 어떻게 알고리즘으로 구현하느냐가 관건인데요. 1의 보수를 if문을 통해서 구해도 되지만 0은 1로, 1은 0으로 변환할때는 1에서 변환할 값을 그냥 빼주면 1의 보수를 좀 더 간편하게 구하실 수 있습니다. 2의 보수를 구할때는 1의 보수에 1을 더하면 되는데 이진수의 각자리가 배열의 각 요소에 분리되어 있으므로 맨 오른쪽 배열의 값에 1을 더해서 만약 맨 오른쪽 배열의 수가 1을 초과하면 앞자리 수로 1을 반올림 해줍니다. C언어/C++ 코드 #include main() { int a[5],b1[..
-
ETC./Algorithm
2019.06.11
[Algorithm] 입력받은 수를 소인수 분해하기
정수를 입력받아 소인수를 구해 출력하기 어떤 수를 소인수 분해하려면 입력받은 수를 2부터 차례대로 입력받은 수(NUM)의 제곱근까지의 숫자로 나누어 떨어지는지를 계산하시면 됩니다. 제곱근까지의 수 중 입력받은 수(NUM)을 처음으로 나누어 떨어지게 하는 수가 있으면 그 수는 소수이고, 입력받은 수(NUM)는 소인수가 됩니다. 소인수를 구했으면, 그때의 몫을 입력받은 수(NUM)에다가 치환하고 다시 NUM의 제곱근까지의 숫자로 나누는 작업을 반복합니다. 만약 제수가 NUM의 제곱근보다 커지면 그떄는 몫인 NUM자체가 그 수의 소인수가 됩니다. C언어 / C++ 코드 #include #include main() { int num,b,c,d,mok,nmg; int a[100]; scanf("%d",&num);..
-
ETC./Algorithm
2019.06.10
[Algorithm] 입력받은 수의 약수 구하기
정수를 입력받아 약수를 구해 출력하세요 어떤수 X를 1부터 X까지 차례대로 나누어 나머지가 0이 되게 하는 제수들이 X의 약수입니다. 예를 들어 10의 약수는 10을 나누었을 떄 나머지가 없게 하는 수이므로 1, 2, 5, 10입니다. C언어/C++ 코드 #include main() { int a[100];\ int b, mok, nmg, i; scanf("%d",&b); int c = 0, d = -1; while(1){ c++; if(c
-
ETC./Algorithm
2019.06.08
[Algorithm] 소수의 개수 구하기
배열 A[99]에 2~100 사이의 정수를 기억시킨 후 이 배열을 이용하여 소수의 개수를 구하시오. 배열에 들어있는 연속된 숫자의 소수 여부를 판별하기 위해서는 정수의 수열에서 처음 나온 소수의 배수들은 소수가 아니라는 원리를 이용합니다. 배열의 첫번째에 들어있는 2는 소수이지만 2의 배수들은 모두 소수가 아닙니다. 그러므로 2의 배수가 들어 있는 위치에는 모두 0을 채워 소수가 아님을 표시합니다. 소수의 판별은 배열의 해당 위치에 0이 들어 있는지만 확인하면 됩니다. C언어 / C++ 코드 #include main() { int k,i,j,m; int a[99]; k=1; do{ //배열 a에 값을 입력한다. k++; a[k-2] = k; }while(k98){ printf("%d번쨰까지의 소수의 갯수..
-
ETC./Algorithm
2019.06.07
[Algorithm] 소수의 합 구하기
임의의 정수를 입력받아 그 안에 포함된 소수의 합을 구하기 입력받은 숫자 X의 범위에 속하는 모든 소스의 합계를 구하려면 숫자 2에서 X까지 증가시키면서 각각의 숫자가 소수인지를 판별한 후, 그 수가 소수일 때만 합계에 누적시키면 됩니다. [C언어] 소수를 판별하는 알고리즘 C언어 / C++ 코드 #include main(){ int a, sum, i, j; scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다. sum=0; i=2; j=2; while(1){ //무한루프 j=2;; while(i%j!=0) //i를 j로 나눈 나머지가 0 이아니라면 반복문을 수행합니다. j++; if(i==j){ //i와 j가 같으면 sum의 값에 i를 누적시킵니다. sum+=i; } if(i
-
ETC./Algorithm
2019.06.06
[Algorithm] 소수를 판별하는 알고리즘
1보다 큰 임의의 정수를 입력하여 소수를 판별 1. 입력받은 숫자보다 작은 모든숫자를 다 나누어본다. 어떤 수 X가 소수 인지를 판별하려면 X를 2부터 X보다 작은 수(X-1)까지 차례대로 나누어 떨어지는지 검사하면 됩니다. 예컨데 5는 2,3,4,로 나누었을때 한번도 나누어 떨어지지 않으므로 소수이고, 4는 2로 나누었을때 나누어 떨어지므로 소수가 아닙니다. C언어 / C++ 코드 #include main(){ int a, i, j; scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다. i=2; j=a-1; f(a==1){ //1은 소수가 아님 printf("소수아님"); return; } while(1){ //무한루프 if(i
-
ETC./Algorithm 2019.07.08[Algorithm] 이진탐색 알고리즘 이진탐색이란? 이진탐색(이분검색)은 말 그대로 검색할 자료를 반씩 나누어 그 중간값을 찾는 대상값과 비교하는 작업을 반복하여 자료를 찾는 검색을 뜻하며 빠른속도로 자료를 찾을 수 있습니다. 단 이진탐색을 하기위해서는 데이터가 정렬되어있어야 합니다. 이진탐색 과정 이진탐색을 할 데이터들이 위와 같이 정렬되어있다고 가정하고 숫자 7을 찾는 이진탐색과정을 알아보겠습니다. 1. 첫번째 주소와 마지막 주소의 위치를 활용하여 중간 위치를 계산합니다. 중간위치 = (0+9)/2 = 4.5 -> 소수점절삭 -> 4 2. 중간위치 4번째주소에 있는 값 8이 찾으려는 값인지 확인합니다. 7은 8보다 작으므로 찾으려는 값의 범위는 0~4번째 주소입니다. 3. 찾으려는 범위의 첫 번째 주소와 마지막 주소의 위치를 이용하여 중..
-
ETC./Algorithm 2019.07.06[Algorithm] 입력받은 그레이코드를 2진수로 변환하기 입력받은 그레이코드를 2진수로 변환하기 그레이 코드를 이진수로 변환할 때는 첫번째 이진수는 그레이 비트를 그대로쓰고, 두번째 이진수 비트부터는 왼쪽에 구해놓은 2진수와 변경할 그레이코드를 XOR연산하여 씁니다. [C언어] 입력받은 2진수를 그레이코드로 변환하기 C언어 / C++ 코드 #include main(){ int i; int input[4], cont[4]; printf("그레이코드: "); for(int i=0; i
-
ETC./Algorithm 2019.07.03[Algorithm] 입력받은 2진수의 보수 구하기 입력받은 이진수의 보수구하기 1의 보수는 0은 1로 1은 0으로 변경하면 되고, 2의 보수는1의 보수에 1을 더하면 됩니다. 즉 01100의 1의 보수는 10011이고, 2의 보수는 10100입니다. 이 로직을 어떻게 알고리즘으로 구현하느냐가 관건인데요. 1의 보수를 if문을 통해서 구해도 되지만 0은 1로, 1은 0으로 변환할때는 1에서 변환할 값을 그냥 빼주면 1의 보수를 좀 더 간편하게 구하실 수 있습니다. 2의 보수를 구할때는 1의 보수에 1을 더하면 되는데 이진수의 각자리가 배열의 각 요소에 분리되어 있으므로 맨 오른쪽 배열의 값에 1을 더해서 만약 맨 오른쪽 배열의 수가 1을 초과하면 앞자리 수로 1을 반올림 해줍니다. C언어/C++ 코드 #include main() { int a[5],b1[..
-
ETC./Algorithm 2019.06.11[Algorithm] 입력받은 수를 소인수 분해하기 정수를 입력받아 소인수를 구해 출력하기 어떤 수를 소인수 분해하려면 입력받은 수를 2부터 차례대로 입력받은 수(NUM)의 제곱근까지의 숫자로 나누어 떨어지는지를 계산하시면 됩니다. 제곱근까지의 수 중 입력받은 수(NUM)을 처음으로 나누어 떨어지게 하는 수가 있으면 그 수는 소수이고, 입력받은 수(NUM)는 소인수가 됩니다. 소인수를 구했으면, 그때의 몫을 입력받은 수(NUM)에다가 치환하고 다시 NUM의 제곱근까지의 숫자로 나누는 작업을 반복합니다. 만약 제수가 NUM의 제곱근보다 커지면 그떄는 몫인 NUM자체가 그 수의 소인수가 됩니다. C언어 / C++ 코드 #include #include main() { int num,b,c,d,mok,nmg; int a[100]; scanf("%d",&num);..
-
ETC./Algorithm 2019.06.10[Algorithm] 입력받은 수의 약수 구하기 정수를 입력받아 약수를 구해 출력하세요 어떤수 X를 1부터 X까지 차례대로 나누어 나머지가 0이 되게 하는 제수들이 X의 약수입니다. 예를 들어 10의 약수는 10을 나누었을 떄 나머지가 없게 하는 수이므로 1, 2, 5, 10입니다. C언어/C++ 코드 #include main() { int a[100];\ int b, mok, nmg, i; scanf("%d",&b); int c = 0, d = -1; while(1){ c++; if(c
-
ETC./Algorithm 2019.06.08[Algorithm] 소수의 개수 구하기 배열 A[99]에 2~100 사이의 정수를 기억시킨 후 이 배열을 이용하여 소수의 개수를 구하시오. 배열에 들어있는 연속된 숫자의 소수 여부를 판별하기 위해서는 정수의 수열에서 처음 나온 소수의 배수들은 소수가 아니라는 원리를 이용합니다. 배열의 첫번째에 들어있는 2는 소수이지만 2의 배수들은 모두 소수가 아닙니다. 그러므로 2의 배수가 들어 있는 위치에는 모두 0을 채워 소수가 아님을 표시합니다. 소수의 판별은 배열의 해당 위치에 0이 들어 있는지만 확인하면 됩니다. C언어 / C++ 코드 #include main() { int k,i,j,m; int a[99]; k=1; do{ //배열 a에 값을 입력한다. k++; a[k-2] = k; }while(k98){ printf("%d번쨰까지의 소수의 갯수..
-
ETC./Algorithm 2019.06.07[Algorithm] 소수의 합 구하기 임의의 정수를 입력받아 그 안에 포함된 소수의 합을 구하기 입력받은 숫자 X의 범위에 속하는 모든 소스의 합계를 구하려면 숫자 2에서 X까지 증가시키면서 각각의 숫자가 소수인지를 판별한 후, 그 수가 소수일 때만 합계에 누적시키면 됩니다. [C언어] 소수를 판별하는 알고리즘 C언어 / C++ 코드 #include main(){ int a, sum, i, j; scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다. sum=0; i=2; j=2; while(1){ //무한루프 j=2;; while(i%j!=0) //i를 j로 나눈 나머지가 0 이아니라면 반복문을 수행합니다. j++; if(i==j){ //i와 j가 같으면 sum의 값에 i를 누적시킵니다. sum+=i; } if(i
-
ETC./Algorithm 2019.06.06[Algorithm] 소수를 판별하는 알고리즘 1보다 큰 임의의 정수를 입력하여 소수를 판별 1. 입력받은 숫자보다 작은 모든숫자를 다 나누어본다. 어떤 수 X가 소수 인지를 판별하려면 X를 2부터 X보다 작은 수(X-1)까지 차례대로 나누어 떨어지는지 검사하면 됩니다. 예컨데 5는 2,3,4,로 나누었을때 한번도 나누어 떨어지지 않으므로 소수이고, 4는 2로 나누었을때 나누어 떨어지므로 소수가 아닙니다. C언어 / C++ 코드 #include main(){ int a, i, j; scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다. i=2; j=a-1; f(a==1){ //1은 소수가 아님 printf("소수아님"); return; } while(1){ //무한루프 if(i