본문 바로가기
반응형

BOJ

 (326)
[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 이 두가지 경로 중 최소 값을 출력해 주면 됩니다. ..
[BOJ] 백준 1753 최단경로 (Swift) 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 알고리즘을 활용하는 문제입니다. 다익스트라에 대한 이해가 없다면 매우 풀기 어려울 것 같습니다. 다익스트라 알고리즘을 작성하면 바로 풀리는 문제입니다. 소스코드 후기 다익스트라 알고리즘을 이전에 공부했었는데, 막상 풀려니깐 또 까먹었습니다. 다시 공부하고 풀이했는데, 어렵네요...
[BOJ] 백준 1707 이분 그래프 (Swift) 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 먼저, 이분 그래프에 대해 알아야 풀 수 있습니다. 이분 그래프는 나와 인접한 노드는 다른 집합이여야 합니다. 구글링해서 이해하기 쉬웠던 방법은 나와 인접한 노드는 다른 색깔을 칠해주어야 한다. 라고 이해하였습니다. 그렇다면 DFS 혹은 BFS로 탐색하면서, 방문할 때 색을 칠해주는 방법으로 구현해야겠다고 생각했습니다. 인접 노드가 방문하지 않은 노드라면 나와 다른 색을 칠해주었습니다...
반응형

티스토리툴바