본문 바로가기
728x90

Python164

[백준] 1753. 최단 경로 - Python https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 생각 한 점에서 모든 점으로 최단 경로 : 다익스트라 heapq : 최소힙 구하기 [값, 노드번호] 모든 점 초기값 무한대로 설정 시작점 거리 0 설정, 힙[(비용, 다음노드)] 추가 힙에서 하나씩 빼면서 수행 현재 거리가 새로운 간선 거칠 때보다 크다면 갱신 새로운 거리 힙에 추가 다익스트라 시간 복잡도 : ElogV heap 삽입, 삭제 시간 복잡도 : l.. 2022. 6. 20.
[백준] 14502. 연구소 - Python https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 생각 벽 3개 만들기 바이러스 퍼트리기 안전 영역 크기 확인 최대면 갱신 반복 코드 from copy import deepcopy from sys import stdin from collections import deque # 지도 가로*세로 N*M N, M = map(int, stdin.readline().split()) arr = [list(map(int, stdin.readline().split())) .. 2022. 6. 19.
[백준] 15649. N과 M (1) ~ (4) - Python https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 생각 재귀로 달성하면 return 코드 from sys import stdin N, M = map(int, stdin.readline().split()) # 수열, 수열에 들어간 요소 표시 def check(arr,visited): # 수열의 길이가 M인가? if len(arr) == M: print(*arr) return for i in range(1,N+1): # 수열에 없다면 if visi.. 2022. 6. 18.
[백준] 2805. 나무 자르기 - Python https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 생각 가장 큰 나무 길이부터 1개씩 줄여가면서 원하는 나무 길이 맞추기 시간 초과... 만약 자를 나무의 길이가 매우 작을 때 오래 걸릴 듯 이진 탐색으로 가장 큰 나무 길이의 절반으로 잘라보고 자른 나무길이가 부족하면 높이를 낮추고 자른 나무길이가 남으면 높이를 올린다. 코드(실패-시간초과) from sys import stdin # 나무의 수 N, 원하는.. 2022. 6. 17.
[프로그래머스] Lv.2 양궁대회 - Python https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 생각 라이언이 쏠 과녁 수 최대가 10이니 라이언이 과녁 쏘는 경우의 수 모두 완탐.. from itertools import combinations_with_replacement : 중복조합 완탐 해도 시간초과 안 날지 걱정 예제 3번의 라이언이 과녁 쏘는 경우의 수 약 18만.... 걱정되었지만 다른 방법 생각 안나서 진행함 라이언이 쏠 수 있는 각 경우의 수에서.. 2022. 6. 16.
[프로그래머스] Lv.2 주차 요금 계산 - Python https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr 생각 요금을 일괄 계산!! 차량번호가 작은 순으로 요금 return 차량 번호가 작은 순으로 + 시간 순으로 정렬 차가 들어오거나 나가는 시간 배열로 만들기 차량 주차 시간 구하기 요금.. 2022. 6. 16.
반응형

티스토리툴바