알고리즘/문제풀이 - 백준

백준 2075 N번째 큰 수

문제 : https://www.acmicpc.net/problem/2075 서론 메모리 제한이 잡혀있다. 입력값을 전부 배열에 넣거나 큐에 넣으면 메모리초과가 발생할 것이다. 일부만 넣어야 한다. 아이디어 최소힙을 가지는 우선순위 큐를 만든 다음 큐에는 입력값 중 가장 큰 수 n개만 들어가도록 한다. 그럼 큐의 루트 힙이 정답이 될 것이다. 큐의 사이즈가 n개가 될때까지는 그냥 채워주고 n개가 되면 큐의 루트 힙보다 큰 값만 큐에 집어넣고 큐의 루트힙은 빼주면 된다. 그럼 입력값 중 가장 큰 수 n개가 들어있는 큐가 유지된다. 구현 //c++ #pragma warning(disable:4996) #include #include int main() { std::priority_queueq; int n; s..

2019. 8. 22. 11:49
알고리즘/문제풀이 - 백준

백준 1655 가운데를 말해요

문제 : https://www.acmicpc.net/problem/1655 서론 상당히 오래 걸린 문제. 반나절은 푼것 같다. 우선순위 큐는 내부 힙이 완벽히 정렬이 되지는 않지만 큐에서 빼낼때마다 배열에 저장하면 완벽히 정렬이 된다. 그래서 입력 한번 받을때마다 큐를 비웠다 채웠다를 반복해봤는데 시간초과 트리에서 수식으로 얻을 수 있는게 있는지 고민해봤으나 찾을 수 없었다. 엑셀에서 예상되는 결과를 표로 그려봤는데 시프트레지스터가 떠올라서 아이디어를 얻을 수 있었다. 아이디어 입력값이 들어올때마다 예상되는 중앙값을 표로 나타내봤다. 각 행의 노란색 셀이 중앙값인데, 노란색 셀이 두개면 둘 중 최소값이다. 우선순위 큐에선 입력될때마다 위와 같이 완벽히 정렬이 되지는 않지만 일단은 정렬이 된다고 가정하고 ..

2019. 8. 21. 20:29
알고리즘/문제풀이 - 백준

백준 11286 절댓값 힙

문제 : https://www.acmicpc.net/problem/11286 서론 1927 최소 힙 문제에서 힙 교환 조건을 크기에서 절댓값과 크기로 변경 1927 : https://hydroponicglass.tistory.com/54 구현 // c++ // min heap #pragma warning (disable:4996) #include #include #include typedef struct pq { int heap[100003] = { 0, }; int index = 0; }pq; void push(pq *q, int item) { q->index++; q->heap[q->index] = item; int index = q->index; while (abs(q->heap[index]) he..

2019. 8. 21. 14:36
알고리즘/문제풀이 - 백준

백준 1927 최소 힙

문제 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 서론 11279번 문제인 최대 힙을 변형했다. 백준 11279 최대 힙 문제 : https://www.acmicpc.net/problem/11279 서론 최대 힙에 관한 문제라서 최대 힙을 구현해봤다. 시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 � hydroponicglass.tistory.com 구현 최대 힙..

2019. 8. 21. 11:43
알고리즘/문제풀이 - 백준

백준 11279 최대 힙

문제 : https://www.acmicpc.net/problem/11279 서론 최대 힙에 관한 문제라서 최대 힙을 구현해봤다. 시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 인한 문제였다. printf, scanf 를 사용하여 해결했다. 구현 // c++ // max heap #pragma warning (disable:4996) #include #include typedef struct pq { int heap[100003] = { 0, }; int index = 0; }pq; void push(pq *q, int item) { q->index++; q->heap[q->index] = item; int index = q->index; whi..

2019. 8. 20. 20:20
알고리즘/문제풀이 - 백준

백준 17298 오큰수

문제 : https://www.acmicpc.net/problem/17298 서론 단순하게 이중반복문을 사용하면 시간초과 아이디어 현재 수와 다음 수들을 크기비교해야 하는데 스택을 이용할 수 있다. 현재 수가 스택의 탑보다 큰경우 탑을 출력함과 동시에 팝하는것을 반복한 후 현재 수를 스택에 넣으면 된다. 현재 수가 스택의 탑보다 크다는것은 현재 수가 스택의 탑(현재 수보다 이전에 나온 수)의 오큰수가 된다. 입력이 3 5 2 7일 때 1. 처음 3은 그대로 푸시 2. 5는 스택의 탑인 3과 비교하여 3보다 크니 5(3의 오큰수)를 출력하고 3을 팝, 5를 푸시 3. 2는 5보다 작으므로 그대로 푸시 4. 7은 스택의 탑인 2보다 크니 7을 출력하고 2를 팝, 다시 스택의 탑인 5보다 크므로 7을 다시 출..

2019. 8. 19. 18:01