알고리즘 (46) 썸네일형 리스트형 [BOJ 14567] 선수과목 (Prerequisite) (c++) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite)3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.www.acmicpc.net풀이A #define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;int n, m;int arr[1001];vector> v;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i > a >> b; v.push_back({ a,b }.. [BOJ 2512] 예산(c++) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 풀이 이진탐색 문제인데 idx값이 아닌 밸류값을 기준으로 잡아 문제를 풀었다. 각 지방의 요청 금액 중에 가장 높은 금액을 end, 0을 start로 잡고 이진탐색을 돌리면 쉽게 해결되는 문제이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int n, sum, m; vector v; int .. [BOJ 1277] 발전소 설치 (c++) https://www.acmicpc.net/problem/1277 1277번: 발전소 설치 첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발 www.acmicpc.net 풀이 각 노드마다 거리를 구해 m 보다 작으면 벡터에 (vv[i] = ({j, cost}))추가한다. w만큼 연결된 전선은 vv[i] = {(j, 0)}을 추가한다. 그 후 다익스트라 알고리즘을 이용해 1번 노드에서 n번 노드까지의 최단 거리를 구한다. #define _CRT_SECURE_NO_WARNINGS #include #include .. [BOJ 11265] 끝나지 않는 파티(c++) https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 풀이 다익스트라 알고리즘을 이용해 모든 노드 간의 최단 거리를 구하고 2차원 배열에 저장한다. m개의 반복을 하며 노드와 cost를 비교하며 결과를 출력한다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int n, m; int dist[500][5.. [BOJ 2015] 수들의 합 4(c++) https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 풀이 이중for문으로 푸니까 O(n^2)으로 시간초과가 났다. arr[i]-arr[j] = k 인걸 이용해 arr[i] - k = arr[j]로 arr[i] - k가 arr[j]인 경우를 찾아 구한다. map을 이용한다. for문으로 m[arr[i] - k]인 경우를 result에 더하고 m[arr[i]]++를 해서 arr[j]인.. [BOJ 11660] 구간 합 구하기 5(c++) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 map[i][j] += map[i-1] + map[i][j+1] - map[i-1][j-1] 을 통해 map[0][0]부터 map[i][j] 까지의 구간 합을 배열에다 저장한다. -> map[i][j]에다가 map[0][0]부터 map[i-1][j]까지의 합, map[i][j-1]까지의 합을 더하고 map[i-1][j-1]까지의 합은 중복됐으므로 m.. 이전 1 ··· 3 4 5 6 다음
