쫑쫑이의 블로그

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 중복되는 값들을 카운트할 HashMap과 오름차순 우선순위 큐, 내림차순 우선순위 큐를 만들어 입력 값이 I 일때 중복되는 값이 HashMap에 없으면 양쪽 큐에 다 넣고 중복되는 값이 HashMap에 있으면 value를 1 증가한다 입력 값이 D 일때 HashMap에 peek 값이 있고 value가 1보다 크면 value를 1 빼고 value가 1이면 HashMap에서 제거하고, 큐에서도 p..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬을 사용하여 먼저 지어야하는 건물 갯수만큼 가중치를 주고, 건물이 완성될 때마다 그 다음 지을 수 있는 건물의 시간 값을 최대값을 비교하여 넣어주고, 가중치가 0이 되면 건물 완성 큐에 넣는다 예제를 예시로 하면 가중치는 [0, 0, 1, 1, 2, 1]이 된다 (0번 인덱스는 사용안함) 가중치가 0인 값을 큐에 넣으면 1번만 큐에 들어간다 1 다음에 지을 수 있는 건물은 2, ..

https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 백준 월드에서 큐브 월드를 공격한다는 말은 백준 월드 수도 c와 큐브 월드 수도 v가 하나의 집합에 속해야한다는 뜻이다 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택한다는 말은 큰 길만 골라간 것과 같다 즉, c와 v가 하나의 집합이 될 때까지 너비 기준 최대 우선순위 큐로 입력값을 큐에서 하나씩 꺼내서 서로 연결되지..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 분리 집합 문제로 여행 계획에 있는 모든 도시들이 하나의 집합에 속해 공통 부모를 가지고 있는지 확인하면 된다 입력에서 1이 나온 부분을 i번째 도시와 j번째 도시를 부모가 같게 만든다 i번째 도시의 i보다 작은 숫자의 도시들은 이전에 중복 체크되니까 j의 시작을 i + 1로 하면 시간을 절반으로 단축할 수 있다 예제의 경우 그림에 빨간 선으로 표현한 것처럼 3번만 확인하면 된다 import ja..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 서로 같은 집합에 속해 있는지 확인하기 위해 모든 원소 값들을 자기 자신을 부모로 설정한다 입력값의 가장 첫 값이 0이면 a의 부모에 b의 부모를 넣거나 b의 부모에 a의 부모를 넣는다 (둘 중에 한가지만 일관되게 사용) 1이면 a의 부모와 b의 부모가 같은지 확인한다 여기서 설명하는 부모는 가장 최상위에 자기 자신을 부모로 하는 원소이다 import ja..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 규칙만 빨리 찾으면 쉬운(?) 문제지만, 규칙 찾는게 영 쉽진 않다 처음에 생각한 방식은 연속된 부분 구간의 합이니까 누적합을 생각해서 구해보았다 예제를 기준으로 1 3 6 7 9 이다 누적합을 구한 후 반복문으로 하나씩 탐색해가면서 앞에서 하나씩 빼가면서 나누어 떨어지는지 확인해보았다 이 방법대로하면 N^2의 시간복잡도로 시간초과이다 그래도 방법을..