분류 전체보기 (88) 썸네일형 리스트형 백준 19582 <200년간 폐관수련했더니 PS 최강자가 된 건에 대하여> 이 문제를 처음부터 탐색을 하면서 선택을 하던지 안 하던지를 정하는 문제이다 하지만 선택을 안 하는 경우는 딱 한가 지거나 없어야 한다는 것을 명심!! 간단하게 푸는 방법은 n개중 차례대로 하나씩을 빼면서 처음부터 탐색하는 것인데 그렇게하면 N^2이므로 시간 초과! 그래서 나는 하나를 선택하지 않은 경우와 전체를 선택한 경우 둘로 나눠서 문제를 풀어나갔다. 문제 풀이 처음 것을 택한 경우와 택하지 않은 경우로 초기화 이전의 택한 경우의 합이 제한 상금보다 작거나 같을 경우 업데이트 --> 선택한 경우 이전의 택한 경우+현재 택하지 않은 경우 VS 이전의 택하지 않은 경우 + 현재 택한 경우 -->한번 참가 안 한 경우 이렇게 두 가지로 나눠서 두가지 경우 중에 답이 있으면 "Kkeo-eok" 없으면 "Z.. 백준 20040 <사이클 게임> 이 문제는 누구 순서인지는 고려할 필요가 없는 단순히 지금까지 그린 선분이 사이클이 이뤄진 것인지 판단하는 문제이다. 이 문제를 다르게 생각하면 하나의 집합인가? 로 보면 되겠다. 그러면 이 문제는 union-find 문제이다. 자기 자신이 부모일 때까지 재귀를 돌려주고 최상위 부모로 전체를 세팅한다. 알고리즘을 많이 아는 것이 좋다는 점을 이런 문제를 보고 깨닫는다.! 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int p[],n,m,result; publi.. 백준 19236 <청소년 상어> 이렇게 푸는 문제가 맞나?라는 생각이 들게 한 시뮬레이션 문제. 매번 물고기 위치와 죽은 물고기수와 상어가 먹은 물고기 합을 들고 다녀야 한다는 게 너무 비효율적이라고 생각되었다. 물고기들을 한번 이동 시키고 상어가 갈 수 있는 방향에 있는 물고기를 먹으면서 먹을 수 없을 때까지 진행하는 문제이다. 풀이 방법 각각의 단계마다 map[][]과 물고기 위치를 표시한 num [][] 배열과 물고기들의 생존 여부 death []를 복사한다. 옮겨닮은 것들로 우선 물고기들을 이동 시킨다. 상어가 향하는 방향에 있는 물고기마다 dfs를 진행해 다음 단계로 향한다. 각 단계마다 물고기들을 먹은 count의 값을 비교해준다. 물고기의 현재 현재 위치랑 값을 담는 클래스를 선언! 1 전체의 상태를 옮겨 담는 과정 -->.. 백준 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가 빌때까.. 백준 17144 <미세먼지 안녕!> 설명이 잘되어 있는 말 그대로 주어진 순서에 맞게 해결하면 되는 시뮬레이션 문제이다. 골드 5 난이도로 삼성 역량 테스트 중에는 쉬운 난이도라고 볼 수 있다. 이 문제는 쉬운 문제이기때문에 함수를 구현해 각각의 함수가 잘 돌아가는지 테스트 겸 풀어도 좋을 것 같다. 문제 풀이 미세먼지 확산을 위한 추가의 visit[][]이차원 배열을 선언하고 확산시킨다. 이때 몇 번 확산시킬 수 있는지 세어줘야 현재의 남은 미세먼지도 정할 수 있다. 확산이 끝나면 다시 map에 이동 시켜준다. 공기청정기를 기준으로 위쪽, 아래쪽 따로 분리해서 계산해준다. 시간이 t가 지나면 남아있는 map의 미세먼지 수를 계산해주면 끝! 확산을 시켜주는 단계이다. 그 후 다시 map에 옮겨준다. 위 쪽을 먼저 순서대로 계산해준다. 마찬.. 백준 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을 선언해주.. 이전 1 2 3 4 5 6 ··· 9 다음
