우선순위 큐
-
백준 17140번 이차원 배열과 연산 :: 마이구미알고리즘 풀이/스택, 큐 2019. 6. 9. 00:36
이 글은 백준 알고리즘 문제 17140번 "이차원 배열과 연산" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 큐와 정렬을 이용해서 문제를 해결한다. 문제 링크 - https://www.acmicpc.net/problem/17140 크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 = 열의 개수라면 R 연산, 그렇지 않으면 C 연산을 실행한다. 2번이 의미하는 것은 다음과 같다. 1 2 1 1 3 4 4 => 1의 개수 => 3, 2의 개수 => 2, 3의 개수 => 1, 4의 개수 2개 위 결과를 수의 등장..
-
백준 11650번 좌표 정렬하기 :: 마이구미알고리즘 풀이/정렬 2016. 10. 19. 00:45
이번 글은 백준 11650번 좌표 정렬하기 문제를 다룰 것이다.문제는 간단하다.백준 11650번 좌표 정렬하기https://www.acmicpc.net/problem/11650백준 11650번 좌표 정렬하기 2https://www.acmicpc.net/problem/11651 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 문제에 보다시피 정렬하는 문제이다. 1차원적인 문제라면 정렬 문제는 정말 쉽다. 본인의 경우는 큰 어려움이 없는 한 Arrays.sort()를 통해 처리한다. 하지만 이렇게 2개 이상의 기준을 가진다면 조금 까다롭게 느껴진다. 이전 글에서도 정렬 문제를 다룬 적이 2번 있다...
-
백준 11279번 최대 힙 [Heap] :: 마이구미알고리즘 풀이/스택, 큐 2016. 8. 7. 14:50
이번 글은 백준 알고리즘 사이트 11279번 '최대 힙' 문제를 알아볼 것이다.자료구조 중 힙 에 관한 문제이다.Github - https://github.com/hotehrud/acmicpc 힙은 트리를 기반으로 된 자료구조다.일단 이것만 기억하면 된다.힙은 완전 이진 트리이다.이진트리는 자식노드가 최대 2개인 트리이지 않느냐?또한 균형이 잡혀있는 트리이다. 힙은 최대 힙과 최소 힙으로 나눌 수 있다.아래 그림처럼 최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지는 구조이다.최소 힙은 당연히 반대이다. 당연히 힙으로 푼다.혹시 이전 글 10814번 나이순 정렬 글을 보면 좋다.http://mygumi.tistory.com/44 이번에도 우선순위 큐로 문제를 해결할 것이다.나는 그냥 최대 힙을 구현해서..
-
백준 10814번 나이순 정렬 [Queue] :: 마이구미알고리즘 풀이/스택, 큐 2016. 8. 3. 18:57
이번 글은 백준 알고리즘 10814번 "나이순 정렬"에 대해 알아볼 것이다.본인은 다르게 풀었지만 다른 사람이 푼 것을 보고 이 글의 메인을 정했다.PriorityQueue 우선순위 큐를 통해 문제를 해결해보자.Github - https://github.com/hotehrud/acmicpc 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이 때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 큐는 모두 알다고 가정한다.큐에는 원형 큐, 우선순위 큐, 덱큐가 있다.PriorityQueue 이녀석은 해석하면 알겠지만 우선순위 큐이다.우선순위 큐는 말 그대로 우선순위가 높은 데이터를 먼저 꺼내온다. 이번 문제는 이해..