본문 바로가기

Algorithm19

다익스트라 알고리즘 다익스트라(Dijkstra) 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 우선순위 큐를 사용하여, 각 정점까지의 최단 경로를 빠르게 계산할 수 있다. 문제 설명주어진 그래프에서 1번 정점에서 모든 다른 정점으로의 최소 거리 비용을 구하고, 그 결과를 출력하는 프로그램을 작성해야 한다. 만약 특정 정점으로 가는 경로가 존재하지 않으면 impossible을 출력한다.입력 설명첫 번째 줄에 정점의 수 N(1다음 M개의 줄에 각 간선 정보(출발 정점, 도착 정점, 거리 비용)가 주어진다.출력 설명1번 정점에서 2번 정점부터 차례대로 각 정점까지의 최단 거리를 출력한다. 만약 특정 정점으로 갈 수 없는 경우는 impossible을 출력한다. 입력 예제6 91.. 2024. 10. 21.
최대 수입 스케쥴(PriorityQueue 응용문제) 현수는 유명한 강연자이다. N개의 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다. 각 기업이 요청한 D와 M을 바탕으로 가장 많은 돈을 벌 수 있도록 강연 스케줄을 짜야한다. 단, 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다. 입력 설명첫 번째 줄에 자연수 N(1다음 N개의 줄에 각 기업이 제시한 강연료 M(1(M은 강연료, D는 해당 강연을 해야 하는 마감 기한이다)출력 설명첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.입력 예제 650 220 140 260 330 330 1 출력 예제 150 문제 풀이 과정우선순위 큐 사용: 각 날짜마다 가능한 강연들 중 가장 많은 강연료를 얻기 위해 우선순위 큐(PriorityQueu.. 2024. 10. 21.
Lv5 멸종위기의 대장균 찾기(SQL) 문제 설명대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화되어 나온 개체를 자식 개체라고 한다. 이 문제는 각 세대별로 자식이 없는 대장균 개체의 수를 구하고, 세대별로 오름차순으로 출력하는 것이다. 테이블 구조대장균들의 정보를 담고 있는 ECOLI_DATA 테이블의 구조는 다음과 같다.ID: 대장균 개체의 ID (PRIMARY KEY)PARENT_ID: 부모 대장균의 ID (최초 대장균은 NULL 값을 가짐)SIZE_OF_COLONY: 대장균 집단의 크기DIFFERENTIATION_DATE: 분화된 날짜GENOTYPE: 대장균의 형질문제 요구사항각 세대별로 자식이 없는 대장균의 수를 구하고, 결과는 세대에 대해 오름차순으로 정렬해야 한다. 모든 세대에는 자식이 없는 개체가 적어도.. 2024. 10. 21.
회의실 배정(Greedy) 한 개의 회의실을 사용하고자 하는 n개의 회의가 있을 때, 각 회의의 시작 시간과 끝나는 시간이 주어진다. 이때, 회의가 겹치지 않게 하면서 회의실을 최대한 많이 사용할 수 있도록 배정해야 한다. 단, 한 회의가 끝나는 동시에 다른 회의가 바로 시작될 수 있으며, 중간에 중단될 수 없다. 문제 해결 아이디어이 문제는 그리디 알고리즘으로 해결할 수 있다. 끝나는 시간이 가장 빠른 회의를 먼저 선택하는 것이 최적의 해를 보장하는 방법이다. 이렇게 해야, 다음 회의가 겹치지 않게 최대한 많이 배정할 수 있다.1. 정렬 기준회의의 끝나는 시간을 기준으로 오름차순 정렬한다.끝나는 시간이 같다면 시작 시간을 기준으로 오름차순 정렬한다.2. 그리디 선택첫 번째 회의를 선택한 후, 선택된 회의의 끝나는 시간 이후에 시.. 2024. 10. 20.
씨름 선수(Greedy) 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.” N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요. 현수는 씨름 선수 선발을 위해 공고를 냈으며, 총 N명의 지원자가 지원하였다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있으며, 선발 원칙은 다음과 같다."한 지원자를 다른 모든 지원자와 비교하여, 키와 몸무게 모.. 2024. 10. 19.
피자 배달 거리(삼성 SW 역량평가 기출/DFS) 이 문제는 DFS(깊이 우선 탐색)을 활용하여 조합을 구하는 문제이다. N x N 크기의 도시에서 M개의 피자집을 선택하여 도시의 피자 배달 거리를 최소화하는 것이 목표다. 각 집은 도시의 여러 피자집 중 하나와 연결되며, 그 집에서 가장 가까운 피자집까지의 거리를 계산해, 모든 집의 배달 거리 합이 최소가 되도록 해야 한다. 문제 설명도시 지도는 N x N 크기로 주어지며, 각 칸은 빈칸(0), 집(1), 피자집(2)으로 표현된다. 각 집마다 여러 피자집과의 거리가 존재하지만, 그중 최소 거리가 해당 집의 피자 배달 거리가 된다. 예를 들어, (1, 2)에 있는 집과 (2, 3)에 있는 피자집의 거리는 |1-2| + |2-3| = 2이다.이 문제는 도시에서 M개의 피자집을 선택하여, 전체 도시의 피자 .. 2024. 10. 19.

티스토리툴바