Algorithms and Languages/파이썬 알고리즘 문제풀이 (59) 썸네일형 리스트형 [Python/백준] 1789. 수들의 합 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 및 난이도 보기더보기그리디/실5https://www.acmicpc.net/problem/13681차 풀이, 성공import sysinput = sys.stdin.readline# 자연수 S 입력받으면,# N개 자연수 합이 S가 되는 N의 최댓갑은?# 즉, 자연수의 개수가 최대가 되게 하려면??# -> 1부터 선택해나가면 될 듯한데? 그리디.# 근데, 예를 들어 11이면, 1 2 3 4 하고 5는 11보다 크니까 빠꾸.# 근데 10의 경우는 그 합이 ==니까 끝.s = int(input())n = 1total = 0while(True): total += n # if total s: .. [Python/백준] 1368. 물대기 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기크루스칼 알고리즘https://www.acmicpc.net/problem/1368현장에서 모의고사로 푼 풀이아이디어를 도저히 못 떠올리겠어서 못 풀고 실패함.import sysinput = sys.stdin.readline# 입력 : 논의 수 N 1부터 시작# 그리고 N개의 줄 동안, i번째 논에 우물을 팔 때 드는 비용# 그 다음 N개의 줄은, 각 줄에 N개의 수가 들어오는데,# 이는 i -> j 논 연결 비용 matrix임.# 흠,... 일단, 뭔가 하나의 우물을 파고, 거기 기점으로 쫙 다 연결하거나,# 아님 여러 개 우물 팔 수도 있겠음.# 브루트 포스로는 90000^2는 무조건 넘을 .. [Python/백준] 1238. 파티 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기다익스트라 알고리즘https://www.acmicpc.net/problem/1238현장에서 모의고사로 푼 풀이from heapq import heappush, heappopimport sysinput = sys.stdin.readline# n개의 숫자로 구분# 정점 N개(1~n), m개의 단방향 도로# i번쨰 길을 지나는 데 T[i]의 시간이 소비됨.# 입력 : n, m, x# x에 갔다가 집에 와야함# 그 다음부터는 x -> y 가는 데 t 걸리는 간선정보 들어옴# 이거, 각 학생이 target까지 가는 시간과, 돌아오는 시간을 구해야 함.# => 다익스트라를 두 번 써서 학생 -> targ.. [Python/백준] 17086. 아기 상어 2 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기bfshttps://www.acmicpc.net/problem/17086현장에서 모의고사로 푼 풀이from collections import dequeimport sysinput = sys.stdin.readline# 일단 델타 탐색 써야하는건 거의 무조건같음.# 안전 거리의 최댓값을 어케구하지?# 각 상어 기준으로 거리를 다 계산한담에 max때리면 되지 않을까?# 각 상어 기준으로 거리를 다 구하고, 거기서 max를 구한 뒤에, 이걸 다시 max# 그럼 거리는 델타 탐색에 bfs 엮어 쓰면 될거 같은데# => 해보니 시간 초과남 아# 산불 문제 이거 아니었는거같음 큐에 미리 다 넣고 시.. [Python/백준] 2628. 종이자르기 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기이차원 리스트 + 구현https://www.acmicpc.net/problem/2628현장에서 모의고사로 푼 풀이import sysinput = sys.stdin.readline# 간선을 좌표로 가지면, 될거같은데?# n x m = 8 x 10이라 하면,# 이걸 9 x 11로 만들어서, 간선을 자를 수 있을듯.# n = n + 1# m = m + 1# # ex. 10 8 들어오면 -> 9 x 11이다.# paper = [[True] * m for _ in range(n)]## iter_of_cutting = int(input())# for _ in range(iter_of_cutting):# .. [Python/백준] 1753. 최단거리 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기다익스트라 알고리즘https://www.acmicpc.net/problem/1753풀이리스트를 사용한 다익스트라→ 시간초과(O(V^2))import sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[] for _ in range(n+1)]s = int(input())for _ in range(m): x, y, w = map(int, input().split()) graph[x].append((y, w))def dijkstra(node): # 3. 시작 정점까지의 최단 거리는 0으로 distance.. [Python/백준] 1976. 여행 가자 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기유니온 파인드https://www.acmicpc.net/problem/1976풀이성공, 주석 제거 버전import sysinput = sys.stdin.readlinedef find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x]def union(x, y): x_root = find(x) y_root = find(y) if x_root == y_root: return if rank[x_root] > rank[y_root]: parent[y_root] =.. [Python/백준] 1647. 도시 분할 계획 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기크루스칼 알고리즘 https://www.acmicpc.net/problem/1647풀이1차 접근, 실패import sysinput = sys.stdin.readline# 집 N개, 길 M개, 연결 그래프이고, 유지비(가중치) 있음.# 마을을 두 개로 분할할 건데, 각 분리된 마을은 연결 그래프여야 함.# 그리고 각 마을은 집이 하나 이상 있어야 함.# 길을 없앨 건데,# 1. 분리된 두 마을 사이에 있는 길은 없애고,# 2. 각 마을 안에서도 임의의 두 집 사이에 항상 경로가 존재하게 하면서# 길을 더 없앨 수 있음. => 이거는 MST 찾으란 거네.# 집의 개수와 길의 개수 N, M# 2번.. 이전 1 2 3 4 ··· 8 다음
