230503_DB복습

안녕하세요. 보랏입니다.

 

오늘은 강의에서 Django 복습을 위주로 진행하여서

자료구조 및 알고리즘에 대한 제가 개인적으로 공부한 내용을 올리도록 하겠습니다.

스택&큐, 힙(heap)에 대해서 정리하겠습니다.

 

 

1. 스택(stack)

개념

• 스택은 데이터를 차곡차곡히 쌓아 올린 자료구조
• 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 LIFO(후입선출)구조
• 한 방향으로만 쌓거나 삭제가 가능
• 파이썬에서는 append, pop 기능을 통해 구현

사용사례

• 웹 브라우저 방문기록(뒤로 가기)
• 실행 취소
• 역순 문자열

 

예제 문제 - 같은 숫자는 싫어(프로그래머스 : https://school.programmers.co.kr/learn/courses/30/lessons/12906)

문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 

코드 

def solution(arr):
    answer = []
    for i in range(len(arr)) :
        if i == 0 : 
            answer.append(arr[i])
        elif arr[i] != arr[i-1] : 
           answer.append(arr[i]) 
    return answer

 

 

2. 큐(Queue)

개요

• 큐는 스택과 반대로 먼저 들어온 것이 먼저 나가는 FIFO(선입선출)구조
• 인큐(Enqueue) : 리어(rear)에서 이루어지는 삽입 연산
• 디규(Dequeue) : 프론트(front)에서 이루어지는 삭제 연산

 

사용 사례

• 우선순위 활동
• 프로세스 관리 

 

예제 문제 - 카드 정렬하기(백준 : https://www.acmicpc.net/problem/1715)

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

 

코드

from queue import PriorityQueue
N = int(input())
pq = PriorityQueue()

for _ in range(N):
    pq.put(int(input()))

data1 = 0; data2 = 0; sum = 0
while pq.qsize() > 1:
    data1 = pq.get()
    data2 = pq.get()
    tmp = data1 + data2
    sum += tmp 
    pq.put(tmp)

print (sum)

3. 힙(heap)

개요

• 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료 구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 가장 큰 값(가장 작은 값)이 최상위 노드에 있고 그 밑으로 작은(큰)노드들이 트리 구조로 형성
• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

사용 사례

• 운영 체제 작업 스케쥴링
• 네트워크 트래픽 제어

 

예제 코드 - 최대 힙(백준 : https://www.acmicpc.net/problem/11279)

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

코드

import heapq
import sys
n = int(input())
heap = []


for _ in range(n):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, (-num))
    else:
        try:
            print ( -1 * heapq.heappop(heap))
        except:
            print(0)

 

 

이번주는 Django복습 내용이 주를 이룰거 같고 다음주는 팀 프로젝트를 진행하게 되어

완성 시 코드를 공유하는 쪽으로 복습을 진행하겠습니다.

 

감사합니다.