이진탐색이란? 이진탐색(이분검색)은 말 그대로 검색할 자료를 반씩 나누어 그 중간값을 찾는 대상값과 비교하는 작업을 반복하여 자료를 찾는 검색을 뜻하며 빠른속도로 자료를 찾을 수 있습니다. 단 이진탐색을 하기위해서는 데이터가 정렬되어있어야 합니다. 이진탐색 과정 이진탐색을 할 데이터들이 위와 같이 정렬되어있다고 가정하고 숫자 7을 찾는 이진탐색과정을 알아보겠습니다. 1. 첫번째 주소와 마지막 주소의 위치를 활용하여 중간 위치를 계산합니다. 중간위치 = (0+9)/2 = 4.5 -> 소수점절삭 -> 4 2. 중간위치 4번째주소에 있는 값 8이 찾으려는 값인지 확인합니다. 7은 8보다 작으므로 찾으려는 값의 범위는 0~4번째 주소입니다. 3. 찾으려는 범위의 첫 번째 주소와 마지막 주소의 위치를 이용하여 중..
입력받은 그레이코드를 2진수로 변환하기 그레이 코드를 이진수로 변환할 때는 첫번째 이진수는 그레이 비트를 그대로쓰고, 두번째 이진수 비트부터는 왼쪽에 구해놓은 2진수와 변경할 그레이코드를 XOR연산하여 씁니다. [C언어] 입력받은 2진수를 그레이코드로 변환하기 C언어 / C++ 코드 #include main(){ int i; int input[4], cont[4]; printf("그레이코드: "); for(int i=0; i
입력받은 이진수를 그레이코드로 변환하기 이진수를 그레이 코드로 변환할때는 첫번째 그레이 비트는 이진수 비트를 그대로 내려쓰고, 두번째 그레이 비트부터는 변경할 이진수의 해당번째 비트와 그 왼쪽의 비트를 XOR연산을 하여 내려적습니다. [C언어] 입력받은 그레이코드를 2진수로 변환하기 C언어 / C++ 코드 #include main(){ int i; int input[4], cont[4]; printf("이진수 입력 :"); for(int i=0; i
입력받은 이진수의 보수구하기 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[..
입력 받은 10진수를 2진수로 변환하기 10진수를 2진수로 변환하려면 10진수를 2로 나누어 몫 과 나머지를 구한 후 나머지는 출력할 배열에 저장하고 몫은 또 2로나누어 나머지를 구하여 출력할 배열에 저장하는 과정을 몫이 0이 될때까지 무한반복 후 몫이 0이되었을경우 저장한 출력배열을 거꾸로 출력시키면 됩니다. C언어 / C++ 코드 #include main() { int num, num2, b, mok, nmg, i; int a[10]; scanf("%d",&num); num2 = num; b = -1; do{ b++; mok = num/2; nmg = num-mok*2; a[b] = nmg; num = mok; }while(mok!=0); printf("%d를 2진수로 변환한 값 = ",num2); ..
정수를 입력받아 소인수를 구해 출력하기 어떤 수를 소인수 분해하려면 입력받은 수를 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);..
정수를 입력받아 약수를 구해 출력하세요 어떤수 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
입력받은 두수의 최대공약수와 최소공배수를 구하기 최대공약수와 최소공배수를 구할 두 수 중 큰수와 작은수를 정한 뒤 큰 수를 작은수로 나누어 나머지를 구합니다. 이때 나머지가 0이면 그때의 작은수가 최대공약수이고, 원래의 두수를 곱한 값을 최대공약수로 나눈 값이 최소공배수입니다. 만약 큰수를 작은수로 나누었을 때, 나머지가 0이 아니면, 그떄의 작은 수를 큰수로 하고 나머지를 작은수로 하여 나머지가 0이 될때까지 반복합니다. 더 빠른 최대공약수 구하는 유클리드 호제법이 궁금하시다면 아래 글을 참고해주세요. [Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기 C언어 / C++ 코드 #include main() { int a,b,big,small,mok,nmg,gcm,lcm; scanf("%d..
배열 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번쨰까지의 소수의 갯수..
임의의 정수를 입력받아 그 안에 포함된 소수의 합을 구하기 입력받은 숫자 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
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
피보나치 수열이란? 피보나치 수열은 첫번째 항과 두번쨰 항을 더해서 세번째 항을 만들고 두번쨰 항과 세번쨰 항을 더해서 네번쨰 항을 만드는 방법으로, 계속해서 다음항을 만들어가는 수열입니다. 피보나치 수열의 10번째 항까지의 합계 구하기 3개의 변수로 먼저 첫번째 항(A), 두번째 항(B), 세번째 항(C)를 만든 후, 두번째 항(B)를 첫번째 항(A)에 치환하고 세번째 항(C)를 두번째 항(B)에 치환한 후 첫번째 항(A)와 두번째 항(B)를 더하여 다시 세번째 항(C)를 만드는 방법을 반복합니다. C언어 / C++ 코드 #include main() { int a = 1, b =1; //첫번째항, 두번쨰항 int c; //세번째항 int sum = 2, cnt = 2; //합계 sum, 항의갯수 cnt..
팩토리얼 수열이란? 수학에서, 자연수의 계승 또는 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱입니다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말입니다. 기호는 느낌표(!)를 사용합니다. 팩토리얼이라고 읽으며 팩토리얼을 줄여서 팩이라고 읽기도 합니다. 팩토리얼 수열의 5번째 항까지의 합계구하기 (1!+2!+3!+4!+5!) 팩토리얼의 합계를 구하는 알고리즘을 풀기 위해서는 각 항 사이에서 일정한 비율로 증가하여 곱할 값으로 사용할 증가 배수 변수 i, 증가 배수를 곱하여 수열의 각 항을 만들어 저장할 변수 Sum, 그리고 수열의 각 항인 j가 만들어질때마다 그 값을 누적할 변수 K가 필요합니다. C언어 / C++ 코드 #include main() { ..