누워서 떡먹기 코딩

싱글 링크드 리스트(단순 연결 리스트) 연산들의 시간 복잡도를 알아 보자. 접근 시간 복잡도 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 가면 된다 마지막 노드에 접근하려면 head에서 다음 노드로 n-1번 가야된다. 최악의 경우 시간 복잡도 : O(n) 탐색 시간 복잡도 배열을 탐색할 때와 같은 방법으로 구한다. 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 데이터를 찾는다. 이를 선형 탐색이라고 한다. 링크드 리스트안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막 노드에 있는 최악의 경우 n개의 노드를 다 봐야한다. 최악의 경우 시간 복잡도 : O(n) 삽입 / 삭제 시간 복잡도 삽입, 삭제는 그냥 삽입, 삭제할 인덱스의 주변 노드들에 연결된 레퍼런스만..

배열 접근 파이썬의 list는 C언어의 배열을 따서 만들었다 차이점이 있다면 C배열은 1. 크기가 고정 2. 같은 타입의 데이터만 담을 수 있다. C언어의 배열은 미리 순서적이고 연속적인 메모리 칸을 쓴다고 예약하고 값을 넣는다 Python의 list는 레퍼런스가 저장되어있고 값을 저장한다기보다는 가리킨다는 의미라서 값이 연속적일 수도 있고 연속적이지 않을 수 도 있다. 배열 탐색 배열 접근 연산 : O(1) 배열 탐색 연산 : O(n) 정적, 동적 배열 정적 배열 : 크기 고정 (요소 수 제한) 동적 배열 : 크기 변함 (요소 계속 추가 가능) 일반적으로 배열은 정적 배열이다. 동적배열은 정적 배열처럼 일정한 메모리를 확보한 후 값을 집어넣는 건데 메모리가 꽉 차면 늘리는 식으로 정적 배열의 크기를 상..