728x90 TIL - 프로그래밍/Python 알고리즘198 [백준] 1504. 특정한 최단 경로 - Python https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 생각 1번에서 N번으로 가는 최단 거리 : 다익스트라 이동 중 주어진 두 정점(v1, v2)을 반드시 통과 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N '세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.' 코드 from sys import stdin,maxsize import heapq input .. 2022. 6. 21. [백준] 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. 이전 1 ··· 12 13 14 15 16 17 18 ··· 33 다음 반응형