[Algorithm] 알고리즘 기초

알고리즘이란 ?

알고리즘이란 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합이다.

좋은 알고리즘을 만들어내고 문제를 잘 해결하기 위해서는 구현력, 이론 및 지식, 응용력이 필요하다.

---

알고리즘의 조건 ?

알고리즘의 조건은 크게 5가지가 존재한다.

 

1. 정밀성 : 명확한 작업 단계를 가져야 한다.
2. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
3. 입출력 : 입력을 받아들이고, 답으로 출력 가능해야 한다.
4. 유한성 : 특정 수의 작업 이후 정지해야 한다.
5. 일반성 : 정의된 입력들에 적용이 가능해야 한다.

---

알고리즘의 성능 ?

알고리즘의 성능을 평가하는데 크게 두 가지의 기준이 존재한다.

 

1. 시간복잡도 : 주어진 문제를 해결하는 데 걸리는 시간을 측정한 것
2. 공간복잡도 : 주어진 문제를 해결하는 데 사용되는 공간의 크기를 측정한 것

 

시간복잡도와 공간복잡도는 서로 Trade-off 관계이다.

알고리즘을 작성할 때 두 가지의 복잡도를 적절하게 사용하여 문제를 해결하자.

---

알고리즘의 접근 ?

모든 문제는 완전탐색을 통해 해결이 가능하다.

하지만, 문제에서 주어진 조건에 맞는 알고리즘 작성이 필요하다. 

그렇기 때문에 다음의 단계를 따라 접근하자.

 

1. 알고리즘의 접근은 완전탐색으로 시작한다.
2. 주어진 조건을 확인하여 적절한 알고리즘을 생각한다.
3. 시간을 초과한다면 Time-cutting 방법을 찾아본다.
4. 계속 시간초과가 나온다면 다른 알고리즘을 생각한다.
5. 모두 만족한다면 주어진 테스트케이스에 넣어보고 코드를 작성한다.

---

주의 사항 ?

코드를 작성하면서 항상 Overflow에 대한 문제를 주의하여야 한다.

 

다음의 코드에서 Overflow가 발생하는 코드를 골라보자.

 

for(char c=0; c<128; c++) {
	System.out.println("Hello");
}

 

int result = 1;
for(int i=1; i<=50; i++) {
	result = result * i % 61;
}

 

int result = 10;
int mod = 1000000007;
for(int i=0; i<10; i++) {
	result = 10 * result % mod;
}

: 1번, 3번 Overflow 발생

---

요약

• 알고리즘은 구현력, 이론 및 지식, 응용력을 필요로 한다.
• 알고리즘의 성능 평가의 기준이 되는 두 복잡도는 Trade-off 관계이다.
• 모든 문제는 완전탐색으로 해결이 가능하다.
• Overflow를 항상 주의하자.