최소 신장 트리를 구하는 프림 알고리즘, 크루스칼 알고리즘 재활하기1

1. 문제 16398번: 행성 연결 (acmicpc.net) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 2. 풀이 최소 신장 트리의 비용을 구하는 알고리즘은 기본이 프림 알고리즘이랑 크루스칼 알고리즘 크루스칼 알고리즘이 간단해서 기억이 잘 난다.. 1) (가중치, 간선) 형태로 edges에 넣어 가중치 기준으로 오름차순 정렬하고 2) 가중치가 적은 간선부터 순회하여 정점 a와 정점 b가 서로 parent가 다르다면, union 시키고 해당 간선을 선택하고 간선의 가중치를 더해간다. 3) parent가 같다..

• format_list_bulleted 최소 스패닝 트리
• · 2023. 4. 18.
• textsms

다익스트라 알고리즘 조금 어려운 문제로 오랜만에 재활하기1

1. 문제 20007번: 떡 돌리기 (acmicpc.net) 20007번: 떡 돌리기 첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N) 두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주 www.acmicpc.net 2. 풀이 다익스트라는 기본 구현 그대로.. 하면 되는데.. 문제 조건을 올바르게 생각해야한다 1) "하루에 x보다 먼 거리를 걷지 않고, 거리가 가까운 집부터 방문한다" 거리가 가까운 집부터 방문한다고 하니까, 그래서 다익스트라로 얻은 최단거리 배열을 오름차순으로 정렬해줘서, 작은 거리부터 방문해줘야한다. 2) "잠은 꼭 본인 집에..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 4. 16.
• textsms

다익스트라 알고리즘 응용 - 다른 정점에서 목적지로 되돌아오는 최단거리 구하는 방법

1. 문제 1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 이 문제의 핵심은 x번 마을에서 다시 i = 1,2,...번 마을로 되돌아오는 최단 거리가 필요하다는 점이다. 다익스트라 알고리즘은 출발 정점 start에서 다른 정점 1,2,...,n번 까지 가는 최단 경로를 구해주는 알고리즘이지 1,2,...,n번 각각의 정점에서 start로 되돌아오는 최단 경로를 구해주는 알고리즘은 아니다 이걸 할려면 다익스트라를 n번 해야하는데..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 4. 16.
• textsms

알고리즘 테크닉 - 좌표압축(grid compression)

1. 좌표압축이란 정점 번호가 1에서 $10^{9}$사이의 값으로 이루어져 있는 그래프가 하나 주어질때, 1번 정점에서 시작하여, 방문 가능한 서로 다른 노드의 수를 구하는 프로그램을 작성하세요. 일반적인 DFS 탐색으로는 1번 정점에서 N번 정점까지 번호가 매겨져 있어서, 큰 문제 없이 크기가 N인 visited 배열과 간선 정보를 나타내는 인접 리스트를 만들어 해결할 수 있습니다. 하지만 위와 같이 정점 번호가 1번에서 $10^{9}$사이로 주어진다면, visited 배열을 만드는 순간 메모리 초과로 일반적인 방법으로는 해결하기 어렵다. 그런데 조금만 생각해보면... 주어진 정점 번호를 오름차순으로 나열할때, 1,4,6,7,30,2000,$10^{9}$밖에 없으며.. 이 정점들의 번호를 1번부터 순서..

• format_list_bulleted 압축 알고리즘
• · 2023. 4. 14.
• textsms

팩토리얼 끝에서 가장 먼저 나오는 0이 아닌 수를 찾는 방법

1. 문제1 2553번: 마지막 팩토리얼 수 (acmicpc.net) 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net 2. 풀이 저번에 풀었던 문제와는 다르게 팩토리얼 계산한 값에서 마지막에서 0이 아닌 처음으로 다른 수가 나올때, 그 수를 출력하는 문제 쉽게 생각할 수 있는 방법은..? 저번에 배운 마지막에 0이 나오는 개수를 구하는 방법을 응용하기 마지막에 나오는 0의 개수 k를 구하고, n!을 계산하여 prod라고 저장한 다음에... prod를 $10^{k}$로 나눠준다면? 일의 자리가 정답이 된다 일의 자리는 어떻게 구해? str()로 바꿔서 -1번을 뽑아? 아니 str()로 바꾸는게 생각보다 시간 많이 먹어 ..

• format_list_bulleted 정수론
• · 2023. 4. 12.
• textsms

투 포인터 올바르게 생각하기 기본문제로 연습2

1. 문제 2018번: 수들의 합 5 (acmicpc.net) 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 2. 풀이 이전에 풀이한 방식대로, 포인터 i,j를 잡고 구간 [i,j]의 합이 N이 되는지 아닌지를 검사하면 된다 자연수 N이 연속된 자연수의 합으로 나타낼려면 결국 N보다 작거나 같은 자연수의 합으로 나타낼 수밖에 없다 그러므로 1부터 n까지 natural이라는 배열을 만들었고 (정렬은 왜 한건지 모르겠지만..) 포인터 i,j를 잡은 다음, 초기값 natural[0]로 잡는다..

• format_list_bulleted 투 포인터 알고리즘
• · 2023. 4. 12.
• textsms