본문 바로가기

전체 글

 (125)
프린터 programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 이 문제에서 생각해 볼 점은 프린터의 인쇄 순위와 대기 목록의 후순위로 들어가야 하는 점이다. 각각을 자료구조로 나눠서 저장하고, 처리하도록 해보자 1. 프린터의 인쇄 순위 순위에 따라 정렬이 필요하기 때문에, 우선순위 큐를 이용하여 우선순위대로 정렬한 뒤, 대기 목록의 맨 앞의 우선순위와 일치한다면 pop한다. 2. 대기 목록 큐를 이용하여 대기하는 순서대로 pop한 뒤, 인쇄..
1806 부분합 처음엔 N^2으로 탐색을 시도했는데, 시간 초과가 나서 다시 생각해보니 worst case가 10^10인걸 알았다. 그리고 탐색의 범위를 줄일 수 있는 방식으로 이분탐색을 생각했지만 구현 방법이 까다로워 고민했는데, 다른 사람의 코드를 참고해보니 투포인터란 개념으로 범위를 줄일 수 있다는걸 알게 되었다. 투포인터란, 일정 범위의 값들을 해로 갖는 문제를 효율적으로 풀기 위한 개념이다. 문제의 정답 코드를 보며 예시를 들어보겠다. 처음 반복문은 이분탐색과 유사하다. 그런데, 오른쪽 포인터가 탐색 범위를 벗어나지 않는 조건이 포함된걸 알 수 있다. 이 문제에 적용한 개념은 다음과 같다. 1. 문제의 조건을 만족하면, 정답을 갱신하고 탐색 범위를 늘린다. (++right) 2. 문제의 조건에 미달하면, 탐색 ..
2467 용액 문제의 입력 조건에 오름차 순으로 입력되므로, 범위를 줄여가면서 탐색할 수 있다. 또한 N이 10^5이기 때문에 완전탐색을 사용하면 시간초과가 난다. 합이 0에 가장 가까운 두 개의 수를 찾는 문제이기 때문에 합이 음수라면, 왼쪽의 범위를 축소하고 합이 양수라면 오른쪽의 범위를 축소하면서 인덱스를 저장한다. 더보기 정답코드 #include using namespace std; #define MAX_SIZE 100000 int N; int arr[MAX_SIZE]; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &arr[i]); int start = 0, end = N - 1; long long sum = arr[start] +..

티스토리툴바