컴퓨터과학/자료구조

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다. 1. 균형 잡힌 이진 탐색 트리1-1. 이진 탐색 트리의 문제점이진 탐색 트리의 탐색 연산은 O(logN)의 시간 복잡도를 가진다.트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하므로 쉽게 판단이 가능하다.이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(N)에 가까운 시간 복잡도를 보인다.위 그림과 같이 이진 탐색 트리의 조건을 만족하지만, 노드 수에 가까운 높이를 형성하게 되었다.위 그림과 같이 저장 순서만 조금 바꿨더니 루트 노드를 기준으로 어느 정도 균형이 잡혔고, 트리의 높이도 반으로 줄었다. 이렇듯 앞서 구현한 이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보이는데, 이것이 이진..

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다. 1. 탐색의 이해와 보간 탐색1-1. 탐색의 이해탐색이란 데이터를 찾는 방법이다.굳이 따지자면 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다.효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안된다.그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다.이때 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다.따라서 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여 있다. 1-2. 보간 탐색지금까지 크게 두 가지 탐색 알고리즘을 학습했다.순차 탐색 : 정렬되지 않은 대상을 기반으로 하는 탐색이진 탐색 : 정렬된 대상을 기반으로 하는 탐색이진 탐색은 중앙에 위치한 데이터를 탐색한 후, 이를 기준..

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다. 1. 함수의 재귀적 호출의 이해📌 재귀 함수 (Recursion)함수 내에서 자기 자신을 다시 호출하는 함수재귀 함수를 실행하는 중간에 다시 재귀 함수를 호출하면, 재귀 함수의 복사본을 하나 더 만들어서 실행하게 된다.하지만 '재귀의 탈출조건'이 없다면 무한히 복제하기 때문에 '재귀의 탈출조건'을 정의해야 한다.2. 재귀의 활용2-1. 팩토리얼 함수 (Factorial)// RecursiveFactorial.c#include int Factorial(int n){ if(n == 0) return 1; else return n * Factorial(n-1);}int main(void){ printf("1! = %d..

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다. 1. 자료구조에 대한 기본적인 이해📌 자료구조데이터의 표현 및 저장 방법 ✍🏻 자료구조의 분류선형 자료구조 : 자료를 표현하고 저장하는 방식이 나란히 또는 일렬로 저장하는 방식비선형 자료구조 : 자료를 표현하고 저장하는 방식이 나란하지 않게 저장하는 방식 📌 알고리즘표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법자료구조에 따라 알고리즘을 달라진다.알고리즘은 자료구조에 의존적이다. 2. 알고리즘의 성능 분석 방법2-1. 시간 복잡도와 공간 복잡도✍🏻 알고리즘을 평가하는 두 가지 요소어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느리냐어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐즉, 하나는 속도에 ..