정신 차리고 살자

문제 (https://www.acmicpc.net/problem/2887) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 입력으로 행성들의 좌표가 들어온다. 이 좌표들로 모든 행성 사이의 거리와 연결 비용을 구한다면 시간 초과가 발생한다. (N ≤ 100,000) 따라서, 행성들의 x, y, z 좌표를 각각 정렬한 후 반복문을 돌며 각 좌표에서 인접한 행성들 간의 비용을 구한다. 예제와 같이 N이 5라면 총 12개의 간선 정보가 생성된다. N이 6이라면 15개이다. 즉 (N-..

문제 (https://www.acmicpc.net/problem/1939) 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이번 스터디 주제인 이분탐색으로 해결하려고 했으나 도저히 모르겠어서 크루스칼로 해결했다 🤯 중량의 최댓값을 구해야 하는 문제이므로 입력을 받은 후 간선의 크기를 기준으로 내림차순 정렬했다. 노드들을 합쳐가면서 매번 마지막 입력으로 들어온 두 섬이 연결되었는지 확인해야 한다. 연결이 되었다면, 연결된 모든 노드들 간의 간선들 중 가..

문제 (https://www.acmicpc.net/problem/3020) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제를 읽고 고민을 하다가.. 예전에 푼 문제에서 lower_bound와 upper_bound를 사용했던 게 생각이 났다. 구현을 해봤지만 시간 초과가 발생했고 구글링으로 약간의 힌트를 얻은 후 구현했다. 석순과 종유석을 각각 입력받고 정렬한다. 정렬 후, 1부터 h까지 반복하며 각 높이일 때 몇 개의 장애물을 파괴하는지를 구한다. 이때 lower_bound를 사용하는 것이다. 장애물의 개수..

문제 (https://www.acmicpc.net/problem/4386) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 비용으로 모든 점을 연결하는 MST 알고리즘을 사용한 문제이다. Union-find를 사용하는 크루스칼 알고리즘으로 문제를 해결했다. 이 문제에서는 점 사이의 거리가 주어지지 않고 별의 좌표가 각각 주어지기 때문에 주어진 좌표들로 점 사이의 거리를 구해주었다. (Line 50~61) 위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다. [소스코드] 더보기 2021-12..

문제 (https://www.acmicpc.net/problem/11779) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 출발 도시에서 도착 도시까지의 최소 비용을 구하는 일반적인 다익스트라 문제이다. 다른 문제들과 차이점은 최소 비용뿐만 아니라 경로에 포함되어있는 도시의 개수와 방문하는 도시 번호도 출력해야 한다. 따라서 배열을 생성하여 각 도시에 도달하기 위해서는 몇 번 도시에서 출발해야 하는지를 기록했다. 예를 들어, route[a] = b는 "a번에 최소로 도달하기 위..

문제 (https://www.acmicpc.net/problem/1484) 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net (현재 몸무게)^2 - (예전 몸무게)^2 = 찐 몸무게 1부터 g까지의 모든 수를 배열에 담아두고 투 포인터를 실행했다. end는 현재 몸무게를 가리키는 포인터이고 start는 예전 몸무게를 가리키는 포인터로 설정했다. 위 식대로 찐 몸무게를 구한 후 구한 값이 g와 같다면 정답을 담아두는 배열에 삽입한다. g보다 작다면? 찐 몸무게를 더 늘려야 하므로 end(현재 몸무게)를 증가 g보다 크거나 같다..

문제 (https://www.acmicpc.net/problem/1644) 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 2 이상 N 이하의 모든 소수를 벡터에 삽입한다. 2. start부터 end까지의 합에 따라 1번에서 구한 벡터 위에서 start와 end를 움직인다. 2-1. 합이 n보다 작다면? end 증가 2-2. 합이 n보다 크거나 같다면? start 증가 2-3. 합이 n과 같다면? ans 증가 [소스코드] 더보기 2021-12-28 Gold 3 - 수학 - 정수론 - 두 포인터 - 소수 판정 - 에라토스테네스의 체

문제 (https://www.acmicpc.net/problem/2470) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터 알고리즘을 사용하여 해결한 문제이다. start를 맨 앞, end를 맨 뒤에 두고 움직이기 시작한다. start와 end가 가리키는 값을 더하여 최솟값인지 절댓값을 취해 비교한다. 더한 값이 0보다 작다면? 숫자를 크게 하여 0에 가까워져야 하므로 start 증가 더한 값이 0보다 크거나 같다면? 숫자를 작게 하여 0에 가까워져야 하므로 end..

문제 (https://www.acmicpc.net/problem/3107) 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 출력은 무조건 4 글자씩 8번 출력되어야 하고, 콜론은 7개여야 한다. 1. 입력받은 문자열을 ':' 기준으로 분리시킨다. 2. 분리된 문자열을 담고 있는 벡터의 크기가 8보다 작다면 2번 규칙이 적용된 것이다. 따라서 2번 규칙이 적용된 곳에 문자열 "0000"을 부족한 만큼 삽입한다. 3. 2번에서 완성한 벡터의 문자열 중 0이 생략된 문자열에 0을 채워준다. [소스코드] 더보기 2021-12-28 Gold 5 - 구현 -..

문제 (https://www.acmicpc.net/problem/1990) 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 소수&팰린드롬을 푼 직후에 풀어서 처음엔 쉽다고 생각했는데.. 계속 시간 초과가 발생했다. 1부터 1억까지의 숫자들 중 소수이면서 팰린드롬인 숫자를 모두 출력해보았더니 최댓값이 10,000,000을 넘지 않았다! (캡처를 못해두었는데 대략 9천7백만 정도?) 따라서 반복문의 최댓값을 10,000,000으로 설정하고 숫자의 범위가 b를 넘어가면 반복문을 탈출했다. [소스코드] ..