Today I Learned🧤

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다. 연결 리스트 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. 삽입과 삭제가 O(1)이 걸리며, 탐색에는 O(n)이 걸린다. 위 그림과 같이 prev 포인터와 next 포인터로 앞 뒤의 노드를 연결시킨 것이 연결 리스트이다. 참고로, 맨 앞에 있는 노드를 head라 한다. 싱글 연결 리스트 : next 포인터만 가지며, 한쪽 방향으로만 이동이 가능하다. 이중 연결 리스트 : next 포인터와 prev 포인터를 가지며, 양방향으로 이동이 가능하다. 원형 이중 연결 리스트 : 이중 연결리스트와 동일하지만, 마지막의 노드의 next 헤더가 head 노드를 가리킨다. 배열 배열은 같은 타입의 변수..

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다. 복잡도 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 시간 복잡도(time complexity) 시간 복잡도란 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 가리킨다. 어떤 알고리즘의 로직이 '얼마나 오래' 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다. 예를 들어, 입력 크기 n에 대한 알고리즘에 필요한 시간이 10n^2+n이라고 하면 빅오 표기법으로는 O(n^2)가 된다. '가장 영향을 많이 끼치는 항'의 상수 인자를 빼고 나머지 항을 없애서 표현한 것이다. 다른 항들도 신경 쓰일 수 있지만 증가 속도를 고려한다면 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 ..