회문 검사 회문(Palindrome): 앞으로부터 읽으나 뒤로부터 읽으나 동일한 스트링 1. 전반부의 문자들을 스택에 push한 후, 후반부의 각 문자를 차례로 pop한 문자와 비교 2. 회문 검사하기는 주어진 스트링의 앞부분 반을 차례대로 읽어 스택에 push한 후 • 문자열의 길이가 짝수이면 뒷부분의 문자 1 개를 읽을 때마다 pop하여 읽어 들인 문자와 pop된 문자를 비교하는 과정을 반복 수행 •문자열의 길이가 홀수인 경우, 주어진 스트링의 앞부분 반을 차례로 읽어 스택에 push한 후, 중간 문자를 읽고 버린다. 3. 이후 짝수 경우와 동일하게 비교 수행 4. 만약 마지막 비교까지 두 문자가 동일하고 스택이 empty가 되면, 입력 문자열은 회문 파이썬 코드 1 2 3 4 5 6 7 8 9 10..

괄호 매칭 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)..