오뚝이개발자

linked list를 정렬하는데 추가적인 메모리를 쓰지 않고 O(nlogn)의 시간복잡도로 하기 위해선 어떻게 해야할까? 답은 merge sort를 쓰면 된다!!!! 그런데 조금 복잡한 부분이 일반적인 array의 경우 index로 분할하여 정렬하면 되는데 linked list의 경우 어떻게 나누어야 하는지이다. 이를 위해선 3개의 포인터를 쓰면 된다. 그 세 포인터를 각각 p,slow,fast라 해보자. p,slow,fast가 차례로 한 칸씩 전진하는데 p->slow->fast의 순서대로 나아간다. 이 때, fast가 None이거나 fast.next가 None이 되면 p.next를 None으로 만들어주고 p와 slow로 linked list를 분할한다. 그럼 p가 가리키는 연결리스트가 l이 되고, s..

Array란? 선형자료구조 + 모든 item 같은 자료형 + item들이 메모리 상의 countinuous하게 저장 Array의 문제점 특정 위치 insert, delete가 불편(모든 item 위치 재배치해야함) 만약 얼마나 많은 item을 저장해야 하는지 모르는 상황이면 최대한 많은 메모리를 할당해야 함(waste) Linked list란? data part + link part(다음 item의 주소 가리킴)로 구성 모든 item이 다음 item과 연결되어있는 item sequence array와 달리 메모리 상에 꼭 continuous하게 저장되지 않음(consecutive일수도 있고 아닐수도 있다) Linked list의 장단점 장점 삽입, 삭제가 array에 비해 쉽다 메모리 낭비 최소화(필요한..