본문 바로가기

CS/Algorism

 (99)
[백준] 2212. 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 그리디 문제로, 2가지 방법으로 풀 수 있다. 방법 1: N = 6, K = 2일 때 각 센서 간의 거리들 중 4(N - K)개가 수신 영역이다. 이때 최소한의 수신 영역을 구해야하므로 센서 간의 거리를 오름차순해서 앞에 4개를 더한 것이 답이 된다. import java.io.BufferedReader; import java.io.IOException; import ja..
[백준] 1525. 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 퍼즐에서 0의 위치를 찾아서 4방향(위, 아래, 왼쪽, 오른쪽)으로 bfs를 진행하면 된다. 그런데 해당 퍼즐을 이미 만들었다면 패스하는 로직을 작성해야 한다. 이때 이차원 배열로 비교하면 복잡하기 때문에 다음과 같이 문자열로 변경해서 생각하면 된다. 1 2 3 4 5 6 7 8 0 ➡️ 123456780 그리고 방문 여부뿐만 아니라 몇 번만에 해당 퍼즐을 만들었는지 저장해주어야 하는데 map을 사용하면 방문 여부와 횟수를 간편하게 저장할 수 있다. map의 key는 중복이..
[백준] 5014. 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 평소 많이 풀던 BFS 문제에서 4방향 탐색을 2방향 탐색으로 바꾸기만 하면 된다. 그런데 다음과 같은 치명적인 실수를 해서 틀렸다. BFS를 풀 때 다음과 같이 그래프 범위 밖을 벗어나거나 이미 방문했으면 continue해버렸다. while (!que.isEmpty()) { Integer num = que.poll(); // 도착한 경우 if (num == G) { System.out.println(map[..
[백준] 1987. 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 처음에는 set을 사용해서 매 경우마다 set을 clone하고 새로운 알파벳을 넣어주는 식으로 풀었다. 그런데 시간초과가 났다. 아무래도 매번 컬렉션을 복제하는 것이 시간이 많이 소요되는 거 같다. 따라서 set이 아니라, 알파벳을 담는 일차원 배열을 두면 된다. 즉, visited[] 배열을 두어서 A를 방문했으면 visited[0] = true로 값을 넣어주는 식으로 하면 된다. ..
[백준] 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() ..

티스토리툴바