알고리즘(Algorithm)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

알고리즘

정해진 입력을 받아 변환하고 일련의 명령을 수행하여 결과를 출력하는 솔루션

 

효율적인 알고리즘

연산 횟수를 입력 크기 N에 대한 다항식으로 나타낼 수 있다면 효율적이다.

 

 

문제의 종류

• Class P (Polynomial Time, 다항 시간): 복잡도를 다항식으로 나타낼 수 있는 문제
• Class NP (Non-Deterministic Polynomial Time, 비결정적 다항 시간): 다항 시간 내에 해결할 수는 있지만 정해진 다항식이 존재하지 않는 문제
• Class EXPTIME (Exponential Time, 지수 시간): 복잡도를 지수 함수 형태로 나타낼 수 있는 문제
• Class PSPACE (Polynomial Space, 다항 공간): 다항식 크기의 공간이 필요한 문제