쭈링이.log 쭈링이.log

재귀함수의 팩토리얼(Factorial) 먼저 재귀험수의 팩토리얼을 설명하려고한다.팩토리얼의 수학적인 함수를 보면 다음과 같이 나타내어진다. 우리가 수학에서 쓸때 팩토리얼을 !를 사용하여 쓰곤한다. 이의 원리는 3! 1부터 자기자신까지의 정수들을 곱하여 나타낸다. 즉,3! = 3 * 2 * 1 의 형태로 나타내어 3! = 6이 된다. 하지만 우리는 수학을 공부하는게 아니라 자료구조를 공부하기때문에이러한 원리를 재귀 함수를 사용하여 나타낼것이다. 먼저 일단 위에있는 사진을 살펴보면 우리가 달리 생각할수도 있을것이다. 이렇게도 볼수 있지않을까?즉 5! = 5 * 4! 이것으로 볼수도 있을것이다.이렇게 식을 바꾸어 보면 재귀함수로 표현할 수 있을것이다.그렇다면 이것을 다시 수학적인 함수로 바꾸면 이렇게 함수로 ..

재귀 함수(Recursion) c언어를 기반으로 말을하면 재귀 함수는 자기자신을 호출하는 함수이다.즉, 함수 선언안에 자기자신을 또 선언하는 문장이 들어있는것. ex)void Recursive (void) {printf("Recursion call! \n");Recursive();} 이러한 것같이 자기 자신을 다시 호출하는 함수가 재귀함수이다.자기자신을 호출하는데 무슨 필요가 있겠는가.. 라고 생각들기도 하지만함수에선 재귀적 성향을 가진 함수가 꽤 많이있다. 그럼 재귀 함수의 호출원리를 알아보자.재귀함수의 호출은 자기자신의 함수로 다시 재진입하는것이 아니라자기자신의 함수를 복사하여 붙여넣는것이다. 즉, 이런식으로 자기함수를 복사하여 호출하는것이다.재귀 함수는 팩토리얼, 피보나치 수열, 하노이타워, 이진 ..

빅-오 표기법(Big-Oh Notation) 빅오 표기법이란 함수 T(n)인 시간복잡도에서 가장 영향력이 큰 부분이 어디인지 따져보는것이다.영향력이 큰 부분이 어디인지를 찾기위해선 다음과 같은 예를 들것이다. 이러한 식이 있을때 이식에 대한 근사치(approximation)의 식을 구할 수 있을것이다. 위의 함수에 대한 근사치식을 구성해보면 이러한 식으로 나타낼 수 있을것이다.+1쯤이야 가볍게 넘어가도 좋다 생각할수 있지만 여기서 더 간략화 시켜도 프로그램에 무리가 없을까?조금더 간략화 시켜보겠다. 이렇게 간략화 시킬 수 있을것이다.하지만 이런 상황에서 2n을 빼버려도 괜찮은지 의문의 생각이 들 수도 있을것이다. 그렇다면 위의 식에서 n의 갯수가 늘어날수록 n^2이 차지하는 비율을 확인해 보자. 이러한 ..

이진 탐색(Binary Search) 알고리즘과 시간 복잡도 이진 탐색(Binary Search) 순차탐색이 있으면 이진 탐색도 있다. 이진탐색이란 우선 이진탐색을 하기위해서는 반드시 정렬이 되어있어야한다. 이진탐색은 정렬된 데이터가 아니면 적용을 할 수 없기 때문이다. 우선 이진 탐색은 정렬된 데이터의 집합을 이분화 하면서 탐색하는것이다. 이진 탐색의 원리는 다음과 같다. [2] [4] [5] [7] [10] [20] [23] [29] [32] arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] 이렇게 정렬된배열이 있다고 가정한다. 배열의 이름을 arr이라 가정하고 이 배열을 대상으로 원하는값이 5라면 5를 찾기위한 이진트리의 원리는 이렇하다..

순차 탐색(Linear Search) 알고리즘의 시간 복잡도 시간복잡도의 2가지중 한가지가 바로 순차탐색 알고리즘이다.순차 탐색 알고리즘은 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘이기에순차 탐색 알고리즘이라고 부른다. ex) for(i=0 ; i

자료구조 (Data Structure) 자료구조란 컴퓨터에서 처리할 자료들을 효율적으로 관리하고 구조한것이다.자료구조는 데이터를 표현한다는데 표현한다는뜻에는 저장의 의미도 담겨져있다.이렇게 자료들을 표현하면 그것들을 처리하는것을 알고리즘 이라고 한다.그래서 알고리즘은 자료구조에 의존적이기도하다 자료구조에는 다음과 같은 구조들이 있다 자료구조를 크게 나뉘어보면 선형구조와 비선형구조, 파일구조와 단순구조로 나눌수있다. 자료구조에서 배울내용들은 선형구조와 비선형구조를 주로 다루기도한다. 또한 자료구조는 수학과 많은 연관을 나뉘어지며 특히 이수식을 잘 알아야한다. x축이 데이터를 의미하고 y축이 연산의 횟수를 의미한다면 과연 두 식중에 어떤게 더 효율적인가 아무래도 데이터가 많을수록 연산횟수가 적으면 좋은 프로..