본문 바로가기
728x90

분류 전체보기423

[python] 백준 17835 면접보는 승범이네 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 문제 해결 다익스트라를 이용해야 한다는 것은 쉽게 알 수 있다. 그러나 출발점→도착점 이동을 모두 계산하기에는 계산해야하는 양이 많아 시간복잡도에서 걸린다. 따라서 도착점에서 시작해서 각 출발점까지 얼마나 걸리는지 계산하는 것이 더 빠르다. CODE import sys input = sys.stdin.readline import heapq d.. 2023. 9. 29.
[python] 백준 2533 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 해결 트리를 이용해야하는데 어떻게 이용해야할지 고민을 많이 했다. 부모-자식 중에서 적어도 한 명은 얼리 어답터여야한다. 따라서 dp를 이용해서 부모가 얼리 어답터일 때(dp[parent][1])일 때와 부모가 얼리 어답터가 아닐 때 (dp[parent][0])를 구분을 해서 알고리즘을 풀어나가면 되겠다라는 생각을 한다. dp[i][j]는 i번째 노드가 j상태일때 i번째 밑에 있는 노드.. 2023. 9. 27.
[python] 백준 14267 회사 문화 1 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 해결 노드 하나를 잡고 그것을 루트(root)로 하는 서브트리의 모든 노드에 일정한 점수를 더하는 문제 점수를 더해줄 때 DFS를 쓰면 편하다는 것은 너무 쉽게 알 수 있다. 하지만 노드 하나씩 잡고 서브트리의 모든 노드에 일정한 점수를 더하는 것은 시간복잡도면에서 비효율적이며 시간초과가 나게 되었다. 루트로 잡을 노드에 모두 점수를 주입시키고 1번이 사장이라는 것(트리의 루트)라는 것을 .. 2023. 9. 26.
[python] 백준 20955 민서의 응급 수술 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 문제 해결 먼저 분리되어 있는 그룹이 몇개인지 알아야 한다. 그것을 유니온-파인드를 통해 알 수 있다. 만약 시냅스로 연결된 두 뉴런의 번호 u,v를 받았을 때 이미 같은 그룹에 있으면 더 연결 될 필요가 없으므로 잘라내는데에 연산을 한 번 쓰게 된다. 만약 다른 그룹이면 유니온-파인드를 통해 서로 연결 시킨다. 그룹이 다른 개수 + 이미 연결되어 연결 될 필요가 없는 개수를 합친다음 하나의 중.. 2023. 9. 25.
728x90