Palindrome(회문)

• 앞에서부터 읽든 뒤에서부터 읽든 동일한 단어나 문장을 의미

1. 회문 여부

✍ 입력

def palindrome(pStr):
    if len(pStr) <= 1:
        return

    if pStr[0] != pStr[-1]:
        return False
    else:
        return palindrome(pStr[1:len(pStr)-1])

a = 'kayak'
a[1:len(a)-1]

💻 출력 'aya'

line11 : 2번째[1] 글자부터 뒤에서 1번째[-1]

2.

✍ 입력

strAry = ['rever', 'kayak', 'Borrow or rob', '주유소의 소유주', 
          '야 너 이번 주 주번이 너야', '뒹굴 뒹굴']

for testStr in strAry:
    print(testStr, end='--> ')
    testStr = testStr.lower().replace(' ', '')   # 영어대문자X,  공백X
    if palindrome(testStr) == True:
        print('회문입니다')
    else:
        print('회문아니오')

💻 출력 rever--> 회문아니오 kayak--> 회문아니오 Borrow or rob--> 회문아니오 주유소의 소유주--> 회문아니오 야 너 이번 주 주번이 너야--> 회문아니오 뒹굴 뒹굴--> 회문아니오

Pivonacci(피보나치)

• 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

✍ 입력

def fibonacci(n):
    if n == 0: return 0
    elif n == 1: return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print('피보나치 수 --> 0 1', end=' ')
for i in range(2, 10):
    print(fibonacci(i), end=' ')

💻 출력 피보나치 수 --> 0 1 1 2 3 5 8 13 21 34

재귀 호출(Recursion)

• 동일한 작동을 무한적으로 반복하는 알고리즘
• 자신을 다시 호출하는 것

1. 재귀 호출의 작동

✍ 입력

def openBox():
    print('종이상자를 엽니다.')
    openBox()   # 자기자신을 다시 호출

openBox()

💻 출력 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. ... 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. ...

openbox를 사용하여 끝없이 호출

2.수를 제한하여 재귀 호출

✍ 입력

count = 10

def openBox():
    global count
    print('종이상자를 엽니다.')
    count -= 1
    if count == 0:
        print('반지를 넣고 반환합니다*****')
        return

    openBox()   # 자기자신을 다시 호출
    print('종이 상자를 닫습니다.')

openBox()

💻 출력 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 종이상자를 엽니다. 반지를 넣고 반환합니다***** 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다. 종이 상자를 닫습니다.

count를 사용하여 횟수를 제한

3. 재귀호출 하지 않고 반복문으로 계산

✍ 입력

sumValue = 0

for n in range(10, 0, -1):
    sumValue += n

print('10+9+8+...+1 = ', sumValue)

💻 출력 10+9+8+...+1 = 55

• 여러 노드가 서로 연결된 자료구조
• 무방향 그래프 : 간선에 방향성이 없는 그래프
• 방향 그래프 : 화살표로 간선 방향을 표기하고, 그래프의 정점 집합이 무방향 그래프와 같음
• *가중치 그래프 :8 간선마다 가중치가 다르게 부여된 그래프
• 순화 : 그래프의 모든 정점을 한번씩 방문(깊이 우선 탐색, 너비 우선 탐색)

01. 무방향 그래프

✍ 입력

class Graph:
    def __init__(self, size) -> None:
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)] # 2차원 배열

✍ 입력

G1 = Graph(4)

for item in G1.graph:    # 세로배열
    print(item)

💻 출력 [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]

✍ 입력

# A출발
# G1.graph[0][1] = 1 # (A, A)
G1.graph[0][1] = 1    # (A, B) 간선(edge)
G1.graph[0][2] = 1    # (A, B) 간선(edge)
G1.graph[0][3] = 1    # (A, B) 간선(edge)

✍ 입력

# B출발
G1.graph[1][0] = 1    # (B, A) 간선
# G1.graph[1][1] = 0  # (B, B)
G1.graph[1][2] = 1    # (B, C)
# 1.graph[1][3] = 1   # (B, D)

✍ 입력

# C출발
G1.graph[2][0] = 1    # (C, A)
G1.graph[2][1] = 1    # (C, B)
# G1.graph[2][2] = 1  # (C, C)
G1.graph[2][3] = 1    # (C, D)

✍ 입력

# D출발
G1.graph[3][0] = 1    # (D, A)
# G1.graph[3][1] = 1  # (D, B)
G1.graph[3][2] = 1    # (D, C)
# G1.graph[3][3] = 1  # (D, D)

✍ 입력

print('무방향 그래프 ')
for item in G1.graph:
    print(item)

💻 출력 무방향 그래프 [0, 1, 1, 1] [1, 0, 1, 0] [1, 1, 0, 1] [1, 0, 1, 0]

2. 방향성 그래프

✍ 입력

G3 = Graph(4)

# G3.graph[0][0] = 0  # A -> A
G3.graph[0][1] = 1    # A -> B
G3.graph[0][2] = 1    # A -> C
# G3.graph[0][3] = 0  # A -> D

# G3.graph[1][0] = 0  # B -> A
# G3.graph[1][1] = 0  # B -> B
# G3.graph[1][2] = 0  # B -> C
# G3.graph[1][3] = 0  # B -> D

# G3.graph[2][0] = 0  # C -> A
# G3.graph[2][1] = 0  # C -> B
# G3.graph[2][2] = 0  # C -> C
# G3.graph[2][3] = 0  # C -> D

G3.graph[3][0] = 1    # D -> A
# G3.graph[3][1] = 0  # D -> B
# G3.graph[3][2] = 0  # D -> C
G3.graph[3][3] = 1    # D -> D

print('방향성 그래프')
for item in G3.graph:
    print(item)

💻 출력 방향성 그래프 [0, 1, 1, 0] [0, 0, 0, 0] [0, 0, 0, 0] [1, 0, 0, 1]

• front(머리) : 저장된 데이터 중 첫번째 데이터
• rear(꼬리) : 저장된 데이터 중 마지막 데이터

1. 큐 생성

✍ 입력

queue = [None for _ in range(6)]

front, rear = -1, -1               # front = rear = -1

배열 크기를 지정한 후 해당 크기의 빈 큐 생성

line1 : queue = [None for _ in range(6)] -> 배열 크기를 지정 line2 : front, rear = -1, -1 -> 빈 큐 생성(큐 초기화) (front = rear = -1 로도 작성 가능)

2. enQueue: 데이터 텍스트 삽입

✍ 입력

rear += 1
queue[rear] = '셔누'
rear += 1
queue[rear] = '민혁'
rear += 1
queue[rear] = '기현'

print('-- 큐상태 --')
print('[출구]', end=' <- ')
for i in range(0, len(queue)):
    print(queue[i], end=' <- ')
print('[입구]')

💻 출력 -- 큐상태 -- [출구] <- 셔누 <- 민혁 <- 기현 <- None <- None <- None <- [입구]

• rear(꼬리)부터 데이터 삽입

• 꼬리쪽이 입구, 머리쪽이 출구

❓ 질문

• 한번에 한칸씩만 넣을 수 있나?

3. deQueue: 데이터 추출

✍ 입력

front += 1
data = queue[front]
queue[front] = None
print(f'deQueue -> {data}')

💻 출력 deQueue -> 셔누

• front(머리)부터 추출

✍ 입력

print('-- 큐상태 --')
print('[출구]', end=' <- ')
for i in range(0, len(queue)):
    print(queue[i], end=' <- ')
print('[입구]')

💻 출력 -- 큐상태 -- [출구] <- None <- 민혁 <- 기현 <- None <- None <- None <- [입구]

✍ 입력

front += 1
data = queue[front]
queue[front] = None
print(f'deQueue -> {data}')

front += 1
data = queue[front]
queue[front] = None
print(f'deQueue -> {data}')

💻 출력 deQueue -> 민혁 deQueue -> 기현

✍ 입력

print('-- 큐상태 --')
print('[출구]', end=' <- ')
for i in range(0, len(queue)):
    print(queue[i], end=' <- ')
print('[입구]')

💻 출력 -- 큐상태 -- [출구] <- None <- None <- None <- None <- None <- None <- [입구]

• 데이터가 다 추출된 후 또 추출하면 error

Stack

• 한쪽 끝이 막힌 형태
• 입구와 출구가 동일하여 선입후출, 후입선출
• push : 스택에 데이터를 삽입
• pop : 스택에서 데이터를 추출
• top : 스택의 가장 위에 있는 데이터

pythonds 설치

!pip install pythonds

pythonds 사용

from pythonds.basic.stack import Stack

st = Stack()
print(dir(st))

1. push : 데이터 삽입

st.push('셔누')
st.push('민혁')
st.push('기현')
st.push('형원')
st.push('주헌')
st.push('아이엠')

2. peek : 가장 위에 있는 데이터(마지막 입력 데이터)

✍ 입력

st.peek()

💻 출력 '아이엠'

3. size : 스택의 크기

✍ 입력

st.size()

💻 출력 6

4. 스택 내의 데이터 확인

✍ 입력

st.items

💻 출력 ['셔누', '민혁', '기현', '형원', '주헌']

5. pop : 추출

✍ 입력

st.pop()

💻 출력 '아이엠'

마지막에 입력한 데이터가 먼저 나옴

✍ 입력

st.pop()
st.pop()
st.pop()
st.pop()

💻 출력 '셔누'

• 모든 데이터가 추출된 후 다시 추출을 하면 error

• 노드들이 물리적으로 떨어진 곳에 위치
• 각 노드의 번지도 순차적이지 않음
• 화살표로 표시된 연결(link)을 따라가면 선형리스트와 순서가 같음
• 데이터를 삽입/삭제할 때 해당 노드의 앞뒤 링크만 수정하면 되므로 오버헤드가 거의 발생하지 않음
• List(정렬) : 데이터들을 잘 관리하기 위해 묶어서관리할 수 있는 자료형
• Node(노드) : 데이터
• self: class 내의 요소

1. 노드 생성

✍ 입력

class Node:                            # Node라는 class 생성
    def __init__(self) -> None:        # 함수 선언
        self.data = None  # 현재 값
        self.link = None  # 다음 노드가리킴

    def __str__(self) -> str:
        return f'{self.data}'

self.data : 현재 값을

2. 첫번째 노드 생성

✍ 입력

node1 = Node()
node1.data = '셔누'

print(node1)

💻 출력 셔누

3. 두번째 노드 생성

✍ 입력

node2 = Node()
node2.data = '민혁'
node1.link = node2      # 1번 노드의 링크에 두번째 노드를 연결

print(node2)

💻 출력 민혁

4. 나머지 노드 생성

✍ 입력

node3 = Node()
node3.data = '기현'
node2.link = node3

node4 = Node()
node4.data = '형원'
node3.link = node4

node5 = Node()
node5.data = '주헌'
node4.link = node5

node6 = Node()
node6.data = '아이엠'
node5.link = node6

5. 연결 리스트 출력(link)

✍ 입력

print(node1.data, end=' -> ')
print(node1.link.data, end=' -> ')                  # node2.data
print(node1.link.link.data, end=' -> ')             # node3.data
print(node1.link.link.link.data, end=' -> ')        # node4.data
print(node1.link.link.link.link.data, end=' -> ')   # node5.data
print(node1.link.link.link.link.link.data)          # node6.data

💻 출력 셔누 -> 민혁 -> 기현 -> 형원 -> 주헌 -> 아이엠

6. 연결 리스트 출력

✍ 입력

print(node1.data, end=', ')         # node1.data
print(node2.data, end=', ')         # node2.data
print(node3.data, end=', ')         # node3.data
print(node4.data, end=', ')         # node4.data
print(node5.data, end=', ')         # node5.data
print(node6.data)                   # node6.data

💻 출력 셔누, 민혁, 기현, 형원, 주헌, 아이엠

✍ 입력

current = node1
print(current.data, end=' -> ')
while current.link != None:
    current = current.link
    if current.link == None:
        print(current.data)      # 뒤에 연결링크가 없으면(마지막 노드) end=' -> ' 삭제
    else:
        print(current.data, end=' -> ')

💻 출력 셔누 -> 민혁 -> 기현 -> 형원 -> 주헌 -> 아이엠

7. 연결리스트에 새 노드 삽입

✍ 입력

newNode = Node()
newNode.data = '덕준'
newNode.link = node2.link   # node3: kihyun
node2.link = newNode

💻 출력 셔누 -> 민혁 -> 덕준 -> 기현 -> 형원 -> 주헌 -> 아이엠

8. 노드 삭제

✍ 입력

node3.link = node4.link   

💻 출력 셔누 -> 민혁 -> 덕준 -> 기현 -> 주헌 -> 아이엠

• 형원 삭제

• 메모리상에 여전히 노드는 남아 있음

✍ 입력

del(node3) 

노드 완전 삭제