[한 권으로 끝내는 코딩테스트 with 파이썬] Chapter2. 자료 구조
·
CS 지식/자료구조
배열배열은 같은 데이터 타입들의 원소로만 이루어지지만, 파이썬은 다른 데이터 타입이어도 한 배열에 담을 수 있다. 파이썬에서는 배열의 최대길이를 지정하지 않기 때문에 데이터를 추가하고 삭제하기 편리하다. 배열 인덱스에 접근하는 데 소요되는 시간: O(1)배열의 중간에 삽입하는 데 소요되는 시간: O(n)뒷부분에 있는 데이터를 한 칸씩 shift한 후에 데이터를 넣어야하기 때문 리스트 끝에 데이터를 삽입하는 경우: O(1)장점구현이 쉽고, 참조를 위한 추가 메모리가 필요 없음연속적이므로 메모리 관리에 편리인덱스를 통한 빠른 검색단점배열의 크기를 변경할 수 없고 사용하지 않는 공간으로 인한 메모리 낭비>> 파이썬의 리스트는 이런 단점을 보완함 문자열문자들의 집합문자를 저장하고 있는 "자료형" 인덱스는 관리하..
Union Find & an Application
·
CS 지식/자료구조
Minimum Spanning Treecycle이 없지만, 전체를 커버한다.루트x, 방향성xKruskal Algorithm가장 작은 weight부터 edge를 추가한다.cycle은 없게 한다.N-1까지의 edge를 추가한다. > tree조건도 만족 Why is Kruskal Correct?cycle을 만들지 않는, 가장 작은 edge를 추가한다.↔ 만약 추가하려는 edge가 cycle을 만든다면, 추가하지 않는다.해당 edge를 추가하려면 cycle을 구성하고 있는 edge중 하나를 빼야한다.> 작은 edge부터 추가하고 있으므로 cycle 중 하나는 빼면 추가 하려는 것보다 더 작은 edge가 빠짐최단거리 아님. 모순 발생> 완벽한 증명은 아니지만 이런 아이디어로 진행된다. Union/Find or D..
Priority Queue & an Application
·
CS 지식/자료구조
Priority Queue란?일단 queue. 근데 우선순위가 존재한다.우선순위가 높은 노드부터 나오는 것한 마디로 1등만 조진다 !!Heap Structurecomplete binary tree왼쪽부터 다 채워져 있다. child 간의 순서는 없고, parent > child 의 순서만 맞춘다. 인덱스 i의 오른쪽 child : 2i인덱스 i의 왼쪽 child : 2i + 1 heap insert먼저 모양만 맞춘 상태로 insert > 가장 마지막 노드에 insert 한다.if) x 일단 x와 c를 바꾼다.x와 c의 자리를 바꾸게 되면 위와 같은 그림이 되는데, 원래 c → x와 a의 관계가 문제 하지만 상관없다! 또 비교해서 x > a라면 자리를 바꾸면 그만이다.insert solution이 위와 같..
AVL Tree
·
CS 지식/자료구조
AVL Tree Idea직관왼 / 오 무게가(개수가) 비슷하면 성능이 좋을 것이다. (log n과 n은 매우 큰 차이 ..!!)6이 root에 있는 한 해결불가 > 루트가 바뀌는건 필수적임if) 4가 루트가 되면 6의 왼쪽 child가 비어서 포인터만 이동하면 child 2개로 조정할 수 있다.  AVL Tree DefinitionL: left sub tree 높이R: right sub tree 높이> 각각의 노드는 L과 R인 두개의 label을 가진다.조건: l L-R l  > 만약 AVL Tree의 노드가 n개라면 높이는 O(lonN)이 된다.더보기l L-R l → 높이가 상대적으로 낮음 Down Sequence DefinitionLLRLRRLLRL..L과 R의 string루트에서부터의 움직임을 나타..