본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 1450 냅색문제 (Swift) 문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이 문제는 dfs + 이분탐색으로 풀이할 수 있습니다. n이 최대 30이므로, 모든 경우의 수를 고려하면 $2^30$ = 약 10억의 비용이 드므로 시간초과가 나올 것입니다. 어떻게 시간복잡도를 줄일 수 있을까요? n을 반씩 나누어서 시간복잡도를 줄일 수 있습니다. 예를 들어 [1, 2, 3, 4] 라는 무게가 주어졌다면, [1, 2]와 [3, 4]를 나누어서 가방에 넣을지 말지를 정해..
[BOJ] 백준 1644 소수의 연속합 (Swift) 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 투 포인터 알고리즘으로 풀 수 있는 문제입니다. 1806 부분합 문제와 거의 동일하고, 소수만 구해주면 되는 문제입니다. 먼저 n보다 작거나 같은 소수들을 모두 구해주어야 합니다. 저는 에라토스테네스의 체 알고리즘을 사용하여 구했습니다. 그 이후 이 소수들에 대해서 투 포인터를 사용하여 부분합을 구해줍시다. 왼쪽에 포인터를 2개 두고, 소수들에 대해서 n보다 크거나 같아질 때 까지, 왼쪽의 포인터를 왼쪽으로 하나씩 옮기면서 더해줍시다. n이랑 같아졌다면, count를 1 증가시켜줍시다. n보다 커졌다면, ..
[BOJ] 백준 1806 부분합 (Swift) 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 투 포인터 알고리즘으로 풀 수 있는 문제입니다. 양 끝에 포인터를 놓는 것이 아닌 왼쪽에 두개의 포인터를 두어서 풀이해야 합니다. 합이 s이하라면 하나의 포인터를 계속해서 늘려주고, s이상이 된다면 또 다른 하나의 포인터를 늘려주어서 길이를 구할 수 있습니다. 소스코드 후기 양 끝에 포인터를 두는 방식으로 투 포인터 알고리즘을 써왔었는데, 한쪽에서 출발하는 방법도 있다는 ..
[BOJ] 백준 2470 두 용액 (Swift) 문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 투 포인터 알고리즘으로 풀이할 수 있는 문제입니다. 용액의 특성 값을 오름차순으로 정렬해주었습니다. 포인터 두개를 첫번째 인덱스와 마지막 인덱스로 두었습니다. 이 포인터가 가르치는 요소의 합이 0보다 작다면? 오름차순으로 나열되어있기 때문에, 왼쪽 포인터를 오른쪽으로 한 칸 이동시켜줍시다. 0보다 크다면? 오른쪽 포인터를 왼쪽으로 한 칸 이동시켜줍시다...
[BOJ] 백준 3273 두 수의 합 (Swift) 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 n의 갯수가 최대 10만이기 때문에, 이중 for문으로 풀이할 시 시간초과$(O(n^2))$가 날 것입니다. 따라서 정렬$(O(nlogn))$ + 투 포인터 $(O(n))$ 알고리즘으로 풀이할 수 있습니다. 오름차순으로 정렬해 준 뒤, 첫번째 index를 start, 마지막 index를 end로 설정해줍시다. array[start]..
[BOJ] 백준 1956 운동 (Swift) 문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 합이 가장 작은 사이클을 구하는 문제입니다. 모든 경로를 확인해야 하므로 플로이드 워셜 알고리즘을 사용하여 풀이할 수 있습니다. 사이클이 되는지 여부는 어떻게 알 수 있을까요? 단순히 1 -> 3 으로 갈 수 있고 3 -> 1로 갈 수 있으면 사이클이 된다고 할 수 있습니다. 모든 경로에 대해 사이클이 되는지 확인하고, 가장 작은 값을 출력해주면 됩니다..
[BOJ] 백준 11404 플로이드 (Swift) 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 문제명 처럼 모든 노드에서 최소한의 거리를 구하는 플로이드 워셜 알고리즘으로 풀이할 수 있는 문제입니다. 플로이드 워셜 알고리즘의 기본만 작성하면 풀이할 수 있는 문제입니다. 단 한가지에 주의해야 하는데, 시작 도시와 도착 도시를 연결하는 노선이 1개가 아닐 수 있기 때문에, 비용을 저장할 때, 비용이 가장 작은 비용으로 저장해주어야 합니다. 소스코드 후기 다익스트라, 벨만포드 보다는 ..
[BOJ] 백준 11657 타임머신 (Swift) 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 음의 간선이 있기 때문에 다익스트라 알고리즘으로는 풀이할 수 없습니다. 벨만-포드 알고리즘을 사용해서 풀 수 있습니다. n - 1 번 반복하여, 모든 간선에 대해 경로를 최소값으로 갱신이 가능한지 확인해준다면 음의 간선이 있어도 최단 경로를 구할 수 있습니다. n - 1 번 반복한 후, 한 번 더 최소값으로 갱신이 가능하다면,..
반응형

티스토리툴바