하나둘셋넷

알고리즘 기초설정] 빠른 입력, 깊이 제한 조절 sys.stdin.readline, sys.setrecursionlimit()

빠른 입력

import sys
input = sys.stdin.readline

깊이 제한 조절

import sys
sys.setrecursionlimit(10**9)

자료구조 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"

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

트리] 용어, 이진 탐색 트리,순회

용어 정리

ㆍ 루트 노드(root node) : 부모가 없는 최상위 노드

ㆍ 단말 노드(leaf node) : 자식이 없는 노드

ㆍ 크기(size) : 트리에 포함된 모든 노드의 개수

ㆍ 깊이(depth) : 루트 노드로부터의 거리

ㆍ 높이(height) : 깊이 중 최댓값

ㆍ 차수(degree) : 각 노드의 (자식 방향) 간선 개수

기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 ( N-1 )개

이진 탐색 트리(Binary Search Tree)

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

순회(Tree Traversal)

ㆍ 전위 순회(pre-order tranverse) : 루드를 먼저 방문

     1 →  2  →  4  →  5  →  3  → 6  →  7

ㆍ 중위 순회(in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문

     4  →  2  →  5  →  1  →  6  → 3  →  7

ㆍ 후위 순회(post-order traverse) : 오른쪽 자식을 방문한 뒤에 루트를 방

     4  →  5  →  2  →  6  →  7  → 3  →  1

백준_스택_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)

동작 원리

문제_센서_2212

코드

import sys
sys.stdin = open('./그리디/백준/센서_송주영_11_19_1.txt')
# sys.stdin = open('./그리디/백준/센서_송주영_11_19_1.txt')
input = sys.stdin.readline
num_sensor = int(input().strip())
num_center = int(input().strip())
location = list( map( int, input().split() ))
location.sort()
print(location)
minus = []

for i in range(1,len(location)):
    minus.append(location[i] - location[i-1] )

print(minus)

minus.sort(reverse = True)

print(sum(minus[num_center - 1:]))

for i in range(1, len(location)):

센서 간의 거리 차를 계산한다.

센서가 5개라면 4개의 값들이 들어갈 것이다.

minus.sort(reverse = True)

거리 차를 큰 값부터 정렬한다.

sum(minus[num_center - 1: ] ))

원본

[ 1, 3, 6, 6, 7, 9 ]

차이

[ 2, 3, 0, 1, 2 ]

차이 내림차순

[ 3, 2, 2, 1, 0 ]

sum(minus[num_center - 1: ] ))

[ 2, 2, 1, 0 ] 합 구하기

즉, 이 예시를 기준으로 한다면 3과 6에 기지국을 설치하여 그룹을 나눈다.

[1, 3 ]

거리차 합 2

[ 6, 7, 9 ]  

거리차 합 3

문제_강의실_배정_11501

코드

import sys
import heapq
sys.stdin = open('./그리디/백준/강의실_배정_송주영_11_19.txt')
input = sys.stdin.readline # input() 보다 더 빠른 실행
n = int(input().strip()) 
# n개의 수업 # sys.stdin.readline으로 읽었으므로 strip()을 통해 앞뒤 공백 혹은 개행문자 제거

# class 목록
class_list = [list(map(int, input().split())) for _ in range(n)]
# 시작 시간을 기준으로 오름차순 정렬
class_list.sort(key=lambda x: x[0])

rooms = []

for start, end in class_list:
    if rooms and rooms[0] <= start:
        heapq.heappop(rooms)

    heapq.heappush(rooms, end)
print(len(rooms))

입력, 라이브러리

import sys
import heapq
sys.stdin = open('./그리디/백준/강의실_배정_송주영_11_19.txt')
input = sys.stdin.readline # input() 보다 더 빠른 실행
n = int(input().strip()) 
# n개의 수업 # sys.stdin.readline으로 읽었으므로 strip()을 통해 앞뒤 공백 혹은 개행문자 제거

# class 목록
class_list = [list(map(int, input().split())) for _ in range(n)]
# 시작 시간을 기준으로 오름차순 정렬
class_list.sort(key=lambda x: x[0])

rooms = []

input = sys.stdin.readline

input() 함수를 sys.stdin.readline 으로 대체하여 보다 빠른 성능 구현, 시간초과 문제 해결
strip()을 뒤에 붙여 앞뒤 공백 및 개행문자 제거

heap 사용

시작 시간과 끝나는 시간을 별도로 고려하고 현재 사용 가능한 강의실이 없을 때에만, 새로운 강의실 추가한다.

여러 개의 강의가 동시에 시작하는 경우를 생각해봐야 한다.

시작 시간을 기준으로 오름차순으로 정렬이 된 상태이다.

처음 [1, 8], [3, 7], [5, 6]은 동시에 진행되는 강의이므로 3개의 강의실이 필요하다.

heap.heappush(room, end)

room에 각각의 end 값 3개를 담는다.

여기에서 room[0] 즉 heap의 최상단 요소(루트)에는 항상 가장 작은 값이 위치한다.

heap.heappush(rooms, end)를 통해 heap에 값을 넣을 때, 새 요소가 현재의 최소값보다 작다면,

새 요소를 최상단에 위치 시키고 기존의 최소값은 아래로 위치시킨다.

if rooms and rooms[0] <= start:

 새로 시작하는 강의 시작 시간이 이전 강의들의 종료 시간보다 같거나 늦을 경우에는 강의실을 추가할 필요가 없다.

heap의 특성으로 가장 작은 요소는 아래 코드를 통해 제거한다. 

 빈 리스트에서 rooms[0]을 수행하지 않도록 rooms를 and 앞에 추가한다.

heap.heappop(rooms)

아래 코드를 통해 새로운 강의 종료 시간을 추가한다.

heap.heappush(room, end)

최종 답은 아래 코드를 통해 출력할 수 있다.

print(len(rooms))

문제_주식_11501

입력 세팅

import sys
sys.stdin = open('./그리디/백준/주식.txt')
d = int(input()) # 테스트 케이스의 수를 입력 받는다.

반복문 세팅

for _ in range(d):
    n = int(input()) # 날의 수를 입력받는다.
    prices = list(map(int, input().split() )) 
    max_profit = 0
    max_price = 0
    
    for price in reversed(prices): # 최신값부터 큰 순서대로 따져본다
        if price > max_price:
            max_price = price
        else:
            max_profit += max_price - price
    print(max_profit)

설명) for 문, if 문, else 문

for price in reversed(prices):

최신값부터 과거값 순서로 역순으로 값들을 탐색한다.

if price > max_price:

최신 값보다 과거 값이 더 큰 경우를 말한다.

max_price 값을 업데이트 한다.

else:

     max_profit += max_price - price

과거 값이 더 작은 경우를 말하며, 이 경우는 수익이 생긴 것이다.

따라서, max_profit을 업데이트 한다.

[10, 7, 6] 경우

최신 값들 보다 과거 값들이 더 크다.

if price > max_price의 경우로 max_price 값만 계속 업데이트 되며

max_profit은 0으로 계속 유지된다.

[3, 5, 9] 경우

처음에 max_price가 9로 된 후에 과거 값들 중에서 9보다 큰 값이 없으므로, max_profit 업데이트만 발생

max_profit 에 (9-5), (9-3) 값이 더해진다.

즉, max_profit =  4 + 6  → 10

[1, 1, 3, 1, 2] 경우

max_profit 에 (2-1) 을 더하고,

max_price가 3으로 업데이트 된 이후

max_profit에 (3-1) + ( 3-1) 이 더해진다.

즉 max_profit = 1 + 2 + 2 →  5

합이 같은 부분집합

 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

입력

 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

출력

 첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

입력 예시

 1 6 1 3 5 6 7 10

출력 예시
 YES

코드로 구현해보자

import sys
sys.stdin = open('.\DFS, BFS\인프런_알고리즘_강의\부분집합\합이 같은 부분 집합.txt','r')

def DFS(L, sum):
    if sum > total//2:
        return # 호출된 재귀함수를 종료하고 싶을 때는 return을 사용한다.

    if L == n:
        if sum ==(total-sum):
            print("YES")
            sys.exit(0)
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

n = int(input()) # 성분의 개수를 입력하자
a = list(map( int, input().split() )) # 안에 있는 요소들을 출력하자.
total = sum(a)
DFS(0, 0) # 여기에서 앞에 0은 시작 지점, 뒤는 현재까지의 누적합을 의미한다

.

부분집합_구하기

[문제]

첫 번째 줄부터 각 줄에 하나씩 출력예제 1과 같이 출력하려 한다. 출력 순서는 깊이 우선탐색 전위순회방식으로 출력한다. 단, 공집합은 출력하지 않는다.

[입력예제_1]

3

[출력예제_1]

1 2 3

1 2

1 3

1

2 3

2

3

import sys

sys.stdin = open("input.txt", "r") # txt에는 3이 입력되어 있다.



def DFS(v):

    if v == n+1: # 3까지 확인하는게 목표이므로 값이 4가 되었다면 현재까지 체크한 내용을 출력하도록 하자

        for i in range(n+1):

            if ch[i] == 1

                print(i, end = ' ')

            print()

    else:

        ch[v] = 1

        DFS(v+1)

        ch[v] = 0

        DFS(v+1)



n = int(input()) # 어디까지의 부분 집합을 구하고 싶은지 입력한다.

ch = [0] * (n+1)

DFS(1) # 1부터 체크를 시작한다.