Algorithm475 [파이썬] 백준 16562 : 친구비 (골드4) [파이썬] 백준 16562 : 친구비 (골드4)https://www.acmicpc.net/problem/16562풀이방향성 생각기본 유니온 파인드 문제입력을 받아서 부모가 다르면 유니온을 진행한다.parent 배열을 바탕으로 각 그룹의 최소 비용을 모두 구한다.최소 비용이 K보다 작으면 비용 출력.전체코드from collections import defaultdict as ddimport sysinput = lambda : sys.stdin.readline().rstrip()def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a]N,M,K = map(int,input().split())costs = [.. 2024. 6. 16. [파이썬] 프로그래머스 : 등산코스 정하기 (레벨3) [파이썬] 프로그래머스 : 등산코스 정하기 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/118669풀이**방향성 생각기본 다익스트라 문제.시작점에서 봉우리에 도착하는 최소 강도를 구한다.현재 경로까지 강도를 힙에 넣어주면서 간선을 이동하면서 최대값을 갱신하는 경우에 최대 강도를 변경한다.입력 크기가 큰 편이라서 각 Node마다 다익스트라를 돌리면 $(NlogN)^2$라서 터져버린다.시작점 gates를 한 번에 힙에 넣고, summits에 도달할 때 마다 정답 후보에 넣는다.마지막에 answer을 정렬해주고 리턴하면 끝summits이 $50000$이라서 summits 유무를 list 대신 set으로 관리한다.또, edges의 수가 많아서 .. 2024. 6. 13. [파이썬] 프로그래머스 : 산 모양 타일링 (레벨3) [파이썬] 프로그래머스 : 산 모양 타일링 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/258705풀이방향성 생각유명한 타일링 DP. 개꿀문제각 지점에 대해서 가능한 경우의 수를 DP로 채운다.점화식을 찾아서 바텀업으로 풀이.탑다운으로 풀기에는 바로 분할해서 보기 쉽지 않다.이전 타일 상태에서 경로만 지정해주면 바텀업이 쉽다.$N=4$, $tops=[1,1,0,1]$의 경우에는 DP 테이블을 다음과 같이 나타낼 수 있다.0 1 0 1 0 0 0 1 01 1 1 1 1 1 1 1 11은 타일이 깔린 부분, 0은 타일이 없는 부분초기 상태 DP를 채워보면0 3 ? ? ? ? ? ? ?1 2 * ? ? ? ? ? ?CASE1) 2 옆의 아래쪽.. 2024. 6. 12. [파이썬] 프로그래머스 : 괄호 회전하기 (레벨2) [파이썬] 프로그래머스 : 괄호 회전하기 (레벨2)https://www.acmicpc.net/problem/번호풀이방향성 생각큐 스택형태입력 문자열의 s의 크기 : $N=1000$모든 경우에 대해서 순회를 해서 체크를 해주면 된다.전체코드from collections import dequedef solution(string): # 매칭 되면 스택 터뜨리기, 아니면 스택에 추가하기 def check(sub_string): stack = [] for s in sub_string: if stack: e = stack[-1] if ((e,s) == ('[',']')) or ((e,s)==('{','}'.. 2024. 6. 11. 이전 1 ··· 42 43 44 45 46 47 48 ··· 119 다음