The Role of Algorithms in Computing

알고리즘이란?

• 입력을 가지고 출력을 생산하는 논리적인 계산 절차
• 입력을 출력으로 변환하는 계산적인 단계의 절차
• 잘 명시된 계산적인 문제를 해결하는 도구

입력이란 주어진 문제의 인스턴스 즉, 처리대상을 뜻한다.

출력이란 주어진 문제의 해결방법을 뜻한다.

 

좋은 알고리즘(정답인 알고리즘?)에는 몇가지 조건이 존재한다.

• 모든 입력 인스턴스에 대하여 알맞은 출력과 함께 알고리즘이 멈춰야한다.
• 따라야할 계산 절차를 정확하게 설명해야한다.

좋은 알고리즘이란 당연히 주어진 문제를 해결할 수 있는 알고리즘이고, 멈추지 않거나 목표한 답과는 다른 답을 가지고 멈추는 알고리즘은 틀린 알고리즘이다.

---

문제를 해결하는 방법 

데이터 구조(data structures)를 사용하여 효율적인 알고리즘을 구현할 수 있다.

데이터 구조란 데이터를 저장하고 관리하는 방식이며, 주로 데이터를 저장, 조작, 검색하는데 쓰인다.

e.g. 배열, 스택, 큐 등등

 

효율적인 알고리즘이란 문제를 해결하는데 걸리는 시간이 짧은 알고리즘을 뜻한다. 보통 어떤 알고리즘이 다항 시간(polynomial time)에 문제를 해결할 때 효율적인 알고리즘이라고 한다.

• P-problem(polynomial-problem): 입력 크기 n에 대하여 다항식 시간 $n^k$ 내에 답을 찾을 수 있는 문제 즉, 알고리즘이 수행한 단계가 n에 대한 어떤 다항식을 항상 넘지 않는 문제를 말한다.
• NP-problem(nondeterministic polynomial-problem): 비결정적 다항 시간 문제이다. 어떤 해답이 주어졌을 때, 그 해답이 맞는지 확인하는 데 걸리는 시간이 다항식 시간 내에 가능하면 NP문제라고 한다. 해답을 검증하는 과정이 다항식 시간 내에 가능할 뿐, 해답을 찾는 알고리즘이 다항식 시간 내에 존재하는지에 대한 여부는 결정되지 않은 것이다.

P-NP 문제는 밀레니엄 7대 난제 중 하나이며, 나무위키를 읽다보면 시간가는 줄 모르니 조심하길 바란다.

 

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **