괄호 매칭 1.왼쪽 괄호는 스택에 push 2.오른쪽 괄호를 읽으면 pop 수행 3.pop된 왼쪽 괄호와 바로 읽었던 오른쪽 괄호가 다른 종류이면 에러 처리, 같은 종류이면 다음 괄호를 읽음 4.모든 괄호를 읽은 뒤 에러가 없고 스택이 empty이면, 괄호들이 정상적으로 사용된 것 5.만일 모든 괄호를 처리한 후 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것이므로 에러 처리 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def is_matched(expr): lefty = '({[' righty = ')}]' S = Stack() #스택구현은 이전 글에 있습니다. for c in expr: if c in lefty: S.push(c) elif c in righty:..

이중연결리스트: 이중연결리스트(doubly linked lists)는 각 노드가 앞과 뒤를 가리치는 두 개의 레퍼런스를 가지는 연결리스트 단순연결리스트는 삽입이나 삭제할 때 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 노드들을 탐색할 수 없음 이중연결리스트는 단순연결리스트의 이러한 단점을 보완하나, 각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가짐 간단하게 이중연결리스트를 구현해보면 파이썬 코드 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5..

단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조 동적 메모리 할당을 받아 노드(node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킴 연결리스트에서는 삽입/삭제 시 항목들의 이동이 필요 없음 연결리스트에서는 자료를 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색 (Sequential Search)을 해야함 단순연결리스트에서 head는 맨 처음 노드라고 생각하면 됩니다. head를 통해서 노드로 순차적으로 탐색 그럼 코드를 통해 확인해볼게요 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

List 자료구조에 대한 내용입니다. 자료구조로서의 리스트는 자료들의 덩어리입니다. 그리고 자료들 사이에 순서가 존재합니다 이러한 순서에 접근하기 위해서 인덱싱을 사용합니다. 리스트연산 1.삽입 append()를 사용해서 리스트에 값을 추가할 수 있습니다. 2.삭제 pop()을 사용해서 삭제가 가능합니다. 시간복잡도 삽입, 삭제 시에는 O(n)의 시간복잡도를 가집니다. 그렇다면 어떻게 시간복잡도를 줄여서 성능을 올릴 수 있을까요? c언어에서는 충분한 배열의 크기를 선언해서 사용합니다. 반면 파이썬은 삽입,삭제하면서 리스트의 메모리공간이 변합니다. 그렇다면 어떻게 메모리를 변화시킬까요? 1. 삽입할때마다 메모리를 일정한 크기씩 확장하는 방법 메모리가 부족할때마다 2씩 메모리를 확장. k = n/c T(n)..