본문 바로가기
반응형

분류 전체보기

 (395)
[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 번 반복한 후, 한 번 더 최소값으로 갱신이 가능하다면,..
[BOJ] 백준 13549 숨바꼭질 3 (Swift) 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 이 문제는 간선의 비용이 0 또는 1이기 때문에 0-1 BFS를 사용하여 풀이할 수 있습니다. 또는 다익스트라 알고리즘을 사용해도 무방합니다. 0-1 BFS로 풀이를 할 때, 간선의 비용이 0인것 부터 처리해주기 때문에 queue보다는 deque 자료구조가 더 어울립니다. insert 메서드로 큐에 앞부분에 삽입시켜주었는데 이는 시간복잡도가 $O(n)$..
[BOJ] 백준 1504 특정한 최단 경로 (Swift) 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 다익스트라 알고리즘을 활용하여 풀 수 있는 문제입니다. 다익스트라 알고리즘으로 특정 노드에서 어느 노드까지의 최단 거리를 알 수 있습니다. v1과 v2를 무조건 지나야 한다면, 경로는 2개가 나올 것 입니다. start -> v1 -> v2 -> N start -> v2 -> v1 -> N 이 두가지 경로 중 최소 값을 출력해 주면 됩니다. ..
반응형

티스토리툴바