기간 제한이 있는 과제들에서 최대 가치를 얻는 그리디 알고리즘

13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..

• format_list_bulleted 그리디 알고리즘
• · 2024. 6. 4.
• textsms

우선순위가 2개 이상인 다익스트라 알고리즘 연습

1. 문제1 16167번: A Great Way (acmicpc.net) 16167번: A Great Way 첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R www.acmicpc.net 2. 풀이 다익스트라 알고리즘으로 최단거리만을 요구하는 문제가 기본문제고, 최단거리면서, 그러한 거리가 여러개인 경우 거쳐가는 노드가 최소가 되는 경로를 찾으라고 한다면? 접근 방법은 distance 배열 설정을 조금만 바꿔주면 된다 distance[v]를 출발점에서 v까지 가는데 가는 [비용, 거친 노드 수]로 정의해주자 "비용이 먼저 최소가 되면서..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 7. 18.
• textsms

다익스트라 응용하기 - 시작 정점은 여러개일 수도 있다

1. 문제 14221번: 편의점 (acmicpc.net) 14221번: 편의점 처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000) www.acmicpc.net 2. 풀이 집에서 편의점까지 거리가 가장 가까운, 집의 번호를 출력하는 문제다. 간단하게 생각하면, 집이 p개 있고 편의점이 q개 있는데.. p개의 점 각각에 대하여, 다익스트라 알고리즘을 수행하면 p개의 다익스트라 배열이 나오고.. 여기서 편의점 q개의 점에 대해 거리를 구해보고 거리가 가장 가까운 점을 찾으면 될것이다 근데 이렇게 하면 다익..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 4. 17.
• 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

[Java]자바로 구현하는 절댓값 우선순위 큐

1. 문제 배열에 다음과 같은 연산을 할 수 있습니다. 배열에 정수 x (x ≠ 0) 를 넣습니다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거합니다. ( 절댓값이 가장 작은 값이 여러개일 때는, 그 중 가장 작은 수를 출력하고, 그 값을 배열에서 제거합니다. ) 비어있는 배열에서 시작하여 입력된 연산을 실행하는 프로그램을 작성해보세요. 2. 풀이 자바하면 클래스 어렵게 생각하지 말고 필요하다면 클래스를 구현해서 사용하라 절댓값을 만드는 클래스를 구현해야하는데, 문제는 절댓값을 기준으로 오름차순 정렬을 할 수 있어야하고 중요한건 절댓값만 저장하는게 아니라 원본도 저장해야한다. 그래야 우선순위 큐에서 출력할때 원본값을 출력할 수 있으니까 import java.util.Scanner;..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 22.
• textsms

[Java]우선순위 큐 응용 - MN개의 조합에서 조건을 만족하는 k번째 수를 찾는 빠르게 찾는 방법 1편

1. 문제 n개의 숫자로 이루어진 수열과 m개의 숫자로 이루어진 수열이 주어졌을 때, 각 수열에서 정확히 원소를 하나씩만 뽑아 나올 수 있는 모든 쌍들을 모두 구하고, 그 값들을 오름차순이 되도록 나열했을 때의 k번째 쌍의 두 수의 합을 구하는 프로그램을 작성해보세요. n,m은 1이상 10만 이하의 자연수 k는 1이상 min(nm, 10만)이하 2. 풀이 가장 쉽게 생각할 수 있는 방법은 mn개의 모든 조합을 만든 다음에 우선순위 큐에 모두 집어 넣고, k번째 빠지는 수를 출력하면 된다 근데 뭐 당연히 시간초과 + 메모리 초과임 m과 n이 10만인데 시간복잡도가 얼마냐 이거 O(M + N + MNlogMN + KlogMN)인가..? 아무튼 O(MN)으로 생각하는 순간 10만*10만 = 100억으로 오바다..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 21.
• textsms