본문 바로가기

알고리즘연습/백준65

[백준] 배낭문제 - 7579번 앱 java https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의.. 2021. 11. 8.
[백준] 우선순위 큐 - 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.

티스토리툴바