나의 지식 보관소

재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다. 종료 조건을 만족할 때까지 자기 자신을 호출하면서 주어진 작업을 수행한다. 팩토리얼을 구하는 코드로 예를 들겠다. #include int main(void) { printf("\b\b= %d", factorial(5)); return 0; } int factorial(int value) { printf("%d * ", value); if (value

빅 오 표기법이란 알고리즘의 효율성을 표기해주는 표기법, 데이터의 수 n에 따른 연산 횟수를 구하는 함수 T(n)에서 가장 영향이 부분을 따지는 것, 데이터의 수 n의 증가에 따른 연산횟수의 증가 형태를 나타내는 표기법이다. 예를 들자면 T(n) = 5n^3+3n+2의 빅오는 n^3이다. 이는 n이 커질수록 n^3가 차지하는 비율이 커지므로 T(n)의 변화 정도가 n^3의 형태를 띠므로 그렇다. 위의 말을 간단히 정리하면, T(n)이 다항식으로 표현 된 경우, 최고차 항의 차수가 빅 오가 된다. 예를 들어 T(n) = 5n^3+3n+2은 O(n^3)이 된다. 위 예시에서 5n^3은 n^3이 됐는데, 최고차항의 계수는 빅오에서 중요치 않다, 왜냐하면 5n^3이나 n^3이나 n이 증가할수록 값이 증가하는 추..

이진 탐색 알고리즘을 사용하기 위해서는 배열에 저장된 데이터가 정렬되어있어야 한다. 다시 말해서 정렬되지 않은 배열에는 이진 탐색 알고리즘을 사용할 수 없다. 이진 탐색은 탐색의 범위를 반복해서 절반씩 줄이는 알고리즘이다. 배열 { 1,3,5,6,7,9,11,13,15,19 }에서 3을 찾는 과정은 다음과 같다. 첫 번째 시도 1 3 5 6 7 9 11 13 15 19 arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9] arr[10] 1. 배열 인덱스의 시작과 끝을( 0과 10 ) 더해서 2로 나눈다. 2. 0과 10을 더해서 나눈 결과 5를 인덱스 값으로 해서 저장된 값이 3인지 확인한다. 두 번째 시도 1. arr[5]에 저장된 값이 3이 ..

알고리즘의 성능을 평가하기 위해서 시간 복잡도와 공간 복잡도라는 개념이 사용된다. 시간 복잡도는 속도에 관한 것이고, 공간 복잡도는 메모리 사용량에 관한 것이다. 하지만 알고리즘의 속도를 재기란 매우 힘든 일이다. 컴퓨터의 연산 속도에 따라 다르고, 같은 컴퓨터에서 잰다 하더라도 시간은 다르게 나오게 된다. 그래서 알고리즘의 속도를 재기 위해서는 연산 횟수를 세고, 처리할 데이터의 수 n에 대한 연산 횟수를 계산하는 함수 T(n)을 만든다. 함수 T(n)을 만드는 이유는 데이터의 수가 늘어남에 따라 연산 횟수의 변화를 알아내기 위함이다. T(n)을 구성하면 아래와 같이 그래프를 통해 데이터수에 따른 연산 횟수 변화를 한눈에 볼 수 있다. 그렇다면 위와 같이 알고리즘 A와 B가 있다고 가정해보자. 데이터가..

자료구조란 컴퓨터 과학에서 효율적인 데이터의 표현 및 저장방법을 뜻한다, 이러한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 해 준다. 따라서 알고리즘과 자료구조는 밀접한 관계이며, 자료구조에 따라 사용하는 알고리즘이 달라진다.