[백준][2606] 바이러스
아주 바이러스 같은 문제였다.. ㅎ
처음에 연결된 컴퓨터 쌍을 [[1, 2], [2, 3], ...] 같은 리스트 형태로 받아서 코드를 구현했다.
분명히 VS Code 에서 실행했을 때는 문제 없이 돌아갔으나...
런타임 에러와 시간 초과 등 갖가지 고난을 맞이했다.
결국 GPT를 붙잡고 물어봤으나, GPT가 고쳐준 알고리즘도 오답 처리를 몇번이고 받고..
다시 초심으로 돌아가서, 구글링을 통해 해결했다.
n = int(input()) # n : 컴퓨터의 수 (100 이하의 양의 정수)
# 컴퓨터는 1번부터 번호 매겨짐
pairs = int(input()) # 연결된 컴퓨터 쌍의 수
# [[], [1번 컴퓨터와 연결된 컴퓨터], ..., [n번 컴퓨터와 연결된 컴퓨터]]
connected = [[] for _ in range(n+1)]
for _ in range(pairs):
com1, com2 = map(int, input().split())
connected[com1].append(com2) # com1과 연결된 com2 번호를 com1 인덱스의 리스트에 삽입
connected[com2].append(com1) # com2과 연결된 com1 번호를 com2 인덱스의 리스트에 삽입
infected = set() # 감염된 컴퓨터 표시
def dfs(com):
infected.add(com)
for c in connected[com]:
if c not in infected:
dfs(c)
dfs(1) # 1번 컴퓨터부터 감염 시작
print(len(infected)-1) # 최초 감염 컴퓨터 제외하고 출력이 문제에서 핵심은 dfs() 함수가 아니라 ( 이 함수 구현은 쉬웠음)
[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]] 와 같은 형태로
n번 컴퓨터와 연결된 컴퓨터를 정리하는 것이었다.
그래프와 관련된 내용인데, 내가 처음에 컴퓨터 쌍으로 설정한 것은 결국 유방향 그래프라서,
[1, 2] 라면 1 → 2 방향의 검색만 가능하다.
내가 원하는 건 2 → 1 방향의 검색도 가능해야 하기에, 무방향 그래프를 구현하기 위해 위와 같은 형태로 리스트를 구현해야 했다.
0번 인덱스의 리스트가 비어있는 것은, 순전히 나의 편함(?)을 위해서인데,
0번 인덱스를 1번 컴퓨터와 연결된 것으로 하면, 코드에서 인덱스 따라갈 때 +1을 해줘야 하는데,
나중에 코드를 다시 볼 때는 헷갈릴 것 같아서, 인덱스와 컴퓨터 번호가 일치하게 설정했다.
장장 2시간을 붙잡고 있던 문제.. 해결...!! 🤯
[백준][2164] 카드2
미로 문제 풀다가 머리가 너무 아파서..
간단하 문제로 넘어왔다.
진짜 5분 컷 코드..
큐를 코드로 구현하는 것에 의의를 둔 문제 같았다.
from collections import deque
n = int(input()) # n장의 카드 (1~n)
queue = deque([i for i in range(1, n+1)])
# n = 4 이면, queue = deque([1, 2, 3, 4])
def card2():
while len(queue) > 1: # queue에 원소 한개만 남으면 반복 종료
queue.popleft() # 가장 앞의 값을 버리기
pick = queue.popleft() # 남은 값 중 가장 앞의 값을 빼서
queue.append(pick) # 가장 뒤에 넣는다.
print(queue[0]) # 마지막으로 남은 값 출력
card2()[백준][1966] 프린터 큐
첨에 호기롭게 힙을 이용해서 풀려고 했다.
근데 문제는.. 힙을 이용하면 우선순위가 동일한 경우에는 제대로된 계산을 할 수가 없었다.
그래서 우선순위와 처음에 들어온 인쇄 순서를 각각 큐에 저장해서,
조건에 따라 두 큐에서 값을 빼고 넣는 과정을 반복하도록 해서, 문제를 해결했다.
import sys
from collections import deque
tc = int(sys.stdin.readline()) # 테스트케이스의 수
for _ in range(tc):
# n = 문서의 개수, m = 인쇄 순서가 궁금한 문서의 위치 (0부터 시작)
n, m = map(int, sys.stdin.readline().split())
# doc_no : 문서가 최초에 큐에 들어간 순서, priorities : 중요도
doc_no = deque([i for i in range(n)])
priorities = deque(list(map(int, sys.stdin.readline().split())))
order = 0 # 문서가 실제로 인쇄된 순서 기록
while doc_no:
if priorities[0] == max(priorities):
order += 1
printed = doc_no.popleft()
priorities.popleft()
if printed == m:
break
else:
doc_no.append(doc_no.popleft())
priorities.append(priorities.popleft())
print(order)[백준][1927] 최소 힙
이게 바로 힙을 쓰는 문제!
힙의 개념을 이날 배워서, 새로운 heapq를 써봤다.
구현 자체는 쉬웠다.
import sys
import heapq
n = int(sys.stdin.readline())
numbers = [] # 배열 선언
for _ in range(n):
numbers.append(int(sys.stdin.readline()))
num_heap = [] # 힙 만들 배열 저장
heapq.heapify(num_heap) # 최소 힙
output = numbers.count(0) # 필요한 출력 횟수 저장
printed = 0 # 출력 횟수 저장할 변수
for num in numbers:
if num > 0: # 자연수라면
heapq.heappush(num_heap, num) # 배열에 값을 넣는다.
else: # num = 0 일 때
if num_heap: # 힙에 값이 있다면
print(heapq.heappop(num_heap)) # 가장 작은 값 제거면서 그 값을 출력
else: # 힙에 원소가 없다면
print(0) # 0 출력[백준][11279] 최대 힙
이번엔 최대 힙!
heapify는 기본적으로 최소 힙을 구현하기 때문에,
최대 힙 구현을 위해서는 원소에 마이너스(-)를 붙여서 반대로 만들어주면 된다.
[1, 2, 3, 4, 5] 가 있으면, [-1, -2, -3, -4, -5]가 되어서, 최소 힙으로 구현 시, -5가 루트에 오게 되어, 최대 힙처럼 만들 수 있다.
위 문제에 -만 붙이면 되는 거라, 구현은 쉽다.
import sys
import heapq
n = int(sys.stdin.readline())
numbers = [] # 배열 선언
for _ in range(n):
numbers.append(int(sys.stdin.readline()))
num_heap = [] # 힙 만들 배열 저장
heapq.heapify(num_heap) # 최소 힙
output = numbers.count(0) # 필요한 출력 횟수 저장
printed = 0 # 출력 횟수 저장할 변수
for num in numbers:
if num > 0: # 자연수라면
heapq.heappush(num_heap, -num) # 배열에 값을 넣는다. (최대 힙으로 해야하므로, 반대로 '-'를 붙여줌)
else: # num = 0 일 때
if num_heap: # 힙에 값이 있다면
print(-heapq.heappop(num_heap)) # 가장 작은 값 제거면서 그 값을 출력 (원래 값 출력 위해 - 붙임)
else: # 힙에 원소가 없다면
print(0) # 0 출력[백준][15903] 카드 합체 놀이
최소 힙을 활용한 문제!
가장 작은 값을 만들면 되므로, 항상 목록에서 가장 작은 두 값을 더하고,
그 계산 결과는 다시 최소 힙에 두번 추가하면 된다.
import sys
import heapq
n, m = map(int, sys.stdin.readline().split()) # 카드의 개수 n, 카드 합체 횟수 m
cards = list(map(int, sys.stdin.readline().split())) # 맨 처음 카드의 상태 (자연수)
heapq.heapify(cards) # 최소 힙으로 구성하면 가장 위의 최소값부터 꺼내면서 더할 수 있다
for _ in range(m): # 카드 합체 횟수만큼 반복
num1 = heapq.heappop(cards)
num2 = heapq.heappop(cards)
result = num1 + num2
heapq.heappush(cards, result)
heapq.heappush(cards, result)
print(sum(cards))