공작소

문제 링크 : https://www.acmicpc.net/problem/10423 풀이 과정목표는 모든 도시를 발전소가 설치된 도시와 연결하는 것, 연결할 때 케이블을 최소 비용으로 설치하는 것이다. 도시를 최소 비용으로 연결하기 위해 최소 스패닝 트리 알고리즘을 사용하지만, 모든 도시가 발전소와 단순히 "연결"되어 있기만 하면 되므로 이 알고리즘을 살짝 변형시켜주면 된다. 1. 크루스칼 알고리즘 변형하기 먼저, 기본 크루스칼 알고리즘의 전체적인 실행 순서에 대해 알아보자.n개의 노드가 있을 때, m개의 간선들을 비용 기준으로 오름차순 정렬한다.정렬된 간선들을 차례대로 순회하면서, 간선이 연결하는 두 노드가 다른 부모 노드를 바라볼 때 (그룹이 다를 때) 두 노드를 연결한다.2번으로 n - 1 개의 간선..

문제 링크 : https://www.acmicpc.net/problem/1477 풀이 과정처음 접근 방법은, 최대 길이 구간의 중간에 휴게소를 설치하는 아이디어였다. 예를 들면, n = 4, l = 700 이고휴게소 위치 :  100  200  500  600구간 길이 :  100  100  300  100  100일 때,최대 길이 구간인 200 ~ 500 중간에 휴게소를 설치하여휴게소 위치 :  100  200 (350) 500  600구간 길이 :  100  100  150  150  100  100 다음과 같이 최대 길이 구간을 찾고, 그 구간을 분할하는 걸 m번 반복할 생각이였다. 하지만 이 아이디어는 최적의 방법이 아니다. 중간 설치 아이디어 문제점 : 균일하게 나누는 것이 더 최적이다.예를 들..

문제 링크 : https://www.acmicpc.net/problem/5214 풀이 과정역 하나하나마다 간선을 연결하는 것은 너무 비효율적이다. 한 하이퍼튜브 안에서 모든 역은 연결되어 있기 때문이다.한 하이퍼튜브가 서로 연결하는 역의 개수 K의 최대 제한이 1000이므로, 각 하이퍼튜브마다 K(K-1) 개의 단방향 간선을 생성해야 하는 일이 발생한다. 한 하이퍼튜브 안에서 단번에 다른 하이퍼튜브로 갈 수 있는 방법이 필요하다.  바로 하이퍼튜브 정점을 따로 만드는 것이다. 하이퍼튜브 정점을 따로 만들면, 한 하이퍼튜브 안에 있는 역 정점들은 하이퍼튜브 정점 한 개를 거쳐서 바로 연결되고, 다른 하이퍼튜브 안에 있는 역 정점 또한 하이퍼튜브 정점을 거쳐서 바로 연결될 수 있다. 이 아이디어가 있으면, ..

프로그래머스 코딩테스트 연습 문제 중에서 2024 KAKAO WINTER INTERNSHIP 문제 세트를 알고리즘 스터디 중에 풀어보게 되었습니다. 해당 문제 세트를 어떻게 접근했고, 어떻게 코드를 작성했는지에 대한 전체 풀이 과정을 포스팅할 예정입니다. 제가 풀이한 과정이 모범 정답 풀이가 아닐 수도 있음을 밝힙니다. 단순히 제가 떠올리고 정답을 받은 풀이임을 알립니다! 1. 가장 많이 받은 선물다음 달에 선물을 가장 많이 받을 친구가 "다음 달에 받을 선물의 수"를 구해야 한다.다음 달에 선물을 받기 위해선 다음과 같은 조건이 필요하다.특정 두 사람이 주고 받은 선물 기록이 있다면, 더 많이 준 사람이 다음 달에 선물을 하나 받는다.선물 기록이 같거나 없다면, 선물 지수 (이번 달 준 선물 수 - 이..

강한 연결 요소 (SCC, Strongly Connected Component) 란, 유향 그래프에서 정점의 부분집합이 부분집합 내의 다른 모든 정점에 대해 방문 가능한 경우를 말한다. 쉽게 말해 사이클이 생기는 그룹을 엮으면 강한 연결 요소가 된다. 다음 그래프에서 사이클이 생기는 그룹을 엮어보자. 이 사이클이 생기는 그룹을 하나의 정점으로 보고 문제를 해결해야 하는 경우가 생길 수 있다. 따라서 이렇게 엮은 그룹들을 정점으로 치환하면 다음과 같은 그래프로 볼 수 있다. 정점 안에서 엮여진 하위 정점들은 그 정점 안이라면 언제든 방문 가능하다. 이렇게 강한 연결 요소로 묶으면 사이클이 없는 유향 그래프로 바라볼 수 있다는 특징이 있다. 이제 SCC 를 두 가지 방법으로 구현해보자. 타잔 알고리즘SCC ..

문제 링크 : https://www.acmicpc.net/problem/24520 문제신촌 왕국에는 1번부터 N번까지 N개의 마을이 있고 N-1개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다.현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에 더 가깝다면 아주 불편해진다. 따라서 두 사람이 사는 각 마을까지의 거리가 정확히 같은 곳을 약속..

문제 링크 : https://www.acmicpc.net/problem/13511 문제N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다.아래의 두 쿼리를 수행하는 프로그램을 작성하시오.1 u v: u에서 v로 가는 경로의 비용을 출력한다.2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같다.입력첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v와 간선의 비용 w가 주어진다.다음 줄에는 쿼리의 개수 M (1 ≤ ..

문제 링크 : https://www.acmicpc.net/problem/3176 문제N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,..

문제 링크 : https://www.acmicpc.net/problem/1761 문제N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.입력첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 입력된다. 두 점 사이의 거리는 10,000보다 작거나 같은 자연수이다.정점은 1번부터 N번까지 번호가 매겨져 있다.출력M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.풀이 과정https://readytojoin.tistory.com/entry/..

문제함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.f1(x) = f(x)f(n+1)(x) = f(fn(x))예를 들어 f4(1) = f(f(f(f(1))))이다.n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오.입력첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m)출력주어지는 n, x마다 fn(x)를 출력한다...