하나둘셋넷

자료구조 UNION_FIND] 집합의_표현_1717

전체 코드

# import os
# print(os.getcwd())
# print(os.listdir())

import sys
sys.stdin = open('./자료구조/백준/집합의_표현_1717_송주영/집합의_표현_1717_송주영.txt')
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map( int, input().split())
parent = [i for i in range(n+1)]

for _ in range(m):
    op, a, b = map(int, input().split())
    if op ==0:
        union_parent(parent, a,b)
    elif op ==1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

설명 포함 코드

################################
#### 기초 세팅 ##################
################################

# import os
# print(os.getcwd())
# print(os.listdir())

import sys
sys.stdin = open('./자료구조/백준/집합의_표현_1717_송주영/집합의_표현_1717_송주영.txt')
input = sys.stdin.readline


#######################################
#### UNION FIND 유형 ##################
#######################################

#######################################
#### 특정 원소가 포함된 집합 찾기 #######
#######################################

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 처음 각 원소의 부모 노드 [0, 1, 2, 3, 4]
# 따라서 처음에는 parent[3] = 3
# 이후에 [0, 1, 2, 1, 4]가 되면
# parent[3] != 3, 재귀적으로 find_parent(parent, parnet[3] ) 호출
# 여기에서, parent[3] = 1, 따라서
# find_parent(parent, 1)에서 parent[1] == 1
# return parent[1] 이고 부모 노드인 1을 반환한다.


######################################
#### 두 원소가 포함된 집합 합치기 #######
######################################

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

# 더 큰 값의 부모 노드를 더 작은 값의 부모 노드에 맞춘다.


###################################
#### 값 대입, 문제 풀이 시작 #######
###################################
        
n, m = map( int, input().split())
parent = [i for i in range(n+1)]

for _ in range(m):
    op, a, b = map(int, input().split())
    if op ==0:
        union_parent(parent, a,b)
    elif op ==1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')


# 0이 주어진다 : 문제 조건에 따라 합집합을 만든다.
# union_parent를 실행하면 더 큰 값의 부모 노드를 작은 값의 노드에 맞춘다. 

# 1이 주어진다 : 문제 조건에 따라 같은 집합에 속하는지 찾는다.
# find_parent가 실행되고, 합집합 연산이 수행되었다면 부모 노드가 변경되었을 것이고 재귀적으로 이를 확인한다.

자료구조] 회전하는 큐

입력

사용 라이브러리

import sys

from collection import deque

사용 라이브러리 함수

sys.stdin = open()
input = sys.stdin.readline

deque.popleft()
deque.pop()
deque.appendleft()
deque.append()

풀이

import sys
sys.stdin = open('./자료구조/백준/회전하는_큐/회전하는_큐_4.txt')
input = sys.stdin.readline

from collections import deque

# numbers_len : 큐의 크기, rep : 뽑고자 하는 숫자의 갯수 
numbers_len, rep = map(int, input().split())
# numbers : 1 ~ 큐의 크기 만큼 채운 deque
numbers = deque([i+1 for i in range(numbers_len)])
# members : 뽑고자 하는 숫자들
members = deque(list( map(int, input().split()) ))

cnt = 0

while True:
    print('='*50)
    print('members', members)
    # 원하는 숫자 추출 : 큐의 첫 번째 숫자가 뽑고자 하는 숫자 목록의 첫 번째 숫자와 같다.
    if members[0] == numbers[0]:
        members.popleft()
        numbers.popleft()
        # 반복복문 중지 : 뽑고자 하는 숫자를 모두 뽑았으면 반복문을 종료한다.
        if len(members) ==0:
            break
    else:
    	# 큐를 오른쪽으로 민다.
        # 중앙보다 뒤에 위치하고 있으므로 큐를 오른쪽으로 밀면서 원하는 숫자가 뒤로 빠져나오도록 한다.
        if numbers.index(members[0]) > len(numbers)/2:
            numbers.appendleft(numbers[-1])
            numbers.pop()
            cnt+=1
        else:
        # 큐를 왼쪽으로 민다.
        # 중앙보다 앞에 위치하고 있으므로 큐를 왼쪽으로 밀면서 원하는 숫자가 앞으로 위치하도록 한다.
            numbers.append(numbers[0])
            numbers.popleft()
            cnt+=1

print(cnt)

print 문을 통한 변화 과정 관찰

자료구조] 예산_2512

풀이

import sys
sys.stdin = open('./자료구조/백준/예산_2512_1.txt')
# sys.stdin = open('./자료구조/백준/예산_2512_2.txt')
input = sys.stdin.readline

# 값 입력
n = int(input())
numbers = list( map( int, input().split() ))
budgets = int(input())

low, high = 0, max(numbers)

# 이진탐색을 통해 원하는 값이 나올 때까지 탐색한다.
# allocation(=배정금액) < budgets(=현재예산)인 경우는 탐색 범위에 답이 존재하므로 하한값 low를 늘려가며, 값을 찾는다.
# allocation(=배정금액) > budgets(=현재예산)인 경우는 탐색 범위에 답이 없으므로 상한값 high을 줄인다.
# 위아래로 값을 계속 제거하다보면 high = low인 순간(=교차 지점)이 존재할 것이다.(=그래프로 생각)
# 교차 지점에서 문제의 조건을 만족한다.
while low <= high:
    mid = (low + high) // 2
    allocation = sum( min(budget, mid) for budget in numbers  )
    
    # 계산을 했을 때, 총 배정액이 총 예산보다 크면, high(=배정 상한액)을 작게 한다.
    # 계산을 했을 때, 총 배정액이 총 예산보다 작다면, low(=배정 상한액)을 작게 한다.
    if allocation > budgets:
        high = mid - 1
    else:
        low = mid + 1

print(high)

자료구조] 백준_스택수열_1874

풀이

스택에 넣었던 최대 숫자를 생각한다.

4가 들어왔다면,

+ push 1

+ push 1 2

+ push 1 2 3

+ push 1 2 3 4

- pop    1 2 3

- pop    1 2

+ push  1 2 5

+ push  1 2 5 6

- pop     1 2 5

+ push   1 2 7

+ push   1 2 8

- pop      1 2

1 2 3 4 까지 push

끝이 4가 되면 pop

끝이 3이면 pop

1 2 에 5, 6 push

끝이 6이면 pop

import sys
sys.stdin = open('./자료구조/백준/스택수열_1874/스택수열_1874.txt')
input = sys.stdin.readline

# 입력값에 대해서는 n과 elements에 할당한다.
n = int(input()) # 문제에서 입력하는 값의 개수
elements =  [int(input()) for i in range(n)] # 문제에서 입력하는 값들

# 정답과 연산에 필요한 값들은 stack, answer, current에 할당한다.


def stack_sequence(n, elemeents):
    stack, answer = [], []
    current = 1

    for element in elements:
        while current <= element:
            stack.append(current) # 현재 값이 문제에서 입력한 값보다 작다면, 1, 2, 3 스택을 쌓는다.
            answer.append('+')
            current += 1
        if stack[-1] == element: # 쌓인 스택의 마지막 값이 문제에서 입력한 값과 같다면 값을 출력한다.
            stack.pop()
            answer.append('-')
        else:
            return "NO"
    return answer

result = stack_sequence(n, elements)
if result == "NO":
    print("NO")
else:
    for i in result:
        print(i)

문제 조건에서 주어진 것처럼 처음에 4가 주어진 경우

current는 1부터 +1 씩 커지는 값

1] 4가 될때까지 stack에 값을 쌓기

while current <= elements 조건인 동안

"stack.append(current)"

"current += 1"

current를 1씩 키워가며 1, 2, 3 오름차순으로 stack에 값을 쌓아간다.

2] 마지막 값이 4가 되었다면 출력

stack[-1] == element 이 된다면,

stack.pop()을 통해 값을 꺼낸다.

3] 최종 값은 answer에 할당

3] 오름차순을 위배하게 될 경우 return "NO"

마지막에서는 문제 조건에 따라 출력

백준_스택_10828

문제 파악 

ㆍ스택의 가장 위에 있는 정수란?

 : Python에서 스택의 가장 위에 있는 정수는 스택에 가장 최근에 추가된 요소를 의미

ㆍ 스택은 "후입선출"(Last In, First Out, LIFO) 구조

 : 가장 마지막에 들어온 요소가 가장 먼저 나가는 특성

스택 vs 힙

ㆍ   스택에서 가장 위에 있는 요소는 가장 최근에 추가된 요소

ㆍ  힙 구조에서 가장 위에 있는 요소는 전체 요소 중 가장 우선순위가 높은 요소( 최대 힙, 최소 힙 구조에 따라 다르다 )

문제 접근

ㆍ 따라서, deque 라이브러리를 통해 문제를 풀이한다.

코드

(1) def를 통해 함수 정의, push X를 제외하고 나머지 함수는 인자가 필요 없다.

(2) 딕셔너리  구조인 commands에 함수들을 넣어두고, 이후에 호출할 때 사용한다.

(3) command = input().split()을 통해 명령어를 분리하고 push X의 경우에는 arg에 값을 저장, 그 외의 경우는 None

(4) if cmd != 'push' 구조를 통해 push가 아닌 경우에만 명령어 출력

 ∵ push의 경우 return 값이 존재하지 않는다.

백준_deque

ver1

ㆍ 단순히 명령어 맞춰서 사용

사용 메서드 

생성

deq = deque()

추가

# 시작 부분에 추가
deq.appendleft(0)

# 끝 부분에 추가
deq.append(0)

제거

# 처음 부분 제거
deq.popleft()

# 끝 부분 제거
deq.pop()

풀이

(1) 먼저, n = input().split()로 명령어 쪼개기

(2) n이 2 이상이면, 앞 글자가 push_front인지 아닌지에 따라 명령어 수행

(3) 그 외의 경우도 각자의 경우에 맞게 명령어 수행

ver2

ㆍ 함수 정의, 딕셔너리 구조 활용

(1) def를 통해 각 경우에 맞게 함수를 정의.

(2) push_front(x)와 push_back(x)은 인자가 필요하고, 그 외의 경우는 인자 필요 없다.

(3) 딕셔너리  구조인 commands에 함수들을 넣어두고, 이후에 호출할 때 사용. 올바르게 정의되었는지 확인

print(type(commands['push_front']))

(4) command = input().split() 구조에 명령어가 분리되어 입력

(5) arg = command[1] if len(command) > 1 else None 구조에서,

 arg에는 command에 요소가 2개인 경우 즉, push_front x와 같은 구조인 경우에만 값이 저장

(6) result = commands[cmd](arg) if arg is not None else commands[cmd]() 구조에서,

     commands[cmd]를 통해 cmd에 입력된 값을 key으로 하여 commands의 function를 호출,

     return 값을 result에 저장

     if문을 통해 인자가 있는 경우와 인자가 없는 경우로 나누었다.

(7) if cmd.startswith("pop") or cmd in ["front", "back","size","empty"] 

 위에서 split한 앞 부분이 pop으로 시작하거나 ["front", "back","size","empty"] 에 있을 경우 위에서 연산한 result를 출력

결론

ver 1

ver2

if을 따지는 경우보다 함수를 정의하고 딕셔너리로 호출하면 속도가 훨씬 빠를거라 생각했으나,

실제 시간을 보니 큰 차이를 보이지는 않았다.

백준_큐

코드

import sys
from collections import deque
sys.stdin = open('./자료구조/백준/큐.txt')
input = sys.stdin.readline

space = deque([])
for i in range(int(input())):
    a = input().strip()

    if len(a)==3:
        if space:
            print(int(space.popleft()))
        else:
            print(-1)
    
    elif len(a)==4:
        if a =='back':
            if space:
                print(int(space[-1]))
            else:
                print(-1)
        else:
            print(len(space))
    
    elif len(a)==5:
        if a == 'front':
            if space:
                print(int(space[0]))
            else:
                print(-1)
        else:
            if space:
                print(0)
            else:
                print(1)
    
    else:
        p, num = a.split()
        space.append(num)

풀이

deque 생성

space = deque([])

길이 3

pop

print(int(space.popleft()))

길이 4

back

else( = size )

길이 5

front

else( = empty )

else

push X

split으로 자르고, 뒷 부분을 deque에 추가

p, num = a.split()
space.append(num)

백준_최소 힙

코드

import sys
import heapq as hq
sys.stdin = open('./자료구조/백준/최소힙.txt')
input = sys.stdin.readline
a = []
for i in range(int(input())):
    n = int(input())
    if n == 0:
        if a:
            print(hq.heappop(a))
        else:
            print(0)
    else:
        hq.heappush(a, n)

백준_최대 힙

코드

import sys
import heapq as hq
sys.stdin = open('./자료구조/백준/최대힙.txt')
input = sys.stdin.readline
a = []
for i in range(int(input())):
    n = int(input())
    if n == 0:
        if a:
            print(-hq.heappop(a))
        else:
            print(0)
    else:
        hq.heappush(a,-n)

동작 원리