❇️오늘의 학습 키워드 : 센서(백준 #2212)문제한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 ..

https://www.acmicpc.net/problem/2179n = int(input())a = [input() for _ in range(n)] # 원본b = sorted(list(enumerate(a)), key=lambda x: x[1]) # 인덱스와 같이 저장 + 알파벳 순 정렬# 정렬하는 이유: 모든 문자열 쌍을 다 비교하지 않고 인접한 문자열끼리만 비교하면 되므로def check(a, b): # 앞에서부터 겹치는 최장 길이 체크하는 함수 cnt = 0 for i in range(min(len(a), len(b))): # 인덱스 범위 초과하지 않게 더 짧은 걸 기준으로 비교해야됨 if a[i] == b[i]: cnt += 1 el..

https://www.acmicpc.net/problem/2056from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())indegree = [0] * (n+1) # 선행 작업 개수 기록graph = [[] for _ in range(n+1)] # 후행 작업들의 리스트dp = [0] * (n+1) # 각 작업이 완료되기까지 필요한 최소 시간t = [0] # 각 작업의 소요 시간 저장for i in range(1, n+1): array = list(map(int, input().split())) t.append(array[0]) if array[1] != 0: # 선행 작업이 있는 경우 fo..

❇️오늘의 학습 키워드 : 작업(백준 #2056)문제수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가..

❇️오늘의 학습 키워드 : 비슷한 단어(백준 #2179)문제N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 ..

❇️오늘의 학습 키워드 : 미로만들기(백준 #2665)문제n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.아래 그림은 n=8인 경우의 한 예이다.위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)..