Algorithms
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation. An algorithm can be described in English, pseudocode, a programming language, hardware, etc. A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.
최댓값 찾는 알고리즘은 이미 많이 배웠던 것이지
특정 단어가 몇번 나왔는지 찾는 그런 알고리즘을 해결하는 상황을 가정
Practical applications of algorithms
마땅한 알고리즘을 찾는게 어렵기는 하지만 그래도 common subprobelm에 사용된 사례가 있기 때문에 이를 참고하면 되겠다.
Efficient algorithms and hard problems
Computer scientists and programmers typically focus on using and designing efficient algorithms to solve problems. Algorithm efficiency is most commonly measured by the algorithm runtime, and an efficient algorithm is one whose runtime increases no more than polynomially with respect to the input size. However, some problems exist for which an efficient algorithm is unknown.
NP-complete problems are a set of problems for which no known efficient algorithm exists. NP-complete problems have the following characteristics:
- No efficient algorithm has been found to solve an NP-complete problem.
- No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.
- If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.
By knowing a problem is NP-complete, instead of trying to find an efficient algorithm to solve the problem, a programmer can focus on finding an algorithm to efficiently find a good, but non-optimal, solution.
- 알려진 efficient algorithm이 없는 것을
NP-complete problem이라고 한다.
NP-complete문제라는 것을 안다면, efficient algorithm을 찾는 것이 아니라 최적은 아니여도 괜찮은 good algorithm을 차증려 노력한다.
- 아직 찾지 못한 것이지 존재할 수 있다는 거야 ㅋㅎ
