본문 바로가기

전체 글116

[백준] 우선순위 큐 - 11286번 절댓값 힙 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최대힙과 최소힙에 이어서 또다른 우선순위큐 문제이다. 입력값 자체가 아니라 입력값의 절댓값이 비교 기준이 되는데 이를 구현하기 위해 compare를 오버라이딩하여 구현하였다. PriorityQueue q = new PriorityQueue( (o1, o2) -> Math.abs(o1) == Math.abs(o2) ? Integer.compare(o1, o2) : I.. 2021. 10. 5.
[백준] 우선순위큐 - 1927번 최소 힙 java 문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 풀이 최소 힙은 최소 값을 빠르게 찾는 자료구조로, 우선순위큐를 통해 구현한다. 자바에서 제공하는 Priorit.. 2021. 10. 3.
[백준] DFS와 BFS - 7562번 나이트의 이동 java 문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 bfs를 이용하여 풀었다. 나이트는 직선으로 2칸 이동 후 오른쪽 혹은 왼쪽으로 한칸 이동하기 때문에 그에 맞춰 이동 배열(dx, dy)를 선언해주었다. 코드 package DFS와BFS; import java.util.*; import java.io.*; public class No7562_나이트의이동 { static int[] dx= {-2, -2, -1, -1, 1, 1, 2, 2}.. 2021. 9. 23.
[Epper] 백준 19538 루머 java 문제 귀찮아서 생략.. 백준 문제와 달리 이퍼 시험에서는 메인 함수를 작성하지 않아도 되기 때문에 따로 입력받지 않고 그냥 예시에 나와있는 값으로 하였다. 또 풀이를 쉽게 하기 위해 처음에 0을 추가로 입력시켜 주었다. 풀이 백준의 바이러스 문제와 비슷하게 감염을 시키는 문제이다. 이 문제 역시 bfs를 사용하여 풀 수 있다. solution 함수에 대해서 설명하자면 answer은 반환할 정답 배열, turn은 몇명 이상이 감염되어야 i번 사람이 감염되는지 저장하는 배열이다. turn 배열은 bfs를 진행하면서 i의 주변인이 감염되면 turn[i-1]-=1(배열 인덱스는 0부터 시작하기 때문에 -1을 해줌)을 해주고 이 값이 0이하가 되면 감염되는 코드이다. answer배열을 -1로 초기화하는 이유는 해.. 2021. 9. 4.

티스토리툴바