8주차_백준 #1541_잃어버린 괄호 #1927_최소 힙 #11659_구간 합구하기 4 파이썬

#1541 잃어버린 괄호 code

#1541 더 간략한 코드

#1541번 문제 

첫번째 코드는 일어나자마자 푼 문제라 머리가 제대로 돌아가지 않아서 약간 좀 그렇게 매끄럽지 않은 코드이다. 하지만 두번째 코드는 좀 인터넷에 찾아보니까 단순하고 명확한 코드가있었다. 설명을 하자면 ()을 아무대나 할 수 있고, 이것을 통해 최소 값을 만드는 것이다. 즉, 예를 들어 50-13+32+24+5 이런 숫자가 있다면 괄호 없이 그냥 계산한다면 양수가 나올 것이다. 하지만 괄호를 사용한다면! 50-(13+32+24+5) 음수가 결과로 나온다. 즉 괄호로 인해 엄청 큰 마이너스 값을 만들 수 있다는 것이다. 

일단 이것을 봤을 때 최소값을 구하는 알고리즘은 딱 떠오른다. 아! -라는기호가 나왔을 때 다음 +기호들은 전부 더하고 총 값을 마이너스로 하면 되겠구나 라는 생각 을 할 수 있다. 즉 50-~~~ 가 나온다면 그냥 50은 양수이기 때문에 제외하고 - 뒤에 +가 계속 나온다면 다 마이너스 총합으로 만들면 된다는 얘기이다.   

 

 

 

#1927번 문제

import sys

import heapq

input = sys.stdin.readline

arr = []

n = int(input())

for _ in range(n):

    operation = int(input())

    if operation == 0:

        if not arr:

            print(0)

        else:

            print(heapq.heappop(arr))

    else:

        heapq.heappush(arr, operation)

 

자료구조 중 스택, 큐, 우선순위 큐가 있다. 스택(Stack)은 filo(first in last out), 후입선출이라고 부르기도 한다. 가장 먼저 들어온 것은 가장 나중에 나간다는 것이다. (그래서 한번 스트레스 스택이 쌓인다면.... 정신병이 걸릴 수도 있다... 처음 들어간 근본적인 스트레스를 바로  빼낼 수 없기 때문이다... 모두 스트레스 없이 건강하게 삽시다)

큐(Queue) 은 fifo(first in first out)(피포!), 선입선출이라고 부르기도 한다. 가장 먼저 들어온 것을 가장 먼저 빼내거나 쓸 수 있다는 것이다. 그리고 여담이지만 이 두개의 기능을 합쳐 양쪽에서 빼낼 수 있는 것을 Deque(덱) 이라고 한다. 파이썬에서는 from collections import deque를 통해 쉽게 쓸 수 있다. 어쨋든 덱은 사용자 마음대로 양쪽에서 빼낼 수 있다.

 

우선순위 큐에는 힙이 있다. 힙은 두 가지로 나뉜다. 최대 힙(max heap), 최소 힙(min heap)이 있다. 파이썬에서는 기본적으로 heap 라이브러리를 불러와서 사용하면 min heap으로 세팅이 되어 있다. max heap으로 만들려면 -를 사용하려는 배열에 붙이면 된다.

 

어쨋든 1927번 문제는 힙을 사용하여 숫자들을 정렬할 수 있다. 그것도 빠르게! 힙의 시간 복잡도는 N*logN ! 왜냐하면 완전 이진트리를 이용하여 정렬하기 때문이당 ㅎㅎㅎ

 

더 자세한 설명을 듣고 싶다면 유튜브에 힙을 검색하여 강의를 수강하길 바란다.

 

#11659 문제

import sys

input = sys.stdin.readline

n ,m = map(int, input().split())

data = list(map(int,input().split()))

Sum_data = [0]

count = 0

for i in data:

    count += i

    Sum_data.append(count)

for _ in range(m):

    a, b = map(int, input().split())

    print(Sum_data[b]-Sum_data[a-1])

 

11659번 구간 합 구하기 문제는 약간의 dp(다이나믹 프로그래밍) 느낌도 있다. 그저 구간이 정해지면 sum()함수로 리스트를 통해 구한다면, 구간이 주어질 때마다 다시 연산을 해야하기 때문에 시간초과가 뜬다. 하지만 약간의 다이나믹 프로그래밍 개념처럼 누적을 통해 구한다고 생각한다면  리스트에 N개의 수가 구어졌다면 O(n) 시간복잡도 만큼이 든다. 즉 5개의 수가 주어졌다고 하면 1번째 합, 1~2번째 합, 1~3번째 합 ... 1~5번째 합, 총 다섯개의 합이 나온다. 

그 다음 주어진 구간의 입력이 들어오면 그 구간에 맞게 더 많은 합에서 작은 합을 빼면 된다. 예를 들면 2, 4라는 구간이 주어진다면 1~4번째 합에서 1번째 합을 뺀다면 2~4번째 합이 나온다.