bdfgdfg

원형 연결리스트 원형 연결리스트는 기존의 연결리스트에서 맨 마지막 노드가 첫 번째 노드를 가리키는 형태를 이루는게 원형 연결리스트. 원형 연결리스트는 꼬리(마지막노드)포인터 변수가 따로 없더라도 맨 마지막에 노드를 추가할 수 있다. 다만 헤드보단 꼬리 포인터변수를 통해 원형 연결리스트를 구현하는것이 훨씬 간단하다. 앞서 단순 연결리스트를 구현할때 변경되는것은 앞(머리) 뒤(꼬리)쪽에도 추가할 수 있게 기능을 추가하고 탐색의 경우 원형으로 계속 돌 수 있는 형태이니 다음 노드의 nullptr을 저장하지 않게만 하면 된다. 양방향 연결리스트 단순 연결리스트는 노드가 내 다음에 존재하는 노드만을 가리켰다면 양방향 연결리스트는 내 다음 노드뿐만 아니라 내 이전의 노드도 가리킨다. (노드 클래스에 포인터변수 한개..

연결리스트 1. 순차 리스트 - 배열을 기반으로 구현된 리스트 (C++에서는 std::array, std::vector등 비슷한 컨테이너가 존재) 2. 연결 리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트 (C++에서는 std::list) 리스트 자료구조는 데이터를 나란히(선형) 저장한다. 그리고 중복된 데이터의 저장을 막지않는다. (자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있다. ex)이진 탐색 트리) 우선 순차 리스트를 살펴보자. (여기서부터는 C가 아닌 C++로 구현합니다.) #pragma once template class Array final { public: Array(); ~Array(); inline size_t GetSize() const; inline siz..

재귀함수. 재귀함수는 나(함수)자신을 재 호출하는 함수를 이야기한다. void Recursive() { pritnf("Recursive Call"); Recursive(); } (위의 경우는 탈출조건이 없는 재귀함수) 재귀함수는 함수의 호출순서를 스택으로 쌓고 탈출조건이 완료되면 마지막에 호출되었던 녀석이 역순으로 종료되는 구조. 이 재귀함수는 탈출조건이 존재한다. 매개변수에 인자로 넘겨온 수가 0보다 작게되면 종료. 그림을 보면 호출의 순서와 반환의 순서는 역순이다. 재귀함수를 쓸 수 있는 간단한 예제를 본다. #include int Factorial(int num) { if(num == 1) return 1; else return num * Factorial(num - 1); } int main() ..

시간 복잡도와 공간 복잡도 앞서 자료구조를 살펴보았을 때 앞으로 배워야할 자료구조의 종류는 다양했다. 그 이유는 데이터를 표현하는 방법에서 그냥 만능키와 같은 자료구조와 알고리즘은 존재하지 않기 때문이다. 그렇기에 우리는 어떤 상황에서 자료구조/알고리즘을 선택해야하는지를 판단할 수 있어야한다. 1. 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가? 2. 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가? 이렇듯 알고리즘을 평가하는데에 크게 두 가지 요소가 존재하는데 하나는 '속도'와 관련된 이야기이며 다른 하나는 '공간'에 관한 이야기이다. 속도에 관한 아록리즘의 수행시간 분석결과를 가리켜 '시간 복잡도' 라 하고 메모리 사용량에 대한 분석결과를 가리켜 '공간 복잡도' 라 한다. ..