주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 드디어 첫 번째 자료구조를 배웁니다. 그런데 이에 앞서 '추상 자료형'이라는 용어를 먼저 소개하고자 합니다. 참고로 이 용어의 개념이 모호하다 하여 이에 대한 이해 없이 자료구조를 공부하는 경우도 있는데 이런 일은 없어야 한다고 저자는 말합니다. 문제를 하나 낼 테니 문제에서 설명하는 것이 무엇인지 맞춰보기 바랍니다. 여기에는 신용카드나 면허증과 같은 카드들을 넣고 뺄 수 있습니다. 여기에는 지폐나 동전도 넣을 수 있습니다. 이 문제의 답은 지갑입니다. 아마 다른 분들도 위 문제를 보고 지갑을 연상하는 데에 어려움은 없었을 것이라 ..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이번에 소개하는 주제는 앞서 보인 예제들과 달리 재귀적으로 접근하지 않으면 해결이 쉽지 않은 문제입니다. 하노이 타워 문제는 재귀 함수를 대표한다고도 볼 수 있습니다. 혹시 하노이 타워가 무엇인지 모른다면 짧게 검색해보고 오길 권합니다. 하노이 타워에 대한 설명은 하지 않겠습니다. 하노이 타워 문제를 막연하게 생각하면 뭔가 복잡한 논리가 필요할 듯 보입니다. 하지만 하노이 타워 문제는 매우 매우 간단한 과정을 반복할 뿐입니다. 하노이 타워 문제를 풀기 위해서는 어찌 됐든 가장 아래쪽에 위치한 가장 큰 원반을 목표지점에 옮겨야 합니다..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 재귀함수는 이해하는 것도 중요하지만 잘 정의하는 것도 중요합니다. 그리고 재귀함수를 잘 정의하기 위해서는 사고의 전환이 필요합니다.. 그래서 사고의 전환을 위한 연습을 진행하고자 합니다. 우선은 간단하게 피보나치 수열부터 시작합니다. 피보나치 수열은 재귀적은 형태를 띄는 대표적인 수열로서 다음과 같이 전개가 됩니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 쉽게 설명하자면 앞에 것 두 개를 더해서 현재의 수를 만들어가는 수열입니다. 때문에 처음 두 개의 수 0과 1이 주어진 상태에서 수를 만들어 가게..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기입니다. 무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있습니다. 그럼 이러한 재귀함수의 특징을 보이기 위해서 팩토리얼(factorial)값을 반환하는 함수를 재귀적으로 구현해 보겠습니다. //main.c 소스 파일로 저장 #include int Factorial(int num) { if (num > 2) num *= Factorial(num - 1); return num; } int main(void) { int facNum..
Chapter 01. 빅-오에 대한 수학적 접근
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 지금부터는 빅-오의 수학적 판별법에 대해 배웁니다. 그런데 이 책의 저자는 설명하기에 앞서 이 내용이 어려운 편에 속하니 이해가 쉽지 않다면 이 내용은 건너뛰어도 문제가 없다고 말합니다. 먼저 빅-오의 수학적 정의입니다. "두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ K에 대하여 f(n) ≤ Cg(n)을 만족하는 두 개의 상수 C와 K가 존재한다면, f(n)의 빅-오는 O(g(n))이다." 예를 들어 다음의 두 함수가 있다고 가정하겠습니다. n ≥ 10인 경우에 대해서, 어떤 상수 C를 g(n)에 곱했을 때, Cg..
Chapter 01. 알고리즘의 성능 분석 방법 2
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이전 시간에 이진 탐색 알고리즘의 시간복잡도를 구했습니다. 이진 탐색 알고리즘의 T(n)은 다음과 같았습니다. 그런데 계산하기에 따라서는 똑같은 이진 탐색 알고리즘에 대해 시간 복잡도가 다음과 같이 구해질 수도 있습니다. 그럼 여기에서 1을 더하는 것이 맞냐, 더하지 않는 것이 맞냐를 따지게 됩니다. 하지만 +1쯤이야 큰 의미가 없습니다. 물론 이는 1이 아니라 10000이었어도 큰 의미가 없다고 말할 수 있습니다. 그럼 여기서 이렇게 생각할지도 모릅니다. '아니, 1쯤이야 뭐 우리도 무시할 수는 있겠다 생각하는데, 그래도 1000..