본문 바로가기

CS

 (140)
[백준] 11403. 경로 찾기 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 DFS와 플로이드 두 가지 방법으로 풀 수 있다. DFS로 푸는 방법은 다음과 같다. 각 정점을 시작으로 이동할 수 있는 다른 정점을 구한다. 이때 dfs를 사용한다. dfs의 결과로 visited[] 배열에 값이 채워지는데, 이때 true이면 이동할 수 있는 것이고, false이면 이동할 수 없는 것이다. 시간 복잡도는 각 정점을 시작으로 dfs를 시작하므로, O(N * (V + E))이다. import java..
[백준] 11724. 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 처음에는 dfs 부분을 다음과 같이 작성했다. private static void dfs(int start) { for (int i = start + 1; i
[백준] 2206. 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 도착점에 가장 빠르게 도착할 수 있는 최단 거리를 구하면 되므로, bfs를 사용하면 된다. 그런데 벽을 한 번 부술 수 있다는 것이 관건이다. 처음에는 다음과 같이 풀었다. Point에 x, y 위치와 지금까지 벽을 부순 적이 있는지 없는지를 의미하는 boolean destroy 변수를 정의했다. 그래프를 탐색하며 벽이 아니면 이동하고, 벽이면 지금까지 벽을 부순 적이 없..
[백준] 2295. 세 수의 합 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net a + b + c = d에서 가장 큰 d의 값을 찾는 문제이다. 주 포인트는 a + b = d - c로 생각해야 한다. 즉, 이중 반복문으로 a + b의 모음들을 만들고, 이분 탐색으로 d - c가 a + b 모음들에 포함되나 확인하면 된다. 그런데 이때 d - c의 값이 a + b의 모음에 포함되나 확인할 때, ArrayList.contain() ..
[백준] 2003. 수들의 합2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터로 풀면 된다. 주요 로직은 다음과 같다. 예를 들어 start가 2, end가 4이면 arr[2] + arr[3]의 합이 sum이 된다. 따라서 초기 값으로 start는 0, end는 1, sum은 arr[start]를 주었다. sum == m인 경우 카운트한다. sum
[백준] 2467. 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이 문제는 이분탐색으로도 풀 수 있고, 투포인터로도 풀 수 있다. 이분탐색 수를 두개씩 더해서 그 절댓값이 가장 작은 것이 답이 된다. 이때 이중 반복문으로 수를 더하면 O(N^2)의 시간 복잡도가 발생한다. 따라서 이분탐색으로 풀어야 한다. (시간 복잡도: O(N * logN)) 배열을 정렬한 후 특정 인덱스를 기준으로, 해당 인덱스보다 큰 인덱스들을 범위로 이분탐색하여, 더한 값의 절댓값..
[백준] 18869. 멀티버스 Ⅱ https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 같은 우주임을 판별하려면 행성들을 정렬했을 때, 기존 인덱스 값을 기준으로 비교하면 된다. ex, 행성1: 10, 30, 20 ➡️ 정렬 후 인덱스 값: 0, 2, 1 ex, 행성2: 30, 20, 10 ➡️ 정렬 후 인덱스 값: 2, 1, 0 ex, 행성3: 20, 50, 30 ➡️ 정렬 후 인덱스 값: 0, 2, 1 결과: 행성1과 행성3은 균등함 따라서 기존 배열(ex, 10, 30,..
[백준] 16401. 과자 나눠주기 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net m명에게 과자를 나눠줄 수 있는 과자의 최대 길이를 구해야 한다. 따라서 과자들을 정렬한 후에 이분탐색으로 그 최대 길이를 찾으면 된다. 주의할 점은 다음과 같다. 하나의 과자를 여러 조각으로 나눌 수 있다(예제 2 참고). 따라서 주어진 과자 갯수보다 조카 갯수가 더 많아도 가능하다. 따라서 과자들을 탐색하면서..

티스토리툴바