공대생 기록장

순환 알고리즘 순환 알고리즘이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법을 말한다. 문제의 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법이다. 그러나, 예로 들어 피보나치값을 계산할 때 같은 항을 중복해서 계산했던 것처럼 함수 호출의 오버헤드 문제가 발생할 수 있다. 순환 알고리즘은 순환 호출을 하는 부분과 순환 호출을 멈추는 부분으로 이루어져 있다. 반복 알고리즘 반복 알고리즘은 for나 while을 이용하여 반복한다. 수행속도가 빠르지만, 순환적인 문제에 대해서는 프로그램 작성이 어려울 수 있다. 다양한 알고리즘 1. 팩토리얼 구하기 int factorial_recur(int n) { // 순환적 방법 if (n == 1) return 1; return ..

알고리즘의 성능 분석 방법 1. 수행 시간 측정 두 개의 알고리즘의 실제 수행 시간을 측정한다. 실제로 구현하여야 하며, 동일한 하드웨어를 사용해야 한다. 2. 알고리즘의 복잡도 분석 알고리즘이 수행하는 연산의 횟수를 측정하여 비교한다. 실제로 구현하지 않아도 된다. 연산의 수행 횟수는 입력의 개수 n에 대한 함수이다. 2-1) 시간 복잡도 전체 소요 시간 = 컴파일 시간 + 실행 시간 방법: 전역 변수 count의 사용, 단계수 테이블 방식 2-2) 공간 복잡도 공간 요구량 = 고정 공간 요구 + 가변 공간 요구 고정 공간: 프로그램 입출력의 횟수나 크기와 관계없는 공간 가변 공간: 해당 문제의 인스턴스(I)에 의존하는 공간 Asymptotic Notation(점근 표기법) 점근 표기법에는 빅오(함수의..

프로그램 = 자료구조 + 알고리즘 프로그램의 자료구조와 알고리즘으로 만들어진다. 그러므로 개발자가 효율적인 프로그램을 작성하기 위해서는 자료구조란 무엇이고 어떤 종류가 있는지, 어떻게 하면 효율적인 알고리즘을 구현할 수 있을지를 고민해야 한다. 또한, 이 둘의 설명과 더불어 크고 복잡한 문제를 단순화시킬 수 있는 데이터 추상화 개념을 숙지해야 한다. 자료 구조란? 자료구조란 자료를 효율적으로 사용하기 위해 자료의 특성에 따라 분류하고 구성, 저장, 처리하는 모든 작업이다. 알고리즘이란? 알고리즘이란 특정한 일을 수행하기 위한 명령어의 유한 집합을 말한다. 기준 입력: (외부)원인 >= 1 출력: 결과 >= 1 명백성: 모호하지 않은 명확한 명령 유한성: 한정된 수의 단계 후에는 반드시 종료 유효성: 각 ..