솧로그

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..

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는 중복이..

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[..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 처음에는 set을 사용해서 매 경우마다 set을 clone하고 새로운 알파벳을 넣어주는 식으로 풀었다. 그런데 시간초과가 났다. 아무래도 매번 컬렉션을 복제하는 것이 시간이 많이 소요되는 거 같다. 따라서 set이 아니라, 알파벳을 담는 일차원 배열을 두면 된다. 즉, visited[] 배열을 두어서 A를 방문했으면 visited[0] = true로 값을 넣어주는 식으로 하면 된다. ..

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..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 도착점에 가장 빠르게 도착할 수 있는 최단 거리를 구하면 되므로, bfs를 사용하면 된다. 그런데 벽을 한 번 부술 수 있다는 것이 관건이다. 처음에는 다음과 같이 풀었다. Point에 x, y 위치와 지금까지 벽을 부순 적이 있는지 없는지를 의미하는 boolean destroy 변수를 정의했다. 그래프를 탐색하며 벽이 아니면 이동하고, 벽이면 지금까지 벽을 부순 적이 없..

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() ..

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

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이 문제는 이분탐색으로도 풀 수 있고, 투포인터로도 풀 수 있다. 이분탐색 수를 두개씩 더해서 그 절댓값이 가장 작은 것이 답이 된다. 이때 이중 반복문으로 수를 더하면 O(N^2)의 시간 복잡도가 발생한다. 따라서 이분탐색으로 풀어야 한다. (시간 복잡도: O(N * logN)) 배열을 정렬한 후 특정 인덱스를 기준으로, 해당 인덱스보다 큰 인덱스들을 범위로 이분탐색하여, 더한 값의 절댓값..

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,..