정신 차리고 살자

링크 (https://www.acmicpc.net/problem/16398) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 무난한 최소 스패닝 트리 문제이다. MST 문제를 항상 크루스칼 알고리즘으로만 풀었는데 이번엔 프림 알고리즘으로 풀어봤다! 정답이 int 범위보다 클 수 있으므로 long long으로 해주어야 한다. [소스코드] 더보기 2022-03-02 Gold 4 - 그래프 이론 - 최소 스패닝 트리

문제 (https://www.acmicpc.net/problem/14621) 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다. 특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다. 남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다. 만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(B..

문제 (https://www.acmicpc.net/problem/1253) 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 처음엔 검사하는 숫자보다 작은 수들로만 검사하는 숫자가 만들어진다고 생각했다. 하지만 음수도 가능하기 때문에 -4 -2 -2 같은 케이스가 존재한다. (-4가 좋은 수) 또한 자기 자신은 서로 다른 두 수에 해당하면 안 되므로 예외 처리를 해주어야 한다. 나는 그냥 for문을 돌 때마다 원본 벡터를 복사한 벡터에 해당 숫자를 erase로 제거하여 사용했다. - n이 2보다 작거나 같으면 다른 수 두 개의 합으로 나타..

문제 (https://www.acmicpc.net/problem/3078) 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우로 해결한 문제!!! 문제 설명이 엄청 길지만,, 요약하자면 좋은 친구의 정의는 아래와 같고 좋은 친구가 몇 쌍 있는지 출력하면 된다. 좋은친구: 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 pair (등수, 이름의 길이) 형태로 입력을 받았다. i번째(i등) 학생은 크기가 k인 창문 내의 다른 학생들 중, 이름의 길이가 같은 학생과 좋..

문제 (https://www.acmicpc.net/problem/2096) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net DP + 슬라이딩 윈도우로 해결한 문제이다. 두 알고리즘 모두 취약해서...ㅎㅎ 다른 코드를 참고하여 풀었다. 크기가 3인 배열들 minArr, maxArr, minTmp, maxTmp을 사용했는데, minTmp, maxTmp는 현재 행 이전까지의 결과를 저장해둔 배열이다. - 첫 번째 행의 값들은 최솟값이자 최댓값이므로 4개의 배열에 모두 삽입해준다. - 첫 번째 행이 아닐 경우에는 minTmp, m..

문제 (https://www.acmicpc.net/problem/2211) 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 처음엔 MST를 사용해야하나? 라는 생각이 들었지만 다익스트라로 만들어진 MST와 MST는 서로 다르다는 반례를 보고 다익스트라로 문제를 해결했다. 11779 최소비용 구하기 2 문제에서 사용했던 방식과 유사하다. route라는 배열을 생성하여 배열의 해당 인덱스에 도달하기 위해서는 몇 번에서 와야 하는지를 기록한다. route[a] = b는 "a번에 최소로 도..

문제 (https://www.acmicpc.net/problem/13549) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 작년에 BFS로 풀었던 1697 숨바꼭질과 비슷한 문제이다. 다익스트라 알고리즘 스터디 주간에 고른 문제여서 다익스트라로 해결해보려 했지만,, 문제를 읽고 생각을 해봐도 1697번 문제처럼 BFS로 해결하는 방법밖에 떠오르지 않았다...! 그래서 일단 BFS로 해결 완! (코드 첨부) BFS로 해결할 경우 방문 순서에 따라 정답이 되기도 하고 아니기도 한..

문제 (https://www.acmicpc.net/problem/1238) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net N개의 마을에는 각각 한 명의 학생이 살고 있고, 입력받은 X번 마을에서 파티가 열린다. 모든 학생들의 이동거리는 최단거리여야 한다. N명의 학생들 중 (i번째 마을 -> x번 마을) + (x번 마을 -> i번째 마을) 시간이 가장 긴 학생의 소요시간을 출력하면 된다. Dijkstra Algorithm: '한 정점'에서 '모든 정점'으로의 최단경로 인접 리스..

문제 (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 이번 스터디 주제인 이분탐색으로 해결하려고 했으나 도저히 모르겠어서 크루스칼로 해결했다 🤯 중량의 최댓값을 구해야 하는 문제이므로 입력을 받은 후 간선의 크기를 기준으로 내림차순 정렬했다. 노드들을 합쳐가면서 매번 마지막 입력으로 들어온 두 섬이 연결되었는지 확인해야 한다. 연결이 되었다면, 연결된 모든 노드들 간의 간선들 중 가..