본문 바로가기

알고리즘78

14226번 - 이모티콘(bfs) 문제:영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.화면에 있는 이모티콘 중 하나를 삭제한다.모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.. 2024. 7. 31.
13913번 - 숨바꼭질4(bfs) 드디어 마지막 숨바꼭질 문제다.문제:수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1 또는 2*X의 위치로 이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법을 구하시오.첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.풀이:이전 숨바꼭질 문제들과 같이 bfs를 활용하여 푸는 문제이다.수빈이가 현 위치에서 다음 위치로 갈때, 다음 위치에 현 위치에서 출발했다는 흔적을 남기고,역순으로 출력해주면 문제가 풀릴 것이다.이를 위한 코드는 아래와 같다.static void bfs() { Queue queue = new LinkedList(); qu.. 2024. 7. 30.
13549번 - 숨바꼭질3(bfs) 문제:수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1으로 이동할 수 있고,0초 후에 2*X의 위치로 순간이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 풀이:수빈이와 동생은 모두 0 ~ 100,000 사이 점에 위치한다. x는 0과 100,000을 넘어갈 수 없다.그렇다면 BFS와 우선순위 큐를 사용해 수빈이가 가장 먼저 K에 도착하는 순간 그 시간을 반환해주면 될 것이다.우선순위 큐를 이용하기 위해 아래 클래스를 작성한다.class Node imp.. 2024. 7. 29.
12851번 - 숨바꼭질2(bfs) 문제:수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1 또는 2*X의 위치로 이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 풀이:수빈이가 어떤 위치로 이동하기 위해서는 X-1 또는 X+1 또는 2*X 로 이동 할 수 있다.가장 빠른 시간 안에 찾는 경우의 수를 구해야 하므로 BFS를 사용하면 될 것이다.일일히 진행하며 모든 수를 저장하고, 일일히 꺼내 쓰는 방법은, 너무 많은 저장공간을 요구한다.그래서 아래와 같이 생각을 해보았다. 두개의 스택 st.. 2024. 7. 28.

티스토리툴바