[자료구조 알고리즘] 순환(재귀)

순환(재귀) 순환이란? 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 예) 팩토리얼 int factorial(int n) { if( n 순환 호출을 하는 부분 } 순환 반복 프로그래밍 언어에서 되풀이하는 방법에는 반복(iteration)과 순환(recursion)의 2가지가 있다. 반복이란 for나 while등의 반복구조로 되풀이 하는 방법이다. 때로는 반복을 사용하게 되면 지나치게 복잡해지는 문제들도 존재한다. 이런 경우에는 순환이 좋은 해결책이 될 수 있다. 순환은 본질적으로 순환적(recursive)인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 기본적으로 반복과 순환은 문제 해결 능력이 같으며 많은 경우에 순환 알고리즘을 반복 버전으로, 반복..

자료구조와 알고리즘 (2)

알고리즘의 성능 분석 - 수행시간 측정방법 가장 단순하지만 가장 확실한 방법은 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 다음, 그 수행시간을 측정하는 것이다. C언어에서 수행시간을 측정하는 방법에는 다음과 같이 2가지의 방법이 있다. [방법 1] #include start = clock(); ... stop = clock(); double duration = (double)(stop - start) / CLOCKS_PER_SEC; clock() 함수는 호출 프로세스에 의하여 사용된 CPU 시간을 계산한다. clock() 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환한다. 따라서 초단위의 시간을 측정하기 위하여 (stop - start)값을 CLOCKS..

자료구조와 알고리즘 (1)

다음 글은 위 책을 공부하면서 정리한 내용이다. 1. 자료구조와 알고리즘 자료구조란? 사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이를 자료 구조(data structure)라 부른다. 컴퓨터 프로그램을 흔히 자료구조 + 알고리즘으로 이루어져 있다고한다. 알고리즘이란? 컴퓨터로 문제를 풀기 위한 단계적인 절차, 엄밀하게 이야기하면 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다. 따라서 알고리즘에는 입력은 없어도 되지만 출력은 반드시 하나이상 있어야 하고 모호한 방법으로 기술된 명령어들의 집합은 알고리즘이라 할 수 없다. 또한 실행할 수 없는 명령어(ex. 0..