본문 바로가기

알고리즘연습90

[백준] 우선순위큐 - 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.
[Epper] 사다리(집으로 가는 길) 문제 겨울이와 친구들은 자신의 집으로 돌아가야 합니다. 겨울이 포함 4명의 사람이 있다고 했을 때, 현재 각 사람이 갈 수 있는 길은 그림1과 같습니다. 편의를 위해 사람에게 번호를 부여하였으며, 각 집에는 살고 있는 사람의 번호로 표시됩니다. 이런 도로상황에서, 우리는 강을 가로지르는 다리를 추가할 수도 하지 않을 수도 있습니다. 다리 추가 작업을 마친 후, 각 사람은 도로를 따라 목표지점인 본인 번호의 집까지 가야합니다. 1번사람을 예시로 들면, 아무런 다리가 설치되어 있 지 않을 경우, 3번집으로 가게 됩니다. 하지만 그림2 와 같은 다리가 놓여있을 경우라면, 모든 사람은 그림3처럼 빨간 경로를 따라 자신의 집에 도착하게 됩니다. 1번 사람은 1번 집, 2번사람은 2번 집, 3번 사람은 3번집, 4.. 2021. 9. 2.

티스토리툴바