[내일배움캠프] 14일차 TIL 230330

 

알고리즘 세션

스택 / 큐

코테 빈출!

 

스택(Stack)

: 한쪽 끝이 막힌 통과 같은 자료 구조 - 후입선출 LIFO

큐(Queue)

: 양쪽 끝이 뚫림 - 선입선출 FIFO

 

활용

데이터 임시 저장

매개변수, 지역변수

큐의 활용

임시저장 : 버퍼로 활용, 임시저장 데이터 차례차례 내보내고 꺼내와야 할 때, 줄 세우고 싶을 때 

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1]
    
    def size(self):
        return len(self.items)

원형 큐 : 원형으로 이루어진 큐

덱 (Deque) : 양쪽에서 데이터 삽입, 삭제 가능

정렬

버블정렬 선택정렬 삽입정렬 퀵정렬

 

내장 정렬 함수

sorted()

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_list = sorted(my_list)
print(sorted_list)
print(my_list)

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_list = sorted(my_list, reverse = True)
print(sorted_list)
print(my_list)

값 자체가 바뀌지 않고 정렬

 

sort()

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
my_list.sort()
print(my_list)
print(my_list)

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
my_list.sort(reverse=True)
print(my_list)
print(my_list)

배열의 값 자체를 바꿔버림

 

 

 

삽입 정렬 (Insertion sort) 

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교, 자신의 위치를 찾아 삽입

시간복잡도 O(n^2)

 

버블 정렬 (Bubble sort)

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

시간복잡도 O(n^2)

 

선택정렬 (Selection sort)

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다. (오름차순)

시간복잡도 O(n^2)

 

퀵 정렬 (Quick sort)

퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

시간복잡도 O(nlogn)

 

분할 정복(divide and conquer) 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

- 리스트 안에 있는 한 요소를 선택 👉 피벗(pivot)
- 피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬
- 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
👉 분할 & 정복

알고리즘 문제풀이

몫 구하기

이거 꼭 answer 쓸 필요 없지 않나.. 싶어서

def solution(num1, num2):
    return num1//num2

최빈값 구하기

내 답

def solution(array):
    counter = {}
    for i in array:
        if i in counter:
            counter[i] += 1
        else:
            counter[i] = 1

    max_count = max(counter.values())
    max_i = [k for k, v in counter.items() if v == max_count]
    if len(max_i) > 1:
        return -1
    else:
        return max_i[0]

다른 사람 답 중 가장 인상 깊은 답

def solution(array):
    while len(array) != 0:
        for i, a in enumerate(set(array)):
            array.remove(a)
        if i == 0: return a
    return -1