개발하지연

문제 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다. 편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나..

문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 기록 (greedy 7일차) 저번에 풀었던 문제(19598)과 비슷해서 금방 풀었다. 저번에는 heapq 사용해서 풀었는데 그 때 알게 된 간단한 방법이 있어서 이번에는 그렇게 풀어봤다. 최대로 중복되는 강의실 개수를 세는 방법이다. 힙 사용한 문제 풀이 >> 2021.07.16 - [알고리즘] - [백준 19598번] 최소..

문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 기록 (greedy 7일차) 난장판....ㅎㅎ 시간초과를 해결하기위해 내가 구현한 방법과 다른 방법을 사용해야했다. 기존엔 인덱스부터 K+1개까지 범위 내의 최댓값을 찾고 앞부분을 지우는 과정을 반복했다. 이 방법은 최댓값이 가장 앞에 있을 때 비슷한 범위를 중복되게 탐색해야한다는 점에서 시간초과에 걸렸던 것 같다. 따라서 숫자를 한 번 돌면서 stack을 사용해 내림차순이 되도록 크기비교하며 K개 제거한다. 이 문제의 해결방법은 결과숫자가 가능한 큰 숫자부터 내림차순으로 될 수 있도록 맨 앞부터 K개를 지워나가야한다는 것. 시간초과에 걸리지 않도록 최대한 탐색범위가 적은 구현방법을 찾..

문제 수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다. 이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오. 각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다 기록 (greedy 7일차) 힘들었다..! 처음엔 사람 수와 거리를 곱한 값을 사람 수로 나눈 평균거리를 계산했는데, 알고보니 합을 구하는 것과는 다른 계산이었다. 그래서 다른 방법을 검색해서 알아보았다. 이 문제의 핵심은 사람 수의 절반이 넘어가는 지..