주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기입니다. 무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있습니다. 그럼 이러한 재귀함수의 특징을 보이기 위해서 팩토리얼(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..
Chapter 01. 알고리즘의 성능 분석 방법 1
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 그저 잘 동작하는 자료구조와 알고리즘을 찾는 것이 목적이라면 기능별로 자료구조와 알고리즘을 하나씩만 알아도 됩니다. 하지만 우리는 잘 동작하는 것은 물론이거니와 좋은 성능까지 보장받기를 원합니다. 때문에 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 합니다. 모든 경우에 있어서 항상 우월한 성능을 보이는, 만능 키와 같은 자료구조와 알고리즘은 존재하지 않기 때문입니다. 자료구조와 알고리즘을 평가하는 두 가지 요소를 다음과 같이 정리할 수 있습니다. 어떤 자료구조와 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가? 어떤 자료..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이 책은 C언어를 바탕으로 자료구조를 배웁니다. 그리고 C언어에 대한 공부가 먼저 수행되었다고 가정하고 쓰였습니다. 자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명합니다. 우리는 데이터를 저장한 경험이 있습니다. 넓은 의미에서 int형 변수도, 구조체의 정의도 자료구조에 속합니다. 뿐만 아니라 배열도 자료구조의 일종입니다. 물론 이제부터 공부하게 될 자료구조는 이렇게 단순하지 않습니다. 자료구조는 기본적으로 다음과 같이 분류할 수 있습니다. 선형구조 비선형구조 파일구조 단순구조 리스트 스택 큐 트리 그래프 순차파일 색인..
C++ 공부를 마치고, 이제 자료구조를 공부하게 되었습니다. 제가 사용하게 될 책은 다음과 같습니다. images.app.goo.gl/kNSe9hGi12AthaEc8 이미지: 윤성우의 열혈 자료구조 - YES24 Google에서 검색된 m.yes24.com 이미지 www.google.com 자료구조에 관한 책을 여럿 찾아봤습니다. 그 중에는 정말 내용이 얼마 없는 초보자용이라고 쓰여진 책도 있었고, 내용은 많으나 목차가 조금 난잡하게 정리되어 있어 거부감이 드는 책도 있었습니다. 위 책은 제가 C++을 공부하기 위해 사용했던 책의 저자가 쓴 자료구조 책입니다. C++책은 내용도 많았고, 또 설명도 되게 세세하고 친절했습니다. 그래서 이 저자에 대한 좋은 신뢰가 있는 상태였는데, 그래서 자료구조 책도 이 ..