- Published on
[ Algorithm ] 알고리즘 개요
- Authors
- Name
- 유사공대생
면접에서 기초 알고리즘 질문을 하는 이유
1. 기초 문제 해결 능력을 평가하기 위해서다.
주먹구구식으로라도 문제를 못 풀면 바로 탈락한다. 예를 들어, char[] 문자열을 뒤집지도 못하는 사람이 할 수 있는 일은 매우 제한적이다.
2. 응용이 가능할 정도로 기초가 잘 잡혀있는지 평가하기 위해서다.
복잡한 알고리즘은 기초 알고리즘의 확장이다. 효율적인 기초 알고리즘을 잘 알아야 복잡한 것을 주먹구구식으로라도 해결 가능하다. 그렇지 못하면 새로운 문제를 해결할 능력이 부족하다 판단한다.
즉, 기초 알고리즘을 뼛속까지 이해하는 게 제일 중요하다!
알고리즘의 올바른 학습 방식
핵심 알고리즘의 동작법을 확실히 이해하려고 노력해야 한다.
알고리즘의 정의
컴퓨터 공학에서의 알고리즘 정의
어떤 부류의 문제를 해결하는 컴퓨터로 구현 가능한 명백한 명령어들이다.
그렇다면, 위 정의에 따르면 다음 코드는 알고리즘인가?
public int add(int num1, int num2) {
return num1 + num2;
}
답은 YES
- 실제 facebook에서 두 수를 더한 코드는 알고리즘이다.
알고리즘 정의로만 판단하면, 두 수를 더하는 코드도 알고리즘이다!
흔히 알고리즘이라 부르는 것들은
사소한 코드는 보통 학계 및 실무에서 알고리즘이라 부르지 않는다. 그렇다고 해서 알고리즘인지, 아닌지를 명백하게 판단하는 기준도 없다.
하지만 알고리즘 책이나 위키피디아에 실린 것들은 확실하다!
알고리즘 공부를 해도 안 느는 프로그래머들
- 하드웨어가 어떤 연산을 지원하는지 모른다.
- 이미 존재하는 마법같은 함수만 호출해본다.
- 툭하면 언어 문법이 틀리는데 컴파일 오류를 봐도 그 문제를 못찾는다.
- 컴퓨터에 데이터가 어떻게 저장되는지 모른다.
- 힙과 스택 메모리의 차이에 대해 모른다. 등등
훌륭한 알고리즘이 갖춰야 할 자질
1. 입력과 출력이 명확히 정의되어 있어야 한다.
2. 알고리즘의 각 단계가 명확하며 모호하지 않아야 한다.
3. 유한시간 안에 결과(출력)가 나와야 한다.
4. 포팅이 어려운 컴퓨터 코드를 포함하면 안된다.
- 거의 모든 언어에 공통되는 연산만 사용해야 한다.(사칙 연산, 비트 연산, 조건문, 반복문 등)
5. 같은 문제를 푸는 다양한 방법 중에 가장 효율적이다.
알고리즘의 효율성
자원의 효율적 사용을 뜻한다.
자원(resource)
- 시간: CPU 속도 등
- 공간/용량: 메모리 사용량 등등
시간과 공간은 종종 상반관계이다.
자원을 많이 사용할수록 그 알고리즘이 복잡하다고 말함
- 시간복잡도
- 공간복잡도
- 알고리즘 복잡도를 표현하는 방법 중 하나
어떤 컴퓨터에서 돌리는지에 따라 다르기 때문이다. 예를 들어, 컴퓨터에서 1씩 증가만 지원한다고 하자. 그렇게 되면 간단히 두 수를 더하게 된다고 하더라도 연산이 달라진다. 다음 코드를 보자
public int add(int num1, int num2){
return num1 + num2;
}
이런 코드가 어떤 컴퓨터에서는 1씩 증가만 지원한다면 다음과 같이 적어야 한다.
public int add(int num1, int num2){
int sum = num1;
for (int i =0; i< num2; i++){
++sum;
}
return sum;
}
이런 방식으로 돌 게 되는데 이 알고리즘의 시간복잡도는 따라서 O(1)이 아닌 O(N)이다.
따라서, 알고리즘의 효율성 분석은 다소 추상적이다.
그래서 알고리즘 공부를 하게 될 때에는 하드웨어 차이에 신경을 쓰지 않는다. 그냥 추상적인 기계에서 알고리즘을 실행한다 가정하고, 알고리즘 자체에 집중하도록 도와준다.
이런 추상적인 기계를 랜덤 접근 기계(random-access machine, RAM-우리가 흔히 아는 RAM이 아니다.)라고 한다. 랜덤 접근 기계는 다양한 하드웨어를 일반적인 형태로 대표하는 가상의 기계이다. 그리고 다음과 같은 특징이 있다.
래지스터를 갖춘 CPU 1개
- 레지스터를 사용하는 걸 공짜라고 생각하기 때문에 변수 더하는 것에 공간이 추가적으로 할당되지 않는다고 가정한다.
정수와 부동소수점 저장 가능
- 정수와 부동소수점은 한번에 저장가능한다고 가정한다.(문자열도 char[] 에 담겨있다고 생각한다.)
메모리 간접 참조(indirection) 지원(알고만 있으면 된다.)
캐시 메모리나 가상 메모리 등은 없음
- CPU 최적화를 위한 파이프라인이 없다고 가정한다.
그래서 우리가 알고리즘을 공부할 때에는 20년에서 30년 전 기계로 알고리즘을 돌린다고 가정을 하고 공부를 한다.
주의: 알고리즘의 효율성과 실제 성능
전에 말했듯이, 실제 코드에서 실행속도는 하드웨어에 따라 매우 달라질 수 있다. 그래서 실무에서는 효율성 낮은 알고리즘이 더 빠르기도 하다.
실무 최적화의 기초는 실제 우리가 돌리고 있는 하드웨어의 성능 측정에서부터 시작한다.(이게 우리가 컴퓨터 구조를 공부해야 하는 이유)
그래서 알고이즘 공부를 통해 이론상의 성능에 대해서는 확실히 습득을 하되, 하드웨어에 따라 달라지는 부분은 추가 지식으로 늘려나가면 된다.
그런데 사실, 아까 말했던 알고리즘에 오류가 있다. 그 코드를 다시 보면
public int add(int num1, int num2){
int sum = num1;
for (int i =0; i< num2; i++){
++sum;
}
return sum;
}
어떤 오류가 있을까?
바로, num2가 음수인 경우에 오류가 생긴다. 따라서 알고리즘이 올바른지 검증이 필요하다.
알고리즘의 올바름 검증
알고리즘이 제대로 작동하는지 검증하는 것도 중요한 부분이다. 알고리즘의 검증을 학계에서는 증명을 통해 시도하기도 한다. 증명을 통해 검증하는 방법은 컴퓨터 가격이 비쌌던 시절에는 매우 유용한 방법이다. 아직도 유용한 곳이 있긴 하지만 이제 실무에서는 거의 사용을 하지 않는다.
실무에서는 버그 처리 프로세스를 따른다.(참고)
제대로 작동 안하면 효율성을 논할 가치도 없다.
아, 그래서 앞서 말한 코드는 다음과 같이 수정할 수 있다. 비효율적이나 올바른 알고리즘이다.
public static int add(int num1, int num2){
int sum = num1;
for(int i=num2; i<0; i++){
--sum;
}
for(int i=0; i<num2; ++i){
++sum;
}
return sum;
}
점근 표기법과 빅오 표기법
점근 표기법(asymptotic notation)
이 표기법은 정수론과 해석학의 방법으로, 어떤 함수가 증가하는 모습을 다른 함수와 비교한다. 알고리즘의 복잡도를 논하거나 단순화시킬 때 사용한다.
대표적인 표기법
대표적인 표기법으로는 다음과 같은 표기법이 있다.
- 대문자 O 표기법(빅오 표기법)
- 소문자 o 표기법
- 대문자 오메가 표기법
- 소문자 오메가 표기법
- 대문자 세타 표기법
컴퓨터 공학에서는 주로 빅오 표기법을 사용한다.
컴퓨터 공학에서의 빅오 표기법
컴퓨터 공학에서의 빅오 표기법은 이름에서 알 수 있듯이 대문자 O를 이용해 표기한다. 주로 알고리즘을 분류하기 위해 사용한다.
O의 의미는 'order of the function'(대략 그 함수 정도)이다. 실제로 빅오 표기법에서는 앞 계수를 계산하지 않는다.
어떤 기준으로 분류하는가?
입력 데이터가 많아짐에 따라 다음 둘이 얼마나 늘어나는지를 측정한다.
- 실행 시간(시간 복잡도): 보통 알고리즘에서 주로 신경쓰는 부분이다.
- 필요한 공간(공간 복잡도)