정보처리기사 실기 - 4. 서버 프로그램 구현(3) /알고리즘

NCS 정보처리기사

•알고리즘

특정 문제를 해결하기 위한 일련의 순차적 계산 혹은 풀이 절차

 

- 알고리즘의 기본 절차 구조

• 순차구조(Sequence) : 직선형, 시작부터 마지막까지 순차적으로 진행
• 선택구조(Selection) : 분기형, 조건에 따라 실행 내용, 순서 달라짐
• 반복구조(Repition) : 조건을 만족할 때까지 일정 내용 반복 실행

 

* 수열 알고리즘

 

-> 1+2+3+ ... +99+100 까지 구하기

int i=0, sum=0;
do {
 i++;
 sum+=i;
} while(i>100);
System.out.println(sum);

 

-> 1-2+3-4+5-6+ ... +99-100 구하기

 -> 스위치 변수(mode) 이용

int i=0, sum=0, mode=0;
do {
 i++;
 if(mode==0){
  sum+=i;
  mode=1;
 } else{
  sum-=i;
  mode=0;
 }
} while(i<100);

System.out.println(sum);

 -> 조건문 조건식에 MOD() 함수를 이용하여 표현할 수도 있다.

if(i%2==1){
 sum+=i;
} else{
 sum-=i;
} while(i<100);

 

* 피보나치 수열

-> 1+1+2+3+5+8+13+ ... +n

void fibonachiNumbers(int count){
 int a=1, b=1, c=0, n=2, sum=0;
 sum=a+b;
 while(true){
  c+a+b;
  sum=sum+c;
  n++;
  if(n<count){
   a=b;
   b=c;
  } else{
   System.out.println(sum);
   break;
  }
 }
}

 

* 약수구하기

-> 배열 이용

void findDivisor(int num){
 int i=0, j=0;
 int A[] = new int[100];
 while(true){
  i++;
  if(i<num){
   if(num%i == 0){
    j++;
    A[j]=i;
   }
  } else{
   System.out.println(num+" : ");
   for(int id=0; id<=j; id++){
   System.out.print(A[id]+" ");
   }
   break;
  }
 }
}
 

 

* 최대공약수, 최소공배수 구하기

-> 유클리드 호제법 이용

void getGCMnLCM(int a, int b){
 int big, small, r;
 int GCM, LCM;
 if(a>b){
  big=a;
  small=b;
 } else{
  big=b;
  small=a;
 }
 while(true){
  r=big%small;
  if(r==0){
   GCM=small;
   LCM=a*b/GCM;
   break;
  }
  big=small;
  small=r;
 }
 System.out.println("GCM : "+GCM);
 System.out.println("LCM : "+LCM);
}

 

* 진법 변환하기(10진수를 2진수로)

-> 배열 이용

void transNumber(int dec){
 int bin[] = new int[10];
 int q=0, r=0, idx=0;
 do {
  q=(int)dec/2;
  r=dec%2;
  idx++;
  bin[idx]=r;
  dec=q;
 } while(q!=0);
 
 for(int i=idx; i>0; i--){
  System.out.print(bin[i]_+" ");
 }
}  

 

* 가까운 수 구하기

-> 절댓값 함수 이용

void nearestNumber(int A[], int a){
 int min, d, n;
 min = Math.abs(A[0]-a);
 n=A[0];
 for(int i=1; i<A.length; i++){
  d=Math.abs(A[i]-a);
  if(d<num){
   num=d;
   n=A[i];
  }
 }
 System.out.println("Nearest Number is "+n);
}

 

* 선택정렬

void selectionSort(int A[]){
 int i,j;
 for(i=0; i<A.length-1; i++){
  for(j=i+1; j<A.length; j++){
   if(A[i] > A[j]){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
   }
  }
 }
}

시간복잡도 O(n^2)

 

* 버블 정렬

public void bubbleSort(int A[]){
 int i,j;
 for(i=0; i<A.length; i++){
  for(j=0; j<A.length-i-1; j++){
   if(A[j] > A[j+1]{
    int temp = A[j];
    A[j] = A[j+1];
    A[j+1] = temp;
   }
  }
 }
}

시간복잡도 O(n^2)

 

* 삽입 정렬

void insertionSort(int A[]){
 int p=0;
 for(int i=0; i<A.length; i++){
  int j=0;
  p=A[i];
  for(j=i-1; j>0; j--){
   if(A[j]>p){
    A[j+1]=A[j];
   } else{
    break;
   }
   A[j+1]=p;
  }
 }
}

시간복잡도 O(n) ~ O(n^2)

 

셀 정렬 : O(n^1.5)

합병 정렬 : O(n^logn)

퀵 정렬 : O(nlogn) ~ O(n^2)

 

정보처리기사 실기 - 5. 화면 설계(1) /스타일가이드/프로토타입