2장. 문제해결절차, 완전탐색, 시간복잡도

실습_2. 문제해결절차, 완전탐색, 시간복잡도

목표

• 알고리즘 문제 해결 절차를 숙지
• 시간 복잡도를 통해 효율적인 알고리즘을 학습
• 완전탐색의 개념을 학습

문제 해결의 절차

1. 문제를 정확히 이해한다
2. 문제를 해결하는 알고리즘을 개발한다
3. 알고리즘이 문제를 해결한다는 것을 증명한다
4. 알고리즘이 제한시간내에 동작한다는 것을 보인다
5. 알고리즘을 코드로 작성한다
6. 제출

시간복잡도

• 알고리즘이 대략 몇개의 명령을 수행하는가?
• 프로그램의 수행 시간을 유추할 수 있음

Big-O 표기:

• 최악의 경우를 수행하는 명령 수

완전탐색(Brute-Force)

• 가능한 모든 경우를 시도해 보는것

• 가능한 모든 경우를 전부 고려해도 괜찮을 경우에는 단순히 모든 경우를 고려함으로써 문제를 해결한다

• 상식적인 문제 해결의 흐름

Complexity Theory

• 복잡도 이론

• 각 문제의 풀이마다 시간 복잡도가 다름

• 가장 효율적인 풀이법은 무엇인가?

• 문제 자체에도 복잡도가 존재한다
  • P class -> 다항시간문제
  • NP-Complete class -> 답을 검증하는데 다항시간이 걸림(오랜시간이 걸림)

보통 다루는 문제

• P문제