알고리즘 (56) 썸네일형 리스트형 백준 19644 <좀비 떼가 기관총 진지에도 오다니> 투 포인터 문제이다. 즉 윈도 슬라이딩 문제이다. 이 문제에서 가장 핵심은 기관통으로 죽일 수 있으면 죽이고 그렇지 않으면 폭탄을 사용하는 문제이다. 즉 쏴죽이지 못하거나 폭탄이 없다--> 죽는 상황이다. 또한 주의할 점은 폭탄과 기관총 두가지를 동시에 사용할 수 없다는 것이다. 문제 풀이 처음 기관총 사격 가능한 범위까지의 Point(몬스터의 위치, 사격 가능 범위)를 queue에 넣는다. 윈도 슬라이딩을 진행하면서 기관총으로 줄일 수 있는지 폭탄으로 죽여야 하는지 판단 폭탄으로 죽일시 다음 몬스터들이 기관총에 안 맞은 횟수를 처리해줄 것 문제를 해결하기 위해 2개의 큐를 사용했다. 한 가지는 윈도 슬라이딩을 사용할 큐, 그리고 폭탄으로 죽일 시 기관총 범위 가장 끝의 몬스터 넘버 기관총 범위 가장 끝.. 백준 20010 <악덕 영주 혜유> 최소 스패닝 트리를 찾고 그 지점에서 가장 긴 거리의 합을 계산하는 문제이다. 문제 풀이 0번 마을부터 시작해서 프림 알고리즘을 구성하면서 연결된 지점을 새로운 arraylist에 넣어준다. 0번 마을에서부터 dfs를 하면서 가장 길게 이어진 합을 갱신해준다. 최소 스패닝을 구하게 되면 그림과 같이 빨간색 선들로 이뤄진 길이가 된다. 그중 가장 긴 길이는 0번 집에서 6번 집까지의 거리를 구하는 것이다. 즉 dfs를 하면서 가장 긴 길이를 매번 update 해주는 것이다. 연결되어 있는 집들과 그사이의 거리를 담을 div 클래스를 생성한다. 최소 스패닝 트리를 구성하기위해 kruskal 또는 prim 알고리즘을 사용하면 되는데 나는 여기서 prim알고리즘을 사용했다. 마을과 마을 중 가장 먼 거리를 구하.. 백준 20007 <떡 돌리기> 성현이 집에서 모든 집의 가장 가까운 거리를 찾는 것이 필요한 문제이다. 즉 다익스트라 알고리즘을 사용하는 문제이다. 다익스트라 알고리즘을 사용하면서 마을마다 가장 가까운 거리를 기억하고 그 정보를 이용해 며칠이 걸리는지를 푸는 문제이다. 문제 해결 다익스트라 알고리즘을 이용해서 각각의 마을의 가까운 거리를 큐에 담아준다. 큐에서 꺼내면서 현재 이동할수 있는 거리보다 작으면 하루를 더해준다. 예외사항의 경우는 성현이 집에서 모든 집을 방문할 수 없을 때와 성현이가 왕복할 수 있는 거리보다 거리가 더 멀 때 -1을 출력한다. 문제를 잘읽자. 다익스트라 알고리즘이다. 이를 통해서 우선순위 큐로 인해 거리가 작은 순서대로 정렬되기 때문에 방문하지 않았을 경우 q에 담으면 거리가 가까운 순으로 정렬된다. 예외사.. 백준 2636 <치즈> 기본 완전 탐색으로 풀어도 통과가 되는 골드 5 수준의 문제이다. 치즈가 전체 꽉 차 있더라도 치즈가 녹는 시간은 가장 n과 m 중 큰 수의 1/2 그리고 접체 맵의 크기만큼 n*m이므로 n*m*(최대)/2 이므로 50만이 최대이기때문에 시간 초과는 날 수 없다. 그러나 맵 크기만큼인 최대인 10000번 으로 끝내는 방법으로 구성했다. 풀이 방법 0,0 지점은 치즈 가 존재하지 않기 때문에 bfs를 진행하며 visit처리를 하고 1 즉 치즈가 위치 한 곳이면 list라는 큐에 넣어 주었다. 가장 끝점의 치즈가 list에 담겨있을 것이고 여기서 Queue를 제거하면서 방문하지 않은 1이면 다시넣어주고 방문하지 않은 0이면 즉 --> 구멍이기 때문에 bfs를 수행해 list에 담아 주었다. list가 빌때까.. 백준 19640 <화장실의 규칙> 우선순위 큐를 사용하여 계산할 수 있는지를 묻는 문제이다. 각각의 사원을 D를 기준으로 H를 기준으로 i를 기준으로 comparable을 이용하여 비교를 할 수 있는지 묻는 문제이다. 이 문제의 핵심은 즉 comparable 이다. 이렇게 D를 비교해준 뒤 같다면 H를 비교 그리고 같다면 줄의 번호를 비교해서 우선순위 큐에 넣어주는 게 핵심이다. 그리고 각 줄의 첫 번째 인원이 존재하면 우선순위 큐에 먼저 넣어 주는 식으로 진행했다. 또한 다음 우선순위 큐에서 꺼내는 것이 k와 같다면 종료를 하게 하고 아니라면 꺼내 주고 해당 줄이 비어있지 않다면 우선순위 큐에 넣어주는 식으로 진행했다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOExcepti.. 백준 20005 <보스몬스터 전리품> 이문제는 BFS를 이용해 보스 몬스터까지 가는 가까운 거리를 알아내고 몬스터의 피를 줄여나가는 시뮬레이션 문제이다. 문제 풀이 보스몬스터 위치에서 BFS를 하여 각각의 플레이어까지 가는 최소 시간을 Queue에 넣는다. Queue에서 꺼내면서 같은 시간이 걸리면 계속 꺼내 주고 체력을 얼마만큼 깎을 수 있는지 계산한다. 몬스터의 피가 음수가 되면 break를 해준다. 플레이어의 id를 key로 dps를 value로 해서 Hashmap 에 저장을 해서 꺼내서 계산해준다. 보스의 위치에서 BFS를 하기위한 클래스를 선언 그렇다면 q에 보스에서 가장 짧게 걸리는 플레이어 순대로 이름과 걸리는 시간이 적혀있게 된다. 초기 값은 result를 0에서 1을 더해주고 깎을 수 있는 체력의 합을 더한 sum을 선언해주.. 백준 19953 <영재의 산책> 이 문제는 규칙을 잘 찾는 것이 중요한 문제이다. 초기의 v 값에 따라 반복되는 숫자가 달라진다. 예를 들어 초기값이 1이고 m이 1 인경우 이렇게 time=4번 만에 같은 값을 가지게 되고 초기값 13이고 m=3 인경우에 time=5번 만에 같은 값을 가지게 된다. 그러므로 time가 4와 5에 따라 계산을 다르게 해줘야 한다. 그래서 확인 해주기 위해서 ArrayList를 북 동 남 서 이렇게 4개를 만들어서 값을 넣어주면서 같을 때까지 진행하였다. 여기서 value는 몇 번 반복되는가를 나타내는 것으로 fv에 time값을 넣어주고 만약에 time이 5였다면 맨 초기의 속력 값을 따로 해줘야 하기 때문에 돌려야 하는 t값을 -1 해준 값으로 value를 구해준다. 반복되는 횟수만큼 이동을 진행한다. .. 백준 1744 <수묶기> 이 문제의 핵심은 어떻게 수를 묶을 것인가이다. 핵심을 파악하자면 음수는 음수끼리 양수는 양수끼리 묶는 게 결괏값이 더 커진다. 문제 접근 방법 음수는 음수끼리 양수는 양수 끼리 묶는다 가장 작은 음수는 그 다음 작은 음수와 묶는 것이 크고, 음수에 0을 곱하면 0 이 되기 때문에 이것 또한 작다. 양수는 가작 큰 양수와 그 다음 큰 양수를 묶으면 값이 커진다. 하지만 0을 곱하면 안 된다. 또한 1을 곱하면 자기 자신이기 때문에 1은 곱해주지 않고 그냥 더한다. 그래서 정렬을 해서 음수는 앞에서부터 양수는 뒤에서부터 계산을 해주면 된다. 음수 계산 방법 양수 계산 방법 2 1 2 답: 3 5 1 1 1 1 1 답: 5 이 반례들을 통해 1은 양수랑은 곱하지 않는것이 좋다는것을 이해했다!! 전체 코드 더.. 백준 19952 <인성 문제있어??> 잘 읽어보면 간단한 DFS 또는 BFS문제이다. 처음에 우선순위 큐로 풀어야 되나 라는 고민을 잠시 했지만 높이의 차만큼 에너지가 감소되는 것이 아니기 때문에 그냥 Queue로도 풀이가 가능하다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main{ public static class car{ int x; int y; int energe; public car(int x, int y, int.. 백준 2589 <보물섬> 일단 최단거리를 찾는 문제이기 때문에 BFS를 사용하는 것은 확실한 문제 그러나 가장 멀리 떨어진 지점을 어떻게 선택할까?라는 고민을 했던 문제. 일방적으로는 가장 끝지점을 고르면 되지 않을까? 하지만 예외상황이 있을 수 있음! 그렇기 때문에 생각한 방법은 완전 탐색으로 모든 지점에서 돌려보는 것!!! 시간 초과는 50*50이 맵 크기 이므로 50*50*50*50=6250000 625만 이므로 절대 터지지 않는다!! 그러므로 답은 bfs를 모든 지점에서 돌려 보는 것! 문제 풀이 1. L인 모든 좌표에서 BFS를 해서 가장 긴 길이를 리턴한다. 끝?! 좌표 x, y와 길이를 나타낼 d를 담을 클래스를 선언한다. BFS에서 핵심인 부분 뒤에 남은 큐가 없다는 것은 가장 긴 지점이므로 그 값을 저장한다. w.. 이전 1 2 3 4 5 6 다음
