회문 검사 회문(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:..

스택(Stack): 한쪽 끝에서만 데이터를 삽입하거나 삭제하는 자료구조 데이터 삽입 연산: push 데이터 삭제 연산: pop 데이터 읽기 연산: top LIFO (Last-In First-Out): 마지막에 들어온 데이터가 먼저 삭제되는 방식 Stack을 코드로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Stack: def __init__(self): self._items = [] def __len__(self): #스택길이 return len(self._items) def __str__(self): return str(self._items) def is_empty(self): return self._items ..

이중연결리스트: 이중연결리스트(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..

자료구조수업에서 시에르핀스키 삼각형에 대한 과제가 있어서 한번 코딩을 해보았습니다. 시에르핀스키 삼각형(Sierpinski triangle)은 프랙탈 도형입니다. 시에르핀스키 삼각형은 다음과 같은 방법을 통해 얻을 수 있다. 정삼각형 하나에서 시작한다. 정삼각형의 세 변의 중점을 이으면 원래의 정삼각형 안에 작은 정삼각형이 만들어진다. 이 작은 정삼각형을 제거한다. 남은 정삼각형들에 대해서도 2.를 실행한다. 3.을 무한히 반복한다. 이것을 반복하면 다음과 같은 도형이 얻어진다.(무한반복) 아래는 Sierpinski Triangles recursively arrow에대한 코드입니다. Sierpinski Triangles을 recursively하게 tuple을 사용해서 그려보겠습니다. 1 2 3 4 5 6..

하노이탑에 대한 Python 코드입니다. 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다. peg1에 있는 디스크를 peg3에 모두 옮기려면 어떻게 해야할까요?? 1. peg3에 6번 디스크가 가기위해서는 peg2에 1~5번 디스크가 있어야합니다. 2. 마찬가지로 peg2에 5번 디스크가 있기 위해서는 peg3에 1~4번 ..

단순연결리스트(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)..

알고리즘의 성능을 나타낼때 정확성, 복잡도, 효율성이 대상이 됩니다. 알고리즘의 복잡도란 알고리즘의 성능을 나타내는 지표입니다. 알고리즘의 수행시간 -> 시간 복잡도 (time complexity) 알고리즘의 사용공간 ->공간 복잡도 (space complexity) 주로 시간복잡도로 알고리즘의 성능을 평가합니다. 시간 복잡도 측정 방법 1.Big-Oh O(n)은 수행시간 함수 입니다. f(n) = 2n^2 + 3n + 5이면, 양의 상수 c 값을 최고 차항의 계수인 2보다 큰 4를 택하고 g(n) = n^2으로 정하면, 3보다 큰 모든n에 대해 2n^2 + 3n + 5 < 4n^2이 성립, 즉, f(n) = O(n^2) f(n)의 수행시간은 O(n^2)라는 것입니다. 흔히 수행시간에서 계수는 생략가능합..

분수에 관한 기본연산과 비교연산에 대한 코드입니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354def gcd(m, n): #최대공약수를 구하는 함수입니다. while n: m, n = n, m % n return m class Fraction: #Fraction class를 만들어줍니다. def __init__(self, num, denom): #constructor입니다 self._num = num #num은 분자값 self._denom = denom #denom은 분모값 입니다. def __repr__(self): #string으로 출력하기위한 함수 return str..