[CS 지식 - 알고리즘] 알고리즘이란?

 

 

1. 알고리즘이란?

• 사전적 의미 : 어떤 문제를 해결하기 위한 절차나 방법
• 프로그래밍에서 의미 : 어떤 문제를 컴퓨터를 사용해서 해결하기 위한 절차나 방법

 

2. 알고리즘 조건

• 입력 : 알고리즘은 0 또는 그 이상의 외부에 제공된 자료 존재
• 출력 : 알고리즘은 최소 1개 이상의 결과가 있어야함
• 명확성 : 알고리즘의 각 단계는 애매함 없는 명확한 과정으로 구성되어야함
• 유한성 :  알고리즘은 유한한 수의 단계를 수행한 후 문제가 해결되고 종료되어야 함
• 효율성 : 알고리즘의 모든 연산은 명백하게 실행 할 수 있음을 검증 할 수 있어야 함

 

3. 알고리즘의 효율성

• 컴퓨터를 사용해 주어진 조건에 맞게 효율적으로 문제를 해결하는 절차와 방법을 우선
  → 알고리즘의 효율성은 해당 알고리즘이 적용될 조건이 어떠하냐에 따라 달라짐
       (어떤 좋은 정렬이라고 하더라도 모든 경우에 반드시 그렇지 않음을 의미)
  ex) 3개의 문자열을 반복해서 출력 
         1. 3개의 printf()를 사용해서 출력
             → printf()함수 안에서 사용하는 연산과 메모리를 제외하고 메모리에 할당해야 할 변수나 실행해야할 연산x
                   단, 반복해서 출력해야 할 문자열이 늘어날 수록 printf()함수를 추가로 작성해야 함
         2. for문을 사용해 반복해서 출력
            → 1번과 비교했을때, 코드 행이 적고, 지역변수 i와 print()함수 3개 안에 있는 문자열을 메모리에 할당
                 문자열이 늘어나도 for문의 종결 조건만 변경하면 됨
                 코드 간결
  
  

1. 시간의 효율성
: 모든 알고리즘에서 가장 중요하게 생각하는 요소
   컴퓨터에서 실행되는 프로그램이라면 주어진 조건에 맞춰 문제를 해결하는데 무한대의 시간을 사용x

int main(){
	int i, input;
	int data[1000];

	for (i = 0; i < 1000; i++){		
    	data[i] = i;
	}

	printf("찾으실 값을 입력하세요 : ");
	scanf_s("%d", &input);

	for (i = 0; i < 1000; i++){
		if (input == data[i]){
			printf("찾으려고 하는 값이 배열 data의 %d번째 있습니다.\n", i);
			break;
		}
	}

	return 0;
}

• 0부터 999까지 데이터를 차례로 검색
  →원하는 데이터가 큰 수 일수록 비교를 많이 해야함

int main(){
	int i, input;
	int data[1000];
	int min = 0, max = 1000;
	int count = 0;

	for (i = 0; i < 1000; i++){
		data[i] = i;
	}

	printf("찾으실 값을 입력하세요 : ");
	scanf_s("%d", &input);

	i = (max + min) / 2;
	while (true){
		if (input == data[i]){
			printf("찾으려고 하는 값이 배열 data의 %d번째 있습니다.(카운트 : %d)\n", i, count+1);
			break;
		}else if (input > data[i]){
			min = data[i];
		}else{
			max = data[i];
		}

		i = (max + min) / 2;

		count++;
	}

	return 0;
}

• 중간값을 이용한 비교
  → 사용자가 입력한 값과 배열의 중간값을 비교해서 배열을 이등분하여 배열의 중간값보다 작으면 앞부분의
      중간값과 비교, 배열의 중간값과보다 크면 뒷부분과 비교
      → 최악의 경우도, 10번이내로 원하는 데이터 찾기 가능

2. 공간의 효율성

• 컴퓨터에서 사용하는 메모리와 관계, 무한대의 메모리 사용x
  → 메모리를 효율적으로 관리하고 사용하는 것이 중요

void main(){
	int i;
	int data[1000];

	for (i = 0; i<10; i++){
		data[i] = i;
	}

}

• 10개의 자료를 저장하기 위해 배열 1000개 분량의 메모리 공간을 선언
  → 불필요한 메모리공간 낭비

int add(void);
int subtract(void);

// 지역변수로 사용할 변수를 전역 변수로 선언 
int a, b;
int ret;

int add(void){
//전역변수를 사용하여 메모리가 낭비됨
	return a + b;
}

int subtract(void){
	return a - b;
}

int main(){
	a = 100;
	b = 90;

	ret = add();
	printf("%d\n", ret);

	ret = subtract();
	printf("%d\n", ret);
}

• 변수를 모두 전역변수로 사용
  → 전역변수는 프로그램의 실행시점부터 메모리 공간을 계속 유지하므로 비효율적
  → 전역변수의 사용을 최소화해야 함

 

3. 코드의 효율성

• 프로그래머 입장에서의 효율성
  : 가독성이 좋은 코드
    유지보수가 쉬운 코드
    이해하기 쉬운 코드
• 컴퓨터 입장에서의 효율성
  : 컴파일러와 하드웨어에 최적화 된 코드
    → 프로그래머에게 효율적인 알고리즘이더라도 컴퓨터입장에서는 효율적인 알고리즘이 아닐 수 있음
  ex) 재귀 호출
        프로그래머의 입장 :  코드 간결, 이해도 높음
        컴퓨터 입장 : 재귀 호출을 위한 부가 작업 필요 → 오버헤드 가능성 높음

 

 

알고리즘 예상질문)

• 동적 계획법에 대해 설명
• 동적 계획법이 갖는 2가지 조건은?
• 버블정렬에 대해 설명
• 선택정렬에 대해 설명
• 삽입정렬에 대해 설명
• 힙 정렬데 대해 설명
• 병합 정렬에 대해 설명
• 퀵 정렬에 대해 설명
• BIg-O표기법의 시간 복잡도 크기 순서
• 허프만 코딩 설명
• 재귀 알고리즘 설명
• 피보나치 수열의 n번째 값을 구하는 메소드에 대해 재귀와 반복문 코딩
• 팩토리얼 n번째 값을 구하는 메소드에 대해 각각 재귀와 반복문을 코딩
• 재귀와 반복의 차이, DP의 장점에 대해 설명
• 피보나치 수열을 구현할 수 있는 알고리즘 3가지를 언급하고 각 시간복잡도 비교

 

참고)

https://dev-coco.tistory.com/160

신입 개발자 기술면접 질문 정리 - 알고리즘

https://kangsu-2ji.tistory.com/158

[ CS 기술면접 ] 알고리즘 예상질문 모음 !

https://cocoon1787.tistory.com/5

[ALGORITHM] 알고리즘의 정의