아티클 목록

정보처리기사 실기 복습 02

반복문을 이용한 피보나치 수열

  • 1+1+2+3+5+8+13…의 순서로 나열되는 피보나치 수열
  • 입력받은 수의 항까지 합을 구하기
public class Test12 {
  
  public static void main(String[] args) {
        
    Scanner sc = new Scanner(System.in);
    
    int a=1, b=1, c=0;
    int sum = 2;
    
    int n = sc.nextInt();
    
    for(int i=3; i <= n; i++) {
      c = a + b;
      System.out.println(c);
      
      sum += c;
      
      a = b;
      b = c;
    }
    
    System.out.println(sum);
  }
}
  • 배열 A[99]에 2~100 사이의 정수를 기억시킨 후 이 배열을 이용하여 소수의 개수를 구하시오
    • 배열에 들어 있는 연속된 숫자의 소수 여부를 판별하기 위해서는 정수의 수열에서 처음 나온 소수의 배수들은 소수가 아니라는 원리를 이용
public class Test18 {
  
  public static void main(String[] args) {
        
    int[] A = new int[99];
    int cnt = 0;
    int m = 0;
    
    for (int i=2; i<99; i++) {
      A[i] = i;
    }
    
    for(int j=2; j<99; j++) {
      
      if (A[j] == 0) {
        continue;
      }
      
      cnt++;
      System.out.println("소수입니다 : "+j);
      m = j;
      
      while(true) {
        m += A[j]; // 소수의 배수의 인덱스
        
        if (m > 98) {
          break;
        }
        
        A[m] = 0; // 배수의 위치는 0으로 바꿔 체크를 안함
      }
    }
    
    System.out.println("소수의 개수 : " + cnt);
  }
}

최대공약수, 최소공배수

  • 두 수를 입력 받아 두 수의 최대공약수와 최소공배수를 계산해서 출력하시오
    • 최대공약수(GCD(Greatest Common Divisor) - 공통으로 가지고 있는 약수 중 가장 큰 수
    • 최소공배수LCM(Least Common multiple) - 두 수의 공통인 배수 중 가장 작은 수
    • 최대공약수와 최소공배수를 구할 두 수 중 큰 수와 작은 수를 정한 뒤 큰 수를 작은 수로 나누어 나머지를 구한다
    • 이 때 나머지가 0이면 그 때의 작은 수가 최대공약수이고, 원래의 두 수를 곱한 값을 최대공약수로 나눈 값이 최소공배수이다
    • 만약 큰 수를 작은 수로 나누었을 때 나머지각 0이 아니면, 그 때의 작은 수를 큰 수로 하고 나머지를 작은 수로 하여 나머지가 0이 될 때까지 반복
      • 이와 같이 큰 수를 작은 수로 나눠 나머지가 0이 될 떄까지 반복하여 최대공약수를 구하는 방법을 유클리드 호제법이라 함
public class Test19 {
  
  public static void main(String[] args) {
        
    Scanner sc = new Scanner(System.in);
    
    int num1 = sc.nextInt();
    int num2 = sc.nextInt();
    
    int big = 0, small = 0, gcd = 0, 
      lcm = 0, quotient = 0,  remainder = 0;
    
    if (num1 >= num2) {
      big = num1;
      small = num2;
    } else {
      big = num2;
      small = num1;
    }
    
    while(true) {
      quotient = big/small;
      remainder = big%small;
      
      if (remainder == 0) {
        gcd = small;
        lcm = num1*num2/gcd;
        
        System.out.println("최대 공약수 : "+gcd+", 최소  공배수 : "+lcm);
        break;
      }
      
      big = small;
      small = remainder;
    }
  }
}

약수 구하기

  • 정수를 입력 받아 약수를 구해 출력
  • 약수 - 어떤 수를 나누어 나머지가 없게 할 수 있는 수
public class Test20 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int remainder = 0;
    List<Integer> divisors = new ArrayList<Integer>();
    
    for(int i=1; i<=n; i++) {
      remainder = n%i;
      
      if (remainder == 0) {
        System.out.println("약수 : "+i);
        divisors.add(i);
      }
    }
    
    System.out.println(divisors);
  }
}

소인수 분해하기

  • 정수를 입력 받아 소인수를 구해 출력
  • 소인수 - 어떤 수를 구성하는 인수 중에서 소수인 것
    • 어떤 수의 약수중에서 소수인 녀석들만 가리켜서 소인수라 칭함
  • 소인수 분해 - 소수를 이용하여 그 수를 만드는 곱의 형태로 표현하는 것.
  • 어떤수 n을 소인수 분해하려면 n을 2부터 차례대로 n의 제곱근까지의 숫자로 나누어 떨어지는지 검사하면 됨
    • 제곱근까지의 수 중 n을 처음으로 나누어 떨어지게 하는 수가 있으면 그 수는 소수
      • n의 소인수가 됨
    • 소인수를 구했으면 그 때의 몫을 n로 하여 2부터 다시 n의 제곱근까지의 숫자로 나누는 작업을 반복
    • 만약 제수가 n의 제곱근보다 커지면 그때는 몫인 n자체가 그 수의 소인수가 된다
public class Test21 {
  public static void main(String[] args) {
        
    Scanner sc = new Scanner(System.in);
    
    // 정수 n을 입력받아 소인수 구해 출력
    int n = sc.nextInt();
    int sqrt = 0, quotient = 0, remainder = 0;
    int d = 2; // 제수
    
    // 소인수를 저장할 리스트
    List<Integer> prime = new ArrayList<Integer>();
    
    while(true) {
      
      sqrt = (int)Math.sqrt(n);
      
      while(true) {
        // 제수가 제곱근보다 커지면 피제수 자체가  입력받은 수의 소인수
        if (d > sqrt) {
          d = n;
          break;
        }
        
        quotient = n/d; // 몫
        remainder = n%d; // 나머지
        
        if (remainder == 0) {
          // 처음으로 나머지가 0이 되게 하는 수가  소인수
              break;
        } else {
          d++; // 제수를 2부터 제곱근(sqrt)까지  증가시킴
        }
      }
      
      System.out.println("소인수 : "+d);
      prime.add(d);
      
      if (n == d) {
        // 제수가 입력값과 같으면 소인수분해 과정이 모두  마친 것
        break;
      }
      
      // 소인수를 구했으면 그 때의 몫에 대해 다시 소인수를  구하기 위한 처리
      n = quotient;
    }
    
    System.out.println(prime); // 소인수 분해된 결과 출력
  }
}

진법변환 - 10진수를 2진수로 변환하기

  • 10진수를 입력 받아 2진수로 변환하시오
  • 10진수를 2진수로 변환하려면 10진수를 2로 나누어 나머지를 구한 후 저장,
    • 다시 몫을 2로 나누어 나머지를 구해 저장하는 과정을 반복.
    • 몫이 0이 될 때까지 이 작업을 반복
    • 마지막에 구한 나머지부터 거꾸로 출력.
public class Test22 {
  
  public static List<Integer> revserList(List<Integer>  reversed_binary) {
    Stack<Integer> binary_stack = new Stack<Integer>();
    List<Integer> binary_list = new ArrayList<Integer>();
    
    for (Integer i : reversed_binary) {
      binary_stack.push(i);
    }
    
    int size = binary_stack.size();
    for(int i=0; i<size; i++) {
      binary_list.add(binary_stack.pop());
    }
    
    return binary_list;
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    
    int quotient = 0, remainder = 0;
    List<Integer> reversed_binary = new ArrayList<Integer>();
    
    do {
      quotient = n/2;
      remainder = n%2;
      
      reversed_binary.add(remainder);
      n = quotient;
    } while(quotient != 0);
    
    reversed_binary = revserList(reversed_binary);
    System.out.println(reversed_binary);
  }
}

댓글