Python 202

[Python] 1504. 특정한 최단 경로

import heapq def dijkstra(s, e): dist = [float('inf') for _ in range(n + 1)] # 초기화 queue = [] heapq.heappush(queue, [0, s]) # 시작 지점 넣기 dist[s] = 0 while queue: d, now = heapq.heappop(queue) # 거리, 현재 정점 if now == e: # 도착 정점이면 중단 break if dist[now] < d: # 가지치기 continue for next in visited[now]: # 현재 정점에서 갈 수 있는 정점 탐방 nd = next[1] + d # 거리 더해주기 if nd < dist[next[0]]: # 출발 정점 ~ 다음 정점까지의 거리보다 작다면 dis..

Algorithm/Baekjoon 2021.12.16

[Python] 2805. 나무 자르기

n, m = map(int, input().split()) # 나무의 수 n, 나무의 길이 m tree_h = list(map(int, input().split()) # 나무의 높이 s, e = 1, max(tree_h) # 시작 높이, 끝 높이 while s = mid: # mid보다 큰 나무라면 자르기 temp += tree - mid # temp == m: break 하면 안됨. 절단기의 높이를 더 높일 수 있기 때문 if temp >= m: # 목표 나무 길이보다 크다면 절단기 높이기 s = mid + 1 else: # 목표 나무 길이보다 작다면 절단기 낮추기 e = mid - 1 print(e)

Algorithm/Baekjoon 2021.12.16

[Python] 9251. LCS

seq1 = input() # 문자열 1 seq2 = input() # 문자열 2 seq_l1 = len(seq1) + 1 # 1번 문자열의 길이 seq_l2 = len(seq2) + 1 # 2번 문자열의 길이 dp = [[0 for _ in range(seq_l2)] for _ in range(seq_l1)] for i in range(1, seq_l1): # dp 배열 행열에 맞춰서(seq1-행, seq2-열) for문 선언 for j in range(1, seq_l2): if seq1[i-1] == seq2[j-1]: # 가장 최근에 추가된 글자가 같다면 dp[i][j] = dp[i-1][j-1] + 1 # 글자가 추가되기 전, 최대 길이 + 1 else: # 다르다면 dp[i][j] = max(d..

Algorithm/Baekjoon 2021.12.16

[Python] 12865. 평범한 배낭

n, k = map(int, input().split()) # 물품의 수 n, 버틸 수 있는 무게 k arr = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)] # [물건의 무게, 물건의 가치] dp = [[0 for _ in range(k+1)] for _ in range(n+1)] for i in range(1, n+1): w = arr[i][0] # 현재 물건의 무게 v = arr[i][1] # 현재 물건의 가치 for j in range(1, k+1): if j < w: # 무게 j보다 현재 물건의 무게가 더 무겁다면 dp[i][j] = dp[i-1][j] # 바로 이전 물건, 같은 무게로 채우기 else: # 무게 j보다 현재 물건..

Algorithm/Baekjoon 2021.12.16

[Python] 후보키

from itertools import combinations def solution(relation): relation_r = list(zip(*relation)) # 돌린거 col = len(relation_r) # 컬럼 개수 row = len(relation) # 행 개수 result = 0 # 유일성 만족하는 컬럼 1개 개수 not_candi = [] # 유일성 만족하지 못하는 컬럼 for i in range(col): if row == len(set(relation_r[i])): # 유일성을 만족하면 result += 1 # +1 else: not_candi.append(i) # 유일성을 만족하지 못하는 컬럼 리스트에 추가 make_candi = [] for i in range(2, len(no..

[Python] 셔틀버스

def solution(n, t, m, timetable): timetable.sort() # 타임테이블 정렬 crew_n = len(timetable) # 타임테이블 개수 for i in range(crew_n): # 시간표를 분으로 전환 hour, minutes = map(int, timetable[i].split(':')) timetable[i] = hour * 60 + minutes bus_time = 9 * 60 - t # 버스 처음 시간 p = 0 # 크루 포인터 for bus in range(1, n + 1): bus_time += t # 버스 시간 passenger = 0 # 탑승 크루 수 for crew in range(p, crew_n): # 안탄 크루들 태우기 if timetable[..

[Python] 오픈채팅방

def solution(record): id_nick = {} # id에 따른 닉네임 저장 log = [] # 들어왔다 나갔다 기록 for rec in record: rec = rec.split() # 띄워쓰기 기준으로 분리 if rec[0] == 'Enter': # 채팅방에 들어온 경우 id_nick[rec[1]] = rec[2] # id를 키로, nickname을 value로 저장 log.append((rec[1], '님이 들어왔습니다.')) # 채팅방 출입 기록에 저장 elif rec[0] == 'Leave': # 채팅방 나간 경우 log.append((rec[1], '님이 나갔습니다.')) # 채팅방 출입 기록에 저장 else: # 닉네임 수정한 경우 id_nick[rec[1]] = rec[2] ..