환한 개발자

스택 스택은 배열과 마찬가지로 데이터를 저장하고, 데이터를 꺼내기 위해 사용하는 자료구조 중 하나이다. 스택은 이와 다르게 최근에 저장한 데이터만 꺼내올 수 있다. 스택이라는 이름 뜻 그대로, 데이터를 차곡차곡 쌓아 저장하고, 데이터를 꺼낼 땐 위에 쌓아 넣은 것부터 하나씩 추출하는 자료구조이다. 이러한 스택의 특성을 가리켜 후입선출(Last In, First Out) 특성을 가진다고 한다. 스택의 시간복잡도 push push 함수는 스택의 맨 위에 데이터를 삽입한다. 즉, 스택 내부에 있는 다른 데이터에 접근하지 않기 때문에, 어떤 데이터가 들어오더라도 시간복잡도는 항상 같다.이 경우, Big-O 표기법에 따라 O(1)로 표기한다. pop pop 함수도 push함수와 마찬가지다. 다른 데이터에 접근할 ..

복잡도 복잡도는 문제 해결에 사용되는 연산의 횟수를 의미하는 시간복잡도와 프로그램이 종료되기까지 필요한 자원 공간의 양을 의미하는 공간 복잡도로 나뉜다. 복잡도는 알고리즘에 데이터가 주어질 때 연산 시간, 혹은 연산에 사용되는 공간의 크기를 객관적으로 비교할 수 있는 기준을 제공하기 때문에, 문제를 해결하는 알고리즘을 평가하는 데에 사용된다. 공간 복잡도 공간 복잡도란 프로그램을 실행시킨 후 완료하기까지 필요로 하는 공간의 크기를 의미한다.이때 필요한 공간은 고정 공간과 가변 공간으로 나뉜다. 고정 공간 : 코드가 저장되고, 단순한 변수와 상수가 저장되는 공간. 알고리즘과 무관하다. 가변 공간 : 코드가 실행되는 도중에 동적으로 필요한 공간, 알고리즘과 연관된 공간 Big-O 표기법을 사용해 입력된 데이..

배열 특징 같은 타입의 변수들로 구성 크기가 정해져 있음 인접한 메모리에 위치한 데이터를 모아놓은 집합, 따라서 랜덤 접근(direct access or random access)이 가능 탐색에 O(1), 삽입과 삭제에 O(n)의 시간복잡도를 가짐 메모리 재사용 불가 - 초기 사이즈 만큼 할당됨, 데이터 없어도 메모리 차지 연결 리스트 특징 데이터를 감싼 노드를 포인터로 연결, 따라서 랜덤 접근이 불가능 크기가 가변적 탐색에 O(n), 삽입과 삭제가 O(1)의 시간복잡도를 가짐 메모리 재사용 가능 - 삭제 시 해당 노드의 참조가 사라지고 GC에 의해 사용가능한 메모리로 전환됨.