유자의 코딩모험

1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 정수를 하나씩 받을 때마다 중앙값을 출력하는 문제다. 이 문제는 우선순위 큐 2개를 이용해서 풀 수 있다. 기본적으로 우선순위 큐가 Heap 구조이므로 Max Heap과 Min Heap 두 개를 선언한다. 비교함수를 따로 정해주지 않으면 기본적으로 내림차순에 따라 정렬한다. (Max Heap) // Min Heap priority_queue minheap; // Max Heap priority_queue maxheap; 중간값을 찾아야 ..

2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 문제풀이 이 문제는 우선순위 큐 2개를 이용해서 풀 수 있다. 기본적으로 우선순위 큐가 Heap 구조이므로 Max Heap과 Min Heap 두 개를 선언한다. 비교함수를 따로 정해주지 않으면 기본적으로 내림차순에 따라 정렬한다. (Max Heap) // Min Heap priority_queue minheap; // Max Heap priority_queue maxheap; 중간값을 찾아야 하므로 두 큐의 크기는 같아야 한다. 우선..

2900번: 프로그램 창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다. void something(int jump) { int i = 0; while (i < N) { a[i] www.acmicpc.net 문제풀이 이 문제는 something이라는 함수를 k번 호출하고 구간 합을 구하는 문제다. something 함수를 잘 보면 jump로 나누어 떨어지는 인덱스마다 1을 증가시키는 함수라는 것을 알 수 있다. jump 인자를 하나씩 입력받으면서 해당 값이 몇 번 나왔는지 카운트한다. 인자가 0부터 시작해서 jump만큼 더해가기 때문에 a[0]은 무조건 k이다. 0을 제외한 jump로 나누어떨어지는..

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. 위의 예시를 보자. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 동시에 진행할 수 있다. 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번 건물의 건설을 시작할 수 있다. 따라서 4번 건물의 건설을 완료하기 위해서는 10초 + 100초 + 10초 = 120초가 소요된다. 120초가 4번 건물을 가장 빨리 지을 때까지 걸리는 최소시간인 것이다. 건물 ..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. dp[i] = i번 건물을 건설 완료하는데 드는 최소 시간 최소 시간을 찾는 것이지만 선행 건물들이 모두 건설완료가 되어야하므로 최댓값을 찾는 것이다. 처음에 선행 정점을 가지지 않는 정점을 큐에 삽입할 때는 dp[i] = t[i]로 초기화해준다. 그리고 나서 다음 순서를 진행할 때 앞순서 건물 건설시간 + 현재 건물 건설시간이 최대인 것을 저장해주면 해당 건물을 건설완료 하는데 드는..

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제풀이 동굴의 길이가 N미터이고, 높이는 H미터이다. 이 동굴은 석순과 종유석으로 가득차 있는데 첫 번째 장애물은 항상 석순이고 그 다음부터는 종유석과 석순이 번갈아가면서 등장한다. 개똥벌레는 자신이 지나갈 구간을 정하면 일직선으로 지나가면서 모든 장애물을 파괴한다. 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 문제다. 먼저 석순과 종유석을 따로 배열에 저장한다. obs1은 석순이고 obs2는 종유석이다. 구간은 아래에서부터 시..

1205번: 등수 구하기 첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000 www.acmicpc.net 문제풀이 먼저 점수를 입력받아서 송유진의 새로운 점수를 추가한 후 내림차순으로 정렬한다. 같은 점수가 있을 때는 그러한 점수의 등수 중에서 가장 작은 등수가 된다. 예제를 한 번 살펴보자. 랭킹 리스트가 100, 90, 90, 80일 때 각각의 드수는 1, 2, 2, 4등이 된다. 점수가 제일 처음 나온 인덱스 + 1이 등수가 되고 동일한 점수가 나올 때까지 인덱스를 이동해준다. 송유진의 점수와 동일한 점수를 만날 때까지 반복문을 진..

10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 N개의 정수를 오름차순으로 정렬하는 문제다. 이때 같은 정수는 한 번만 출력해야 한다. 벡터를 정렬해서 중복을 제거한 후 출력을 해주면 되는 아주 간단한 문제다! C++ 코드