[Day26] 자료구조/알고리즘

유용한 라이브러리

collections, itertools(순열/조합), functools, re, bisect, math 등

속도 개선

1. class로 구현
2. 메서드 대신 슬라이싱 구현
   • list.reverse(), reversed(list), list[::-1]
   • 슬라이싱은 C로 구현되어 있어 메서드보다 통상 8배 정도 빠름. 다만, 공간 복잡도 상승함.
3. for문 대신 list comprehension 사용
4. 재귀는 느림 -> 최후의 수단으로 사용

문제 유형

워밍업 문제

1. 1부터 10,000까지 8이라는 숫자가 총 몇번 나오는가? 8이 포함되어 있는 숫자의 갯수를 카운팅 하는 것이 아니라 8이라는 숫자를 모두 카운팅 해야 한다. (※ 예를들어 8808은 3, 8888은 4로 카운팅 해야 함)

str(list(range(1, 10001))).count('8') 
str([i for i in range(10001)]).count('8')
# 정답 4000

2. 1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오. 단, 점들의 배열은 모두 정렬되어있다고 가정한다. (예를들어 `S = [1, 3, 4, 8, 13, 17, 20]` 이 주어졌다면, 결과값은 (3, 4)가 될 것이다.)

data = [1, 3, 4, 8, 13, 17, 20]
m = float('inf')
index = 0

for i in range(len(data)-1):
    if data[i+1] - data[i] < m:
        m = data[i+1] - data[i]
        index = i

data[index], data[index+1]

data = [1, 3, 4, 8, 13, 17, 20]
list(zip(data, data[1:]))
# [(1, 3), (3, 4), (4, 8), (8, 13), (13, 17), (17, 20)]

sorted(list(zip(data, data[1:])), key=lambda x: x[1]-x[0])
# [(3, 4), (1, 3), (17, 20), (4, 8), (13, 17), (8, 13)]

sorted(list(zip(data, data[1:])), key=lambda x: x[1]-x[0])[0]
# (3, 4)

data = [1, 3, 4, 8, 13, 17, 20]
[[i[1]-i[0], i] for i in zip(data, data[1:])]
'''
[[2, (1, 3)],
 [1, (3, 4)],
 [4, (4, 8)],
 [5, (8, 13)],
 [4, (13, 17)],
 [3, (17, 20)]]
 '''

 sorted([[i[1]-i[0], i] for i in zip(data, data[1:])], reverse=True)
 '''
 [[5, (8, 13)],
 [4, (13, 17)],
 [4, (4, 8)],
 [3, (17, 20)],
 [2, (1, 3)],
 [1, (3, 4)]]
 '''

기본 자료구조 및 알고리즘

1. 스택과 큐
2. 연결리스트
3. 트리와 그래프
   • 3.1 트리 구현
   • 3.2 트리의 순회
4. 정렬 알고리즘
   • 4.1 선택정렬
   • 4.2 삽입정렬
   • 4.3 병합정렬
   • 4.4 퀵정렬
5. 페이지 교체 알고리즘
6. 슬라이딩 윈도우와 투 포인터 알고리즘

스택과 큐

• 스택과 큐는 프로그래밍 언어가 생겨날 때부터 있었던 매우 고전적인 개념
• 스택은 LIFO(Last-In-First-Out, 후입선출)
• 큐는 FIFO(First-In_First-Out, 선입선출)
• 특히 알고리즘 문제에서 너비 우선 탐색(큐)과 깊이 우선 탐색(스택)에 응용됨
• 리스트가 스택과 큐의 모든 연산이 구현되어 있음
• ADT(Abstract Data Type)
  • S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
  • S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
  • S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
  • S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.
• 파선아실 : 파라미터는 선언 아규먼트는 실행
• 깊스너큐 : 깊이는 스택 너비는 큐

* 다음중 스택이 될 수 없는 것은? 스택에 들어가는 값은 1, 2, 3, 4, 5이다. (4번)

1. 1, 2, 3, 4, 5
2. 3, 2, 4, 5, 1
3. 4, 3, 2, 5, 1
4. 1, 5, 4, 2, 3

s = []
s.append(10)
s.append(20)
s.append(30)

# stack
s.pop()   # 30
# queue  <- [] <-
s.pop(0)  # 10

 

Python Algorithm Best20 | WENIV

data = [1, 1, 1, 2, 3, 4, 1, 2, 3, 4, 1]
stack = []
count = 0
for i in data:
    stack.append(i)
    if stack[-5:] == [1, 2, 3, 4, 1]:
        for _ in range(5):
            stack.pop()
        count += 1

count  # 2

연결리스트

• 메모리 효율을 위해 사용되는 경우가 많음

# 22, 2, 90, 77 을 연결한 linked list 구현
# step 2 자동으로 다음 노드가 연결되는 linked list 구현
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        init = Node('init')
        self.head = init
        self.tail = init
        self.count = 0

    def append(self, data):
        newNode = Node(data)
        self.tail.next = newNode
        self.tail = newNode
        self.count += 1

    def __len__(self):
        return self.count

    def __str__(self):
        current = self.head
        current = current.next
        s = ''
        for _ in range(self.count):  # while current:
            s += f'{current.data}, '
            current = current.next
        return f'<{s[:-2]}>'

# step 3 추가 기능 구현
    def pop(self):
        마지막값 = self.tail.data
        현재노드 = self.head

        for i in range(self.데이터수):
            if 현재노드.next is self.tail:
                self.tail = 현재노드
                break
            현재노드 = 현재노드.next

        self.데이터수 -= 1
        return 마지막값

    def find(self, data):
        index = -1
        현재노드 = self.head

        for i in range(self.데이터수+1):
            if 현재노드.data == data:
                return index
            index += 1
            현재노드 = 현재노드.next

        return -1

    def insert(self, input_index, input_data):
        현재노드 = self.head

        for i in range(input_index):
            현재노드 = 현재노드.next

        신규노드 = Node(input_data)
        신규노드.next = 현재노드.next
        현재노드.next = 신규노드

        self.데이터수 += 1

# step 4 순회기능 구현    
    def __iter__(self):
        현재노드 = self.head
        현재노드 = 현재노드.next
        while 현재노드:
            yield 현재노드.data
            현재노드 = 현재노드.next

l = LinkedList()
l.append(22)
l.append(2)
l.append(90)
l.append(77)

len(l)  # 4
print(l)  # <22, 2, 90, 77>
for i in l:
    print(i)
# 22
# 2
# 90
# 77