알고리즘문제해결전략2 [알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘의 정당성 증명review 도입 단위 테스트는 알고리즘에 문제가 있음을 증명할 수 있지만 없음을 증명할 수 없다. 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘 증명을 공부해야 하는 이유 : 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문. 수학적 귀납법과 반복문 불변식 수학적 귀납법 : 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법 단계 나누기 -> 첫 단계 증명 -> 귀납 증명 반복문 불변식 (loop in - variant ) : 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건 이진 탐색에서 int binsearch (const vector&A,int x){ int n =A.size(); .. 2022. 5. 22. [알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘 시간 복잡도 분석 review 알고리즘 : 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것 소스코드 != 알고리즘 명료하고 모호하지 않은 형태로 표현하기 위해 대체로 소스코드의 형태로 설명하기에 둘이 비슷해 보일 수 있지만 알고리즘은 문제를 해결하는 방법 그 자체이며 완전히 달라 보여도 같은 원리에 따라 동작한다면 같은 알고리즘을 사용한다고 할 수 있다. 한 문제를 해결하는 여러 알고리즘 중에 어떤 것을 배워야 할까? 알고리즘의 평가 기준 1. 시간 : 알고리즘의 수행 속도와 특성을 분석하는 능력을 키울 필요가 있다. 2.공간 : 알고리즘이 아무리 빠르더라도 너무 많은 메모리 공간을 요구한다면 수행 x 두 기준은 서로 상충할 때가 많다. 대회에서는 주로 속도를 중요시한다. 알고리즘의 시간 복잡도 분석 프로그램의 실행시간은 알고리.. 2022. 4. 3. 이전 1 다음